Выдающийся ум

300000

Выдающийся ум

Общее количество прослушиваний: 445808

Количество цифр		0
Диапазон цифр 1..		0
Максимальное количество раз, которое может встречаться цифра		0
Максимальное количество попыток		0

Аббревиатура

Как можно разбить всю проблему на подцели?

Какими могут быть очень общие принципы для формулировки следующей догадки?

Полезные инструменты:

Для первого этапа А) полезно записать все возможные цифры, почему?

Для фазы Б) полезно иметь таблицу выбывания, как и почему?

А) Как попытаться найти все горячие цифры?

После отправки предположения, какие результаты (ответы) были бы очень полезны?
- Нам повезло, если окажется, что все или большинство угаданных цифр являются горячими, но мы также получаем много информации, если два возвращенных числа равны 0, потому что тогда ни одна из угаданных цифр не встречается в решении, т.е. все угаданные цифры холодные. В этом случае мы можем вычеркнуть N цифр из списка возможных цифр или N строк в таблице исключения.

Если нам не так повезло, то какова возможная стратегия для поиска большего количества горячих цифр?
- Предположим, что решения состоят из 4 цифр и что цифры 1,..,9 могут выпасть не более одного раза (в противном случае измените следующие 3 предложения). С решением, содержащим 4 цифры, мы угадаем 1,2,3,4, а затем 5,6,7,8 и автоматически узнаем о 9, подсчитав, сколько цифр 1,..,8 являются горячими. Если было четыре горячих цифры, то 9 – холодно, иначе – горячо. Если нам повезет и 1,2,3,4 уже горячие, то мы не будем пробовать другие цифры, так как они холодные.

Предположим, что мы сделали несколько догадок, скажем, 7, после чего мы знаем для каждой цифры, горячая она или холодная.
Имеет ли значение, содержали ли эти 7 догадок в основном горячие или холодные цифры?
- Кажется одинаково полезным угадывать и знать все горячие цифры или угадывать все холодные цифры, потому что, зная один набор, знаешь и другой набор. Но это не так. Если в наших догадках много горячих цифр, то мы собираем на стороне еще и дополнительную информацию о правильных или неправильных позициях этих горячих цифр. Мы не будем собирать эту информацию, если наши догадки содержат в основном холодные цифры.
- По какому принципу мы отправляем догадки с большим количеством горячих цифр?
  - Принцип 1, потому что мы дополнительно собираем информацию о позициях, которая пригодится нам позже, когда мы узнаем все горячие позиции.
- Можете ли вы представить себе формулировку догадок, которые следуют принципу 2? Другими словами, какие догадки дают ответы, которые легко использовать?
  - Следуя принципу 2, мы можем взять предположение и изменить его, убрав одну цифру, скажем, 5, и другую цифру, скажем, 3. Если в новой догадке меньше горячих цифр, то 5 — горячее, а 3 — холодное. Если в новом предположении больше горячих цифр, то 5 — холодное, а 3 — горячее. В противном случае 5 и 3 оба горячие или оба холодные. Чтобы разобраться между этими двумя случаями, в следующем предположении можно получить и то, и другое, 5 и 3. Решая, какую догадку изменить на одну цифру, мы следуем более ранней подсказке и выбираем предыдущее, у которого было больше всего горячих цифр, чтобы также собрать информацию о позициях и следовать принципу 1.
Предположим, вы последовали предыдущему указанию и предположили, где поменяли местами только одну цифру, скажем, 7 на 3, и из результата вы узнали, что новая цифра 3 — горячая, а 7 — холодная.
Это все, что вы узнали из этой догадки?
- Нет. Теперь вы можете вернуться к более ранним догадкам и использовать знание о том, что 3 — горячее, а 7 — холодное, чтобы извлечь больше информации из предыдущих догадок. Например, более раннее предположение включало 3 и имело только одну горячую цифру, тогда как другие цифры в этой догадке холодные. Тот факт, что они холодные, может дать вам подсказку о том, какие другие цифры горячие, от других догадок и так далее.

Если вы решили, какие цифры должны быть в следующей догадке, имеет ли значение, в каком порядке их разместить?
- Если вы решили, какие цифры должны быть в следующей догадке, имеет ли значение, в каком порядке их разместить?
Как только мы узнаем все горячие цифры, мы также знаем все холодные цифры и можем вычеркнуть их строки в таблице на выбывание.

Б) Как мы можем найти положение каждой горячей цифры?

Теперь, когда мы знаем все горячие цифры, какая обратная связь была бы очень полезна?
- Если все угаданные цифры находятся на правильном месте, то, конечно, нам повезло и мы решили задачу. Еще один удачный исход – когда ни одна из угаданных цифр не находится в правильной позиции. Тогда мы многому научились и можем вычеркнуть N полей в таблице выбывания.

Вспомним, как мы можем использовать таблицу устранения на этом финальном этапе решения.
- Если все строки холодных цифр зачеркнуты, и если есть строка или столбец только с одним полем, которое не зачеркнуто, то это говорит нам, какая цифра занимает эту позицию в решении, а остальные свободные поля в этом столбце могут быть зачеркнуты. Если каждая цифра может встречаться только один раз, то также все поля в этой строке могут быть зачеркнуты.

Сколько чисел может быть сформировано из горячих цифр?
- Каждая такая последовательность цифр называется перестановкой. Итак, вопрос в том, сколько перестановок существует для N объектов, здесь N цифр?
  Если все цифры отличаются, то для первой цифры есть N вариантов. Для каждого из этих N существует N−1 вариантов для второй цифры. Для каждой из этих N×(N−1) комбинаций существует N−2 вариантов для третьей цифры и так далее, всего N×(N−1)×...×2×1 = N! (называемый N-факториалом) многие.
  Если не все цифры отличаются, то мы можем иметь, например, N=4, а 4 горячие цифры равны 2,2,2,5. Тогда продукт N! = 4! Приходится делить на 3! Потому что порядок между тремя двойками не имеет значения. Мы получим 4!/3! = 24/6 = 4 (или более элегантно 4!/3! = 4×3! / 3! = 4).
- Сколько их для N=3 или N=4?
  - Если каждая цифра выпадает только один раз, мы получаем 3! = 3×2×1 = 6 и 4! = 4×3! = 24 перестановки (последовательности). Это не так уж и много.
- Что это означает для поиска решения?
  - Можно записать все числа (перестановки N горячих цифр) и проверить их одну за другой относительно всех предыдущих догадок. Обычно только одно или два из этих чисел остаются возможными, которые можно попробовать в качестве следующей догадки.

Обратите внимание: после догадки мы можем знать, каким должно быть решение, но нам все равно нужно отправить решение, чтобы доказать компьютеру, что мы его нашли.

Как часто в среднем приходится гадать, если следовать приведенным выше подсказкам?