3
1

Вася и Петя играют в игру. Вася загадал число с суммой цифр 2012. Петя называет натуральное число $%a$%, Вася говорит ему сумму цифр числа $%|x-a|$%. За какое наименьшее число ходов Петя гарантированно угадает загаданное число?

задан 22 Окт '12 19:24

@dmg3, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(24 Апр '14 22:49) Angry Bird
10|600 символов нужно символов осталось
2

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

Для начала узнаем количество нулей в конце числа (их может быть и 0). Для этого заметим, что при вычитании 1 из нашего числа его сумма цифр уменьшается на 1 и увеличивается на $%9\cdot$%(количество нулей). Теперь вычислим последнюю ненулевую цифру. Для этого будем говорить числа вида $%k\cdot10^s$%, где $%s$% - количество нулей в конце. Сумма цифр будет уменьшаться пока k не превысит значение последней цифры. Теперь вычтем из нашего числа число $%k\cdot10^s$%, где $%k$% - последняя ненулевая цифра и повторим. Таким образом нам понадобится 10 запросов, чтобы избавиться от одной ненулевой цифры, т.е. 20120 запросов по любому хватит.

Что делать с минимальным количеством - пока не очень понятно.

UPD. Кстати, если оценить точнее, то на каждый запрос второго рода мы добавляем 1 к текущей обнаруженной сумме цифр, поэтому на самом деле нам хватит 2012 запросов.

ссылка

отвечен 1 Ноя '12 19:03

изменен 6 Ноя '12 21:10

(1 Ноя '12 19:08) freopen

Да, идея хорошая! К сожалению, от автора вопроса ответа, наверное, не дождемся, @aapetrov3 ушел в непонятки!

(2 Ноя '12 1:20) DocentI
10|600 символов нужно символов осталось
2

Не умею писать здесь формулы, поэтому объясняюсь в основном словами, опуская лекговосстанавливаемые подробности. Развиваю идею @freopen.

а) Минимально необходимое число вопросов - 2012.
Назовем "правой группой" набор из ненулевой первой цифры с последующими нулями (число таких нулей в группе - ноль или больше). Любое задуманнное Васей число состоит не более чем из 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...*
Для s1=7 все ясно: x=2
Для s1=2 вопрос a2=90 даёт варианты ответов s2= 16, 7, 2, 11, 20, 29...
соответвующие x=11, 20, 110, 1010, 10010, 100010...
Для s1=11 вопрос a2=900 даёт варианты ответов s2= 25, 7, 2, 11, 20, 29...
соответвующие x=101, 200, 1100, 10100, 100100, 1000100...
Для s1=20 вопрос a2=9000 даёт варианты ответов s2= 34, 7, 2, 11, 20, 29...
соответвующие x=1001,2000,11000,101000,1001000,10001000...

Дальнейшее для N=2 понятно, дальше должна вроде бы работать индукция. Для N=3 тоже проверял непосредственно, если не наврал нигде, то тоже все проходит

ссылка

отвечен 4 Ноя '12 15:19

изменен 4 Ноя '12 17:09

@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

@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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×590
×76
×54

задан
22 Окт '12 19:24

показан
1404 раза

обновлен
24 Апр '14 22:49

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru