В лифте двадцатиэтажного дома работают только две кнопки: «5» (при нажатии на эту кнопку лифт поднимается на 5 этажей вверх, если это возможно) и «7» (при нажатии на эту кнопку лифт опускается на 7 этажей вниз, если это возможно). Можно ли, пользуясь таким лифтом, попасть: а) с первого этажа на второй; б) со второго этажа на первый; в) с третьего этажа на двадцатый?

Решение:

Эта задача решается как задача на достижимость состояний. Мы можем представить этажи как узлы графа, а нажатие кнопок — как переходы между узлами.

Начальное положение — 1-й этаж.

Кнопка «5»: +5 этажей (если этаж <= 15)

Кнопка «7»: -7 этажей (если этаж >= 8)

Разбор подпунктов:

• а) С первого этажа на второй:
  • Находясь на 1-м этаже, нажатие кнопки «5» приведет нас на 1 + 5 = 6-й этаж.
  • Находясь на 6-м этаже, нажатие кнопки «7» приведет нас на 6 - 7 = -1 этаж (невозможно, так как этаж должен быть >= 1).
  • Находясь на 6-м этаже, нажатие кнопки «5» приведет нас на 6 + 5 = 11-й этаж.
  • Продолжая последовательность, мы не можем получить 2-й этаж.
• б) Со второго этажа на первый:
  • Находясь на 2-м этаже, нажатие кнопки «5» приведет нас на 2 + 5 = 7-й этаж.
  • Находясь на 7-м этаже, нажатие кнопки «7» приведет нас на 7 - 7 = 0 этаж (невозможно).
  • Находясь на 7-м этаже, нажатие кнопки «5» приведет нас на 7 + 5 = 12-й этаж.
  • Продолжая последовательность, мы не можем получить 1-й этаж.
• в) С третьего этажа на двадцатый:
  • Находясь на 3-м этаже, нажатие кнопки «5» приведет нас на 3 + 5 = 8-й этаж.
  • Находясь на 8-м этаже, нажатие кнопки «7» приведет нас на 8 - 7 = 1-й этаж.
  • Из 1-го этажа мы не можем попасть на 20-й (см. пункт а).
  • Рассмотрим другие комбинации:
    • 3 + 5 = 8
    • 8 + 5 = 13
    • 13 + 5 = 18
    • 18 + 5 = 23 (невозможно, так как 23 > 20)
  • Попробуем другие последовательности, чтобы попасть на 20-й этаж.
  • Путем перебора или решения уравнения в общем виде (3 + 5a - 7b = 20, где a и b — количество нажатий кнопок) можно показать, что 20-й этаж недостижим.
  • Например, 3 -> 8 -> 1 -> 6 -> 11 -> 4 -> 9 -> 2 -> 7 -> 12 -> 5 -> 10 -> 3 (цикл)

Ответ:

• а) Нет
• б) Нет
• в) Нет