|
|
 |
Условие
Саша написал по кругу в произвольном порядке не более ста различных натуральных чисел, а Дима пытается угадать их количество. Для этого Дима сообщает Саше в некотором порядке несколько номеров, а затем Саша сообщает Диме в том же порядке, какие числа стоят под указанными Димой номерами, если считать числа по часовой стрелке, начиная с одного и того же числа. Сможет ли Дима заведомо угадать количество написанных Сашей чисел, сообщив
а) 17 номеров;
б) менее 16 номеров?
Решение
а) Пусть Дима сообщил Саше следующие 17 номеров: 1, 2, ..., 10, 40, 50, ..., 100. Если числа, стоящие под номерами m и n (n > m), совпали, то количество написанных Сашей чисел является делителем числа n – m. Разность n – m для названных Димой номеров может равняться: 1, 2, ..., 10, 30, 31, ..., 99.
Будем перебирать по очереди все возможные варианты количества написанных Сашей чисел от 1 до 100. Если Саша написал одно число, то Дима узнает это, сравнив первое и второе число. Предположим, что Дима уже знает, что Саша написал не меньше k чисел, где k = 2, 3, ..., 99. Покажем, как Дима сможет определить, написал Саша ровно k + 1 число или нет.
Если k = 2, 3, ..., 9, то Дима сравнивает первое число и число с номером k + 1. Их совпадение будет означать, что количество написанных Сашей чисел является делителем k. Учитывая, что Дима уже знает, что этих чисел не меньше k, он получит, что k и есть искомое количество. Аналогично, если k = 10, 30, 31, 32, ..., 99, он сравнит два известных ему числа с разностью номеров, равной k, и точно узнает, является ли k количеством написанных Сашей чисел. Если же k = 11, 12, ..., 29, то Дима сможет подобрать среди известных ему чисел такие две пары, разность номеров первой из которых равна 2k, а второй – 3k. Если в каждой из пар числа совпадут, то k – непременно искомое количество чисел, ведь это единственное число, не меньшее k, которое делит и 2k и 3k. Наконец, если k = 100, то Дима сможет заключить, что Саша написал ровно 100 чисел.
б) Пусть n – количество написанных Сашей чисел. Покажем, как Дима сможет узнать его разложение на простые множители, сообщив Саше 15 номеров.
Пусть N = 26·34·5²·7²·11·13·17·19·23·29·31·37·41·43·47·53·59·61·67·71·73·79·83·89·97 – наименьшее общее кратное всех чисел от 1 до 100. Каждому из чисел 2k (k = 1, 2, ..., 6) сопоставим число 27–k, каждому из чисел 3l (l = 1, 2, ..., 4) – число 35–l, каждому из чисел 5m и 7m (m = 1, 2) – числа 53–m и 73–m соответственно, каждому простому числу от 11 до 97 – само это число. Заметим, что число с номером 1 + N/s, где s – делитель N, будет совпадать с первым числом тогда и только тогда, когда N/s делится на n. Заметим также, что N/s делится на n тогда и только тогда, когда для любого делителя числа n вида 2k, 3l, 5m, 7m, 11, ..., 97 сопоставленное ему число не является делителем числа s.
Перечислим номера, которые должен назвать Дима. Пусть первым Дима назовёт номер 1. Нетрудно видеть, что никакие два из 25 чисел 24, 3³, 5², 7², 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 и 97 не могут одновременно являться делителями числа n. Присвоим каждому из этих чисел свой код от 00001 до 11001, состоящий из пяти цифр 0 или 1. Пусть со второго по шестой номера Дима назовёт где sj (j = 1, 2, ..., 5) – число, равное произведению всех чисел, сопоставленных каждому из упомянутых 25 чисел, код которых содержит единицу на месте j.
Эти номера позволят Диме определить, является ли одно из упомянутых 25 чисел делителем числа n. Для этого ему понадобится сравнить числа с номерами 1 и (j = 1, 2, ..., 5) и составить новый код, где на месте j будет стоять 0, если числа совпали, и 1 в противном случае. Если получится код 00000, то ни одно из упомянутых 25 чисел делителем n не является. Если же получился другой код, то Дима определит, что делителем n будет то самое число, код которого получится.
Никакие два из трёх чисел 26, 34 и 5 не могут одновременно являться делителями числа n. Присвоим каждому из этих чисел свой код от 01 до 11, состоящий из двух цифр 0 или 1. Пусть седьмым и восьмым Дима назовет номера ,
где sj+5 (j = 1, 2) – число, равное произведению всех чисел, сопоставленных каждому из упомянутых трёх чисел, код которых содержит единицу на месте j. Как и ранее, эти номера позволят Диме определить, является ли одно из упомянутых трёх чисел делителем числа n, и если да, то какое из них.
Пусть также Дима назовёт номера Как и ранее, эти номера позволят Диме определить, являются ли числа 25, 2³, 2², 2, 3², 3 и 7 делителями числа n.
Таким образом, Дима сможет определить разложение числа n на простые сомножители, а значит и само число n, сообщив Саше менее 16 номеров.
Ответ
Сможет.
Замечания
15 номеров – далеко не наименьшее возможное количество, благодаря которому Дима всегда сможет отгадать количество написанных Сашей чисел.
