1. 100 дверей

Created Wednesday 08 October 2014

https://www.youtube.com/watch?v=Z41uWyelHKE

Имеется 100 пронумерованных дверей — 1 .. 100
Изначально все двери закрыты.
1-й шаг: каждая дверь меняет своё состояние (если открыта — закрывается и наоборот)
2-й шаг: каждая 2-я дверь меняет своё состояние
3-й шаг: каждая 3-я дверь меняет своё состояние
...
100-й шаг: каждая 100-я дверь меняет своё состояние

Вопрос: какие двери будут открыты (закрыты) через 100 шагов?

Моё решение:

Обобщение: 100 бит в состоянии 1
Ограничение: рассмотрим 10 шагов для 10 бит

Результат:
  1. i-й бит меняется на каждом шаге, номер которого (шага) является множителем числа i.
  2. На основе п. 1. можно вычислить значение всех битов на сотом шаге.

Из урока:

  1. Попробовать проанализировать и решить эту же задачу, но меньшей размерности, и обобщить до заданной размерности.
  2. Автор выбрал 10 дверей :)
  3. На i-том шаге происходит изменение всех позиций, номера которых делятся на i.
  4. Если над дверью произведено чётное количество изменений состояния, то конечное состояние двери будет равно начальному
  5. Т.е., состояние двери изменится только если количество операций над дверью было не чётным.
  6. Открыты (0) двери 1, 4, 9
  7. Гипотеза: возможно, только квадраты чисел ряда 1, 2, 3, 4, ... будут номерами открытых дверей...
    1. Дверь открыта, если её номер есть квадрат натурального числа
  8. Мы меняем состояние двери только тогда, когда номер итерации является делителем номера двери
  9. Дверь открыта тогда и только тогда, когда её номер имеет нечётное количество делителей
  10. У каких из чисел от 1 до 100 есть нечётное количество делителей?
  11. Может быть нечётное количество делителей есть у квадратов?
  12. Если у числа Ч есть делитель А, то у него также есть делитель Б, такой, что А х Б = Ч
    1. Если А = Б, то делитель 1, вместе с 1 и самим числом
      1. Если у числа есть другие неравные друг другу делители, то всё равно общее количество делителей будет нечётным (минимум 3)
      2. Число, у которого есть делители А х Б, А = Б — квадрат



Backlinks: