Маша

[Илья]

Дальше, если перебор, я называю число кратное пяти и лежащее в середине полуинтервала, то есть 1325 ( 25*53), НОД у возможных кандидатов будет одинаковый - это 5 ( 5, 10, 15, 20, 35, 40, 45, 50), если недобор, то 75, то есть75*53=3975, так же будет иметь НОД 5 с какдидатами (55, 60, 65, 70, 75, 80, 85, 90, 95, 100). Сократили интервал еще в два раза.
Не, кандидатов побольше будет.

[buka]

Дальше, если перебор, я называю число кратное пяти и лежащее в середине полуинтервала, то есть 1325 ( 25*53), НОД у возможных кандидатов будет одинаковый - это 5 ( 5, 15, 35, 45), если недобор, то 75, то есть75*53=3975, так же будет иметь НОД 5 с какдидатами (55, 65, 85, 95). Сократили интервал еще в два раза.
Не, кандидатов побольше будет.

Ваше замечание справедливое, но из подобного свойства можно выжать больше.
Чтобы ощутить всю прелесть этого свойства и тот эффект, который можно от него получить, предлагаю на время вернуться к исходной задаче, а именно:
Маша задумала целое число от 1 до 100. Алёша может называть любые натуральные числа. Если число, названное Алёшей, совпадает с тем, о котором думает Маша, считается, что Алёша победил, и Маша ему об этом сообщает. В противном случае Маша молча меняет своё число. Она делит его на Алёшино, если деление нацело возможно, иначе умножает своё число на Алёшино и прибавляет 1. Сможет ли Алёша победить?
То есть - абсолютно исходная задача, один к одному.
Мы выяснили, что Алёша может победить. Причём затратит на это число попыток не бОльшее, чем если бы Маша не меняла бы число...
Но оказывается, что Алёша может ГАРАНТИРОВАННО победить, с числом попыток ЗНАЧИТЕЛЬНО МЕНЬШИМ 100!!!
Когда я вчера к этому пришёл, я просто оторопел, а когда оценил НАСКОЛЬКО меньше, был просто шокирован!
После этого я задумался, а можно ли гарантированно победить в модифицированной задаче (т.е. с НОД и "Перебор/Недобор/Угадал") меньше чем за 7 попыток...

[Илья]

ГАРАНТИРОВАННО победить, с числом попыток ЗНАЧИТЕЛЬНО МЕНЬШИМ 100!!!

У нас же нет ни какой инфы в исходной задаче.

[buka]

ГАРАНТИРОВАННО победить, с числом попыток ЗНАЧИТЕЛЬНО МЕНЬШИМ 100!!!

У нас же нет ни какой инфы в исходной задаче.

Тем не менее
Когда я до этого допёр, я был шокирован!
Конечно, речь не идёт, чтобы победить в 7 попыток, но победить в ~70 попыток и гарантированно - можно! А 70 вместо 100 - разве это не достижение!
Ведь если бы Маша не меняла бы числа, то Алёше требовалось бы 100 попыток для гарантированной победы, и уменьшить это число на ~30 - это имхо не слабо!

[buka]

Илья, я Вас не заинтриговал?

[Илья]

Илья, я Вас не заинтриговал?

Заинтриговали, но вот после второй попытки я пока не знаю как дальше действовать, ведь я могу сказать число одно, а оно окажется меньше, если разделилось, то есть 100% уверенности у меня уже нет. Пока не знаю как с этим быть. Наверное, что-то связанное с делителями...

[buka]

Илья, я Вас не заинтриговал?

Заинтриговали, но вот после второй попытки я пока не знаю как дальше действовать, ведь я могу сказать число одно, а оно окажется меньше, если разделилось, то есть 100% уверенности у меня уже нет. Пока не знаю как с этим быть. Наверное, что-то связанное с делителями...

Давайте сначала рассмотрим исходную задачу, т.е. когда Маша отвечает только "Угадал" или молча делит своё число на Алёшино (если деление нацело) или умножает на Алешино и прибавляет 1 в противном случае.
Если Алёша называет 2, то:
1. Если угадал - то ОК.
Иначе:
2. Если Маша задумала 1, то 1 превратится в 3 (1*2 + 1).
Но если Маша задумала 6, то 6 тоже превратится в 3.
Если продолжить эти рассуждения, то получим:
3 и 14 -> 7, 5 и 22 -> 11, 7 и 30 -> 15, ..., 21 и 86 -> 43, 23 и 94 -> 47
Остальные чётные разделились на 2, а остальные нечотные удвоились и к ним прибавилась 1-ца.
Итак, общее число кандидатов после 1-го названного числа (2) уменьшилось на 13 - мы можем исключить 2-ку и одно из чисел из каждой из 12-ти "сжатых" пар.
3. Теперь мы можем выбрать 2-е число для угадывания:
это либо опять 2 (т.е. первоначально Маша задумала 4), либо 3 (т.е. первоначально Маша задумывала 1 или 6). Оба варианта почти равноценны и дают
сжатие ~6
Ну, и так далее
3. Теперь мы можем выбрать 2-е число для угадывания:
это либо опять 2 (т.е. первоначально Маша задумала 4), либо 3 (т.е. первоначально Маша задумывала 1 или 6). Оба варианта почти равноценны и дают
сжатие ~6
Ну, и так далее  
С каждым шагом степень сжатия уменьшается, но где-то ~25 попыток мы можем сэкономить
----------------------------------------------------------------------
Задавайте вопросы, сомнения и т.д.
А потом мы вернёмся к задаче с НОД и "Угадал/Недобрал/Перебрал"   

