Фокусник

Логические задачи

Модераторы: Азарапетыч, Администрация

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Сообщение Dendr »

Подсказки могу подкинуть...

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

Аватара пользователя
Atson
Литератор-любитель
Литератор-любитель
Сообщения: 371
Зарегистрирован: 15 апр 2007, 21:02
Пол: Мужской
Откуда: планета K-pax

Сообщение Atson »

А кого ждем?
зайчатки интеллекта

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Сообщение Dendr »

Ну, для второй страницы - уже можно и выложить решение. Скрытым шрифтом, для приличия.
Что происходит, вообще говоря?
Зритель пишет набор из N цифр. Т.е. - N-значное число, вообще говоря, одно из 10^N.
Назовем это первой группой наборов.

Помощник закрывает две соседние цифры кружком, зовет фокусника.

Что видит фокусник? (N-2) цифры, разделенные в каком-то месте на две группы (в т.ч., группа может быть и пустой). Всего - (N-1) вариант.
Итого - фокусник может увидеть (N-1)*10^(N-2) наборов цифр. Назовем это второй группой наборов

И фокусник ставит в соответствие каждому из наборов второй группы какой-то набор из первой группы.
Важно! Не 2-значное число, а именно N-значное.
И однозначное соответствие, обратите внимание. Т.е., каждому набору из второй группы ставится в соответствие один непустой набор из первой. Причем без пересечений. Обратное соотношение (в смысле однозначности) может не соблюдаться - это никак не повлияет на ведение фокуса.

Стало быть, условие: (N-1)*10^(N-2)>=10^N, т.е. N>=10^2+1=101
Для системы счисления с основанием k, соответственно, N>=k^2+1

Ответ - N>=101.
Последний раз редактировалось Dendr 17 май 2007, 12:44, всего редактировалось 1 раз.

Аватара пользователя
Atson
Литератор-любитель
Литератор-любитель
Сообщения: 371
Зарегистрирован: 15 апр 2007, 21:02
Пол: Мужской
Откуда: планета K-pax

Сообщение Atson »

Извините, не понял. Понятно до слов "И он ставит...". Желательно уточнить, что здесь "первая группа" и "вторая".
Хотя и не разобрался, но у меня такое ощущение, что тут показано, что менее 101 цифры недостаточно, а не то, что 101 достаточно. Или нет?
зайчатки интеллекта

Аватара пользователя
Dendr
Акула пера
Акула пера
Сообщения: 5717
Зарегистрирован: 06 май 2005, 15:11
Пол: Мужской
Откуда: Раменское, Мос.обл.
Контактная информация:

Сообщение Dendr »

Поправил насчет определения первой и второй групп.

По второму вопросу... Формально - да. Доказано, что 100 цифр недостаточно, т.е. необходима 101 цифра. Достаточности 101 я просто не успел доказать - molch64 переслал мне pdf с официальным решением, где была указана методика шифрования.

AndrNiko
Графоман со стажем
Графоман со стажем
Сообщения: 517
Зарегистрирован: 16 апр 2005, 09:03
Пол: Мужской
Откуда: Минск

Сообщение AndrNiko »

Идея решения явно перекликается с задачей Снова про мудрецов и колпаки. (А там решение так и не опубликовано!). Только есть один нюанс: нужно брать отдельно цифры на чётных местах и на нечётных. Подробности расписывать не буду - и лень, и неохота портить удовольствие тем, кто ещё хочет подумать. Хорошо бы вообще не публиковать здесь решение. Кто сам не решит - тому и готовое решение читать будет неинтересно.
С уважением Андрей Николаев.
- - -
Нам не дано предугадать, Как слово наше отзовётся... (Ф.Тютчев).

Аватара пользователя
Atson
Литератор-любитель
Литератор-любитель
Сообщения: 371
Зарегистрирован: 15 апр 2007, 21:02
Пол: Мужской
Откуда: планета K-pax

Сообщение Atson »

Нашел я ентот pdf. Очень красивый алгоритм фокуса. Прям не верится, что все так просто и работает. Поскольку Кноп стал у нас появляться, спасибо ему за задачу!
зайчатки интеллекта

Ответить

Вернуться в «Задачки»