|
Вася и Петя играют в игру. Вася загадал число с суммой цифр 2012. Петя называет натуральное число $%a$%, Вася говорит ему сумму цифр числа $%|x-a|$%. За какое наименьшее число ходов Петя гарантированно угадает загаданное число? задан 22 Окт '12 19:24 
dmg3 |
|
На самом деле можно различить, т.к. число ответов на вопрос тоже бесконечно и оно нам может давать потенциально произвольное количество информации. Попробуем воспользоваться этим с умом. Для начала узнаем количество нулей в конце числа (их может быть и 0). Для этого заметим, что при вычитании 1 из нашего числа его сумма цифр уменьшается на 1 и увеличивается на $%9\cdot$%(количество нулей). Теперь вычислим последнюю ненулевую цифру. Для этого будем говорить числа вида $%k\cdot10^s$%, где $%s$% - количество нулей в конце. Сумма цифр будет уменьшаться пока k не превысит значение последней цифры. Теперь вычтем из нашего числа число $%k\cdot10^s$%, где $%k$% - последняя ненулевая цифра и повторим. Таким образом нам понадобится 10 запросов, чтобы избавиться от одной ненулевой цифры, т.е. 20120 запросов по любому хватит. Что делать с минимальным количеством - пока не очень понятно. UPD. Кстати, если оценить точнее, то на каждый запрос второго рода мы добавляем 1 к текущей обнаруженной сумме цифр, поэтому на самом деле нам хватит 2012 запросов. отвечен 1 Ноя '12 19:03 
freopen
(1 Ноя '12 19:08)
freopen
Да, идея хорошая! К сожалению, от автора вопроса ответа, наверное, не дождемся, @aapetrov3 ушел в непонятки!
(2 Ноя '12 1:20)
DocentI
|
|
Не умею писать здесь формулы, поэтому объясняюсь в основном словами, опуская лекговосстанавливаемые подробности. Развиваю идею @freopen. а) Минимально необходимое число вопросов - 2012. Пусть $%a1, a2(s1), a3(s2)...$% - "оптимальная" последовательность петиных вопросов, s1, s2, s3... - васины ответы на $%a1, a2, a3...; М1, М2, М3$% - число цифр в $%a1,a2,a3...$%
Тогда если Вася задумал число $%G_n....G_2G_1$%, состоящее из 2012 правых групп вида $%10^{Mi} = 10...0$% - т.е. 1 с Mi нулей, то за один петин вопрос дается информация, касающаяся только одной правой группы. помимо тех, о которых информация была получена на предыдущих вопросах. Следовательно потребуется не менее 2012 вопросов, чтобы получить информацию о 2012 правых группах. б) нестрого! Видимо, 2012 вопросов достаточно. Петя должен задавать вопросы вида $%9, 9\cdot 10^{K1},...,9\cdot 10^{Ki},...$%. Где Кi - позиция i-той ненулевой цифры задуманного числа, считая от конца десятичной записи. Значение Кi однозначно устанавливается по ответу на (i-1)-й вопрос, а само значние этой цифры - по ответу на i-ый. Таким образом после i-того вопроса становится известна как минимум i-тая правая группа задуманного числа. Число таких групп не более 2012. По пункту б) имею пока только проект доказательства (сложность в части доказательства гарантированного установления конретной "лидирующей" цифры правой группы на i-том вопросе и однознчности "перехода через ноль"). Объясняю идею на пальцах. Если заменить N=2012 на N=2, то двух вопросов достаточно. Первый вопрос - 9, варианты ответов - s1 = 2, 7, 11, 20, 29, 38, 45...* Дальнейшее для N=2 понятно, дальше должна вроде бы работать индукция. Для N=3 тоже проверял непосредственно, если не наврал нигде, то тоже все проходит отвечен 4 Ноя '12 15:19 
behemothus @behemothus, здесь редактор формул по типу LaTex. Готовую формулу заключаем в "скобки" - либо двойные доллары (вынесенная формула), либо доллар+процент - формула в тексте.
(4 Ноя '12 16:46)
DocentI
Я не знаю, что такое LaTex. Если разберусь документациии, постараюсь освоить. Спасибо.
(4 Ноя '12 17:08)
behemothus
Для простых формул это не обязательно. Подчеркивание, _ - нижний индекс, "галочка", ^ - верхний. Если действие относится к группе знаков, берем их в фигурные скобки. Зарезервированные слова выделяются бакслешем, \
(4 Ноя '12 17:12)
DocentI
Можете пояснить, почему за один вопрос мы получаем информацию только об одной группе? Неочевидно.
(5 Ноя '12 13:53)
freopen
Десятичная длина "группы" больше длины вопроса. $%(nnnnnnnN00000000000zzzzzzzz - xxxxxxxx)_1o = (nnnnnnnn(N-1)999999yyyyyyyyyyy)_1o$% О цифрах $%(nnnnnnnn)_1о$% мы никакой информации не получим. Нет, этот редактор выше моего понимания. Я хотел сделать 10 в нижнем индексе - т.е. десятичнгая запись. Но вообще-то это все из вашей-же идеи и следует. Вся информация о том, что стоит перед ненулевой цифрой, которую вы на i-том шаге тестируете скрыта. Я только предположил, что не надо вычитать 10 раз по единице, достаточно одной 9.
(6 Ноя '12 5:30)
behemothus
(6 Ноя '12 11:56)
Андрей Юрьевич
@behemothus, Поставьте 10 в фигурные скобки.
(6 Ноя '12 12:41)
DocentI
Пробовал, не получается: $%nnnnnnnN00000000000zzzzzzzz _ {10} − xxxxxxxx _ {10} = (nnnnnnnn(N−1)999999yyyyyyyyyyy) _ {10}$% Только один раз на формулу: $%(nnnnnnnn)_{10}$% Андрей Юрьевич, спасибо, мне ссылку давали, только мне бы еще ссылку на новые мозги кто дал. )))
(6 Ноя '12 17:02)
behemothus
1
Все равно непонятно. Что мои вопросы не дают больше информации -- это понятно, но почему бы не задать другие, которые могут дать нам информацию сразу о нескольких группах?
(6 Ноя '12 21:00)
freopen
Пункт б тоже нифига не понял. Возьмем числа 21 и 12. Сделаем два запроса, на первом оба числа вернут 3, значит, второй запрос будет 9? или 90? Хотя это неважно, все равно в первом случае ответ будет 3 у обоих, во втором 15. Ну и как узнать последнюю цифру???
(6 Ноя '12 21:08)
freopen
@behemothus, извините, я хотела посмотреть Ваше оформление, и превратила комментарий в ответ. А обратно вернуть не могу. Верните, пожалуйста, сами, или удалите. Помнится, в РЯ Вы исправляли мой комментарий, на удивление и мне и моей собеседнице (про падежи). Как Вы это сделали? Я не умею...
(6 Ноя '12 22:39)
DocentI
Действительно, нижние индексы иногда барахлят, (особенно у тех, кто пользуется редактором?), например, у Anatoliy. Дело в том, что подчеркивание еще является знаком курсива (между двумя соседними подчеркиваниями шрифт меняется), так что возникает конфликт пониманий. Я вроде заметила, что подчеркивание нельзя ставить после фигурной скобки. Но у Вас была обычная! После ее удаления все наладилось. Что самое плохое, в процессе ввода на контрольном экране картинка бывает нормальной!
(6 Ноя '12 22:42)
DocentI
Вы наперед не знаете длины группы. Предположим на i-том шаге вы собираетесь "спросить" число длины k. Тогда, если задумано число у которого k-ая (считая с конца) группа начинается с (i+1)-й десятичной позиции (тоже считая с конца), то информации о цифрах, чтоящих перед этой группой вы не получите. Насчет пункта б) - пока не комментирую. при 12 и 21 0- принимается, там видимо, надо отдельно разбираться с последней цифрой, когда "перелезаем" через 0. Но все это пока в порядке обсуждения было. Разберусь с редактором - объяснюсь.
(7 Ноя '12 1:37)
behemothus
Да, похоже на правду. По поводу пункта б -- я его решил и описал в своем ответе уже давно.
(15 Ноя '12 17:49)
freopen
показано 5 из 14
показать еще 9
|
@dmg3, Если вы получили исчерпывающий ответ, отметьте его как принятый.