[Илья]

3

и 14 -> 7, 5 и 22 -> 11, 7 и 30 -> 15, ..., 21 и 86 -> 43, 23 и 94 -> 47
Остальные чётные разделились на 2, а остальные нечотные удвоились и к ним прибавилась 1-ца.

Задача оказалась даже интереснее, чем я думал.
Я подошел к ней довольно поверхностно.

[Илья]

Так, если решать данную задачку с последним условием / перебрал, недобрал, угадал/, то например первая попытка с числом 50, дает нам: 15 - 3, 75 - 3, 30-3
100/50=2, 20/10=2, 5/5=1, 10/10=1, 25/25=1 и т. д.
Просто класс.
Посмотрим у какого числа 1-100 больше всех делителей.

[Илья]

Если первое число 30, то: 1 1 1 2 1 1  210 4 3 1.....
А 60 оптимальнее будет:
1, 1, 1, 1, 1, 1, 420, 2, 3, 1, 660, 1, 780, 7, 1, 4, 1020, 3, 1140,1, 7, 11, 1380, 2, 5, 13, 9,7, 3120,....

[buka]

Если Вы вкусили всю прелесть исходной задачи (без "Недобор/Перебор"), то перейдём к модифицированной, т.е. "Угадал/Перебор/Недобор".
Сразу замечу, что благодаря "Перебор/Недобор" мы всегда можем угадать Машино число за 7 шагов (при начальном интервале 1 - 100).
Всю эту катавасию с делителями имеет смысл заваривать, если в результате мы сможем уменьшить число попыток хотя бы на шаг.
А просто так уменьшать кандидатов на 10, 20 и даже 30 смысла не имеет, ведь если мы даже сумеем убить 30 чисел интервал в 70 чисел опять таки требует тех же 7-ми шагов...
Лично я пессимистичен в том, что для 100 исходных чисел мы сможем "украсть" один шаг. Слишком уж велико 100 относительно 63...
А вот попытаться угадать число в начальном интервале 1 - ~80 имеет смысл пытаться.
Несколько общих замечаний.
1. Да, если заваривать катавасию, то лучше всего выбрать число (я назову его селектор) с большим числом делителей.
2. Нижний полуинтервал лучше сжимается, чем верхний. Поэтому надо выбирать селектор не на середине а где-то в отношении 3:2 или даже 2:1 (надо исследовать глубже, 2:1 видится мне слишком уж агрессивным)
3. Следует учитывать, что сжатие имеет смысл учитывать только для худшего полуинтервала.
4. Если начальный интервал 1 - ~80, то вряд ли на первом шагу можно "вложиться" в два полуинтервала, чтобы бОльший из них был < 32. Но сжатие может быть продолжено и на следующих шагах. Но надо учесть, что с каждым шагом число "убитых" кандидатов уменьшается.
5. Выбор селектора на 2-м и следующем шагах - тоже искусство. Ведь порядок трансформированных чисел отличается от исходного.
Надо пересчитать трансформанты для каждого числа и просортировать их отдельно по каждому полуинтервалу.
Но ведь сам процесс исследования интересен, не правда?

[Илья]

Ну первое число я уже предложил - это 60, там в результате деления получается куча единиц и второй вариант, будет 1, если конечно Маша скажет "перебор", а вот если скажет "недобор", то останется всего 40 кандидатов и там уже надо подумать какое следующее число предлагать.

[Илья]

Занимаюсь проверкой возможных селекторов - удачное название.

[buka]

Ну первое число я уже предложил - это 60, там в результате деления получается куча единиц и второй вариант, будет 1, если конечно Маша скажет "перебор", а вот если скажет "недобор", то останется всего 40 кандидатов и там уже надо подумать какое следующее число предлагать.

Вы всё-таки хотите покорить 100 за 6 шагов?
40 вариантов в верхнем интервале это плохо.
Там ничего не сжимается и 40 требует 6 шагов, вынь и положь. Плюс 1-й шаг - итого 7...
Чтобы верхний интервал взять за 5 шагов, там должно остаться 31 кандидат...
А если уменьшить интервал?
Скажем, до 95? Тогда можно посмотреть 64 как селектор. Он сократит все чётные.
А остальные станут чётными, вернее, кратными 64.
Короче, может 95 падёт

[buka]

Я проанализировал 60 в качестве селектора.
Очень хороший селектор. Может и 100 свалит...
В верхнем полуинтервале тоже можно сжать на 6-7
Если на 2-м шаге можно будет сжать ещё на 1, думаю, 100 падёт.