Фокусник

[molch64]

На мой взгляд, очень красивая задача. Сразу скажу источник - финал всероса по математике, прошедший 2 недели назад в Майкопе.

Фокусник с помощником собираются показать такой фокус:
Зритель пишет на доске последовательность из N цифр. Потощник фокусника закрывает две соседние цифры черным кружком. Затем входит фокусник. Его задача - отгадать обе закрытые цифры (и порядок, в котором они расположены).
При каком наименьшем N фокусник может договориться с помощником так, чтобы фокус гарантированно удался.

[Инна]

На мой взгляд, очень красивая задача. Сразу скажу источник - финал всероса по математике, прошедший 2 недели назад в Майкопе.

Фокусник с помощником собираются показать такой фокус:
Зритель пишет на доске последовательность из N цифр. Потощник фокусника закрывает две соседние цифры черным кружком. Затем входит фокусник. Его задача - отгадать обе закрытые цифры (и порядок, в котором они расположены).
При каком наименьшем N фокусник может договориться с помощником так, чтобы фокус гарантированно удался.

Задачка была только что на всероссийской олимпиаде по математике.

[Dendr]

Ну.. в первую очередь можно дать грубую оценку снизу. Фактически, надо назвать двузначное число (при этом первая цифра может быть и нулем), т.е. 100 вариантов.

N=3 - явно мало. Войдя в комнату, фокусник номер 2 увидит кружок и цифру (слева или справа от кружка). Т.е. 2*10=20 вариантов. Информации недостаточно в любом случае.

N=4. Он увидит либо двузначное число слева/справа от кружка, либо две цифры по бокам от кружка. Всего 3*100=300 вариантов.

При произвольном N, имеем (N-1)*(10^(N-2)) вариантов.
Для справки - список:
5--4000
6--50000

Можно предположить, что для N=6 подойдет любой алгоритм, даже взятый с потолка. Для 5 - уже надо думать более серьезно.

Первая задача здесь, получается - найти алгоритм договоренности для N=4. Теоретически, он может существовать. Либо - доказать, что такого алгоритма не существует, и перейти к N=5.
Думаем дальше.

[Semak]

Не совсем так.
Мы же не сами пишем цифры, откуда такое бешенное число вариантов?
Проще рассматривать, сколькими вариантами мы можем закрыть написанные цифры. В случае для N = 4 таких вариантов только 3.
Ежу понятно, что как бы мы ни старались - не отгадать даже одну из 10 цифр, что под кружком.

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

Скорее тут другое. Нам нужно понять, при какой длине строки мы гарантированно найдем заранее известную пару цифр, которую и назовет "фокусник". Но человек может писать строку из одинаковых цифр до бесконечности... Похоже, надо искать алгоритм.

[Dendr]

исправился... не то написал.

[Semak]

Интересно взять два предельных случая:
- строка из одинаковых символов, вроде 111111111
- любое иррациональное число, например число пи

Алгоритму должно быть пофиг, раз фокус гарантирован. Значит не нужно искать закономерности и периодичности в строке, их может и не быть.

[Semak]

Бредовая мысль про суммы цифр.
Закрывая две цифры определенным образом, мы можем постараться сделать так, чтобы итоговая сумма была четным или нечетным числом.

Но тоже не получается.
Если строка вроде 1111, то что ни закрывай, получишь всегда сумму 2
Если вроде 1234, то на выходе могут получиться суммы 7, 5, 3 (то есть только нечетные)
А если что-то вроде 1233, то на выходе может быть 6, 4, 3 (то есть как чет, так и нечет)

увы

[Dendr]

А вот если так подойти.

Обозначения
a, b, c, d, e, f, ..., v, w, y, z - цифры, известные фокуснику №2.
х - закрытые цифры.

Пусть он вошел и видит надпись:
abcdefxx
И он тут же говорит:
это "yz"!
Т.е., если зритель напишет abcdefyz, то помощник фокусника закроет последние две цифры.
А вот если напишет abcdefgh?

Надо закрывать другую пару - это понятно.

Нет, не то что-то... Дальше ступор

[Dendr]

Пока доказал, что 5 цифр - мало.

Например, зритель написал 12345 (конкретные значения цифр роли, на самом деле не играют, в этом доказательстве - особенно это касается 1, 3, 5). Предположим, что, по договоренности, помощник закрывает первые две цифры, т.е. фокусник увидит вот это: **345.
Но зритель мог бы написать и 13345, и 17345...

Предположим, что при написании 13345 закрываются цифры - вторая и третья, т.е.: 1**45 (а может, и нет - при любой второй цифре этого не произойдет - но это не влиляет н доказательство).
Рассмотрим вариант: 16345. Если закрывать первые две цифры, то получится **345, если вторые, то 1**45. В любом случае - повтор.
Значит, надо закрывать 3-4 либо 4-5. Т.е.:
16**5 или 163**.
Аналогично, если заменить шестерку на любую цифру от 4 до 9, или 0, или 1. Всего - 8 цифр. И во всех случаях обязательно закрывается цифра 4: 1?**5 или 1?3** (где на месте вопроса одна из цифр 01456789)

Возьмем другую 4-ю цифру, даже две. Например, 1?375 и 1?305.
В этих случаях, допустим, 4-я цифра закроется в том случае, когда на втором стоит: не 2 и не 3 для семерки и не 4 и не 5 для ноля.
(значения цифр, еще раз отмечу, не важны - они могут и повторяться - но это только еще больше утвердит правоту доказательства.

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

Т.е., второй фокусник увидит вот что, например:
173** или 17**5. И (!) это может обозначать: 17345, 17375 или 17305.
Уже три числа на два варианта. Таким образом, так передать информацию не получится.

Следовательно, N>5 (по крайней мере).

Для 6 такое доказательство уже не прокатывает.

[Atson]

Я лично с другой стороны пошел. Нужно отгадать цифру в сторичной системе счисления. Попробуем предложиь алгоритм договоренности фокусника и помощника сначала в двоичной системе.
Тут я малость потупил, некоторое время думал - его нет. А алгоритм простой. Если цифры одинаковые - закроем первую, разные - вторую. Нужно 2 цифры.
Далее в троичной и обобщим...
Только вот я пока сижу на троичной, и не особо-то получается.

[Semak]

Кстати, про двоичную систему - это круто!
Действительно, давайте попробуем родить алгорим для последовательностей вида 0110011001... и т.п.

Вот это я не совсем понял:

Если цифры одинаковые - закроем первую, разные - вторую

Одинаковые могут быть как 00, так и 11
Разными соответственно 01 и 10
В нашем распоряжении - позиция кружочка (начиная с какого символа N мы закрываем цифры)
И собственно сами закрываемые цифры выбрать - тоже в нашей власти.

Хорошо бы для начала вот еще что выяснить.
Допустим нам надо угадать не обе цифры, а всего лишь одну.
И даже еще проще - неважно, на каком месте она стоит.
То есть фокуснику надо ответить на вопрос, а есть ли под кружочком единичка?

Если у нас строки длиной в 3 символа, то могут быть варианты:
000
001
010
011
100
101
110
111

Если закрываем левые две цифры, то единичка под кружком будет всегда кроме вариантов 000 и 001

Если же закрываем кружком правые две - то единичка под кружком будет всегда кроме вариантов 000 и 100

Таким образом, общая цифра в этих двух вариантах - это 000.
Значит примем за аксиому, что в случай 000 мы закрываем первые две цифры. И если мы закрытли первые две и справа видим ноль, то это только 000 и ничего более, то есть под кружком нет единичек.

Все остальные случаи мы закрываем кружком правые две цифры. И что бы мы не удидели слева, под кружком будет гарантированно минимум одна единичка.

...
Теперь надо попытаться определить, на каком месте стоит эта единичка, после чего пробовать угадывать уже сразу две цифры.

[Atson]

Semak
Я как раз и говорил про закрытие одной цифры (вроде, так тогда и написал). И все ясно тогда - первая цифра 0 (1) - вторая закрыта - говорим 0 (1). Первая закрыта, вторая 0 (1) - говорим 1 (0).
А выбираем мы, все-таки, только позицию кружка, а никак не закрашиваемые цифры.
И чем больше я думаю над двумя двоичными или одной троичной цифре, тем больше сомневаюсь в возможности такого фокуса.

[Atson]

Поскольку братья по разуму задачкой не заинтересовались (может, знали уже), а я уже устал думать над доказательством невозможности такого фокуса, не пора ли дать ответ?

Кстати, я некоректно говорил о цифре в сторичной системе счисления. Все-таки здесь именно 2 десятичные цифры.

[Dendr]

Так на все времени не хватает....

Но нашел немного. Красивое и простое решение.
Ответ - N=101. Меньше - никак.

Если больше ни на кого не снизойдет озарение, выложу свое решение.

[molch64]

to Dendr: ответил в приват)