Название: Маша Отправлено: sek140675 от Апрель 23, 2010, 19:04:59 Маша задумала целое число от 1 до 100. Алёша может называть любые натуральные числа. Если число, названное Алёшей, совпадает с тем, о котором думает Маша, считается, что Алёша победил, и Маша ему об этом сообщает. В противном случае Маша молча меняет своё число. Она делит его на Алёшино, если деление нацело возможно, иначе умножает своё число на Алёшино и прибавляет 1. Сможет ли Алёша победить?
Название: Re: Маша Отправлено: House Fox от Апрель 23, 2010, 19:16:42 Маша задумала целое число от 1 до 100. Алёша может называть любые натуральные числа. Если число, названное Алёшей, совпадает с тем, о котором думает Маша, считается, что Алёша победил, и Маша ему об этом сообщает. В противном случае Маша молча меняет своё число. Она делит его на Алёшино, если деление нацело возможно, иначе умножает своё число на Алёшино и прибавляет 1. Сможет ли Алёша победить? Ну сможет, если угадает :D Или я что-то не понял? Название: Re: Маша Отправлено: sek140675 от Апрель 23, 2010, 19:35:20 ну если угадает - с этим ясно
а вот сможет он целенаправленно подойти к ответу Название: Re: Маша Отправлено: buka от Апрель 23, 2010, 20:08:18 Красивая задача! Спасибо! :bravo2: :bravo: :good3:
Показать скрытый текст Название: Re: Маша Отправлено: sek140675 от Апрель 23, 2010, 20:13:16 :beer:
чуть позже проверим в действии?? Название: Re: Маша Отправлено: buka от Апрель 23, 2010, 20:43:11 :beer: Я вообще-то могу доказать :)чуть позже проверим в действии?? Кстати, под впечатлением этой задачи у меня родилась другая :) Название: Re: Маша Отправлено: sek140675 от Апрель 23, 2010, 20:44:04 выкладывайте :)
Название: Re: Маша Отправлено: firemen от Апрель 23, 2010, 21:12:28 а что, если у Маши при умножении число выходит более 100 ?
Название: Re: Маша Отправлено: buka от Апрель 23, 2010, 21:32:58 выкладывайте :) Давайте сначала "распpавимся" с исходной задачей.Просто если я выложу новую, это может подсказать кое-что для исходной :) Название: Re: Маша Отправлено: Илья от Апрель 24, 2010, 07:46:35 Цитировать а вот сможет он целенаправленно подойти к ответу Сможет. Задача и вправду хороша :good2:Спасибо! Последовательность чисел Алеши: 1, 3, 13, 209, 8361... и т. д. Название: Re: Маша Отправлено: buka от Апрель 24, 2010, 13:59:46 Цитировать а вот сможет он целенаправленно подойти к ответу Сможет. Задача и вправду хороша :good2:Спасибо! Последовательность чисел Алеши: 1, 3, 13, 209, 8361... и т. д. 1,2,7,15,1171,... - имхо проще... Название: Re: Маша Отправлено: Илья от Апрель 24, 2010, 14:05:15 Цитировать Вы решили 2-ку потом проверить? В принципе можно, но зачем? Да это у меня двойка на 1 не разделилась, я ее и пропустил. :DНазвание: Re: Маша Отправлено: Илья от Апрель 24, 2010, 14:27:49 Цитировать Кстати, под впечатлением этой задачи у меня родилась другая Так как на счет другой? Название: Re: Маша Отправлено: sek140675 от Апрель 24, 2010, 14:33:39 а проверить
я задумал число а ваши действия Название: Re: Маша Отправлено: Илья от Апрель 24, 2010, 14:35:11 а проверить Окей, поехали, давай только в играх, чтоб тему не заполонять.я задумал число а ваши действия Название: Re: Маша Отправлено: sek140675 от Апрель 24, 2010, 14:36:10 ты ж начальник :beer:
Название: Re: Маша Отправлено: Илья от Апрель 24, 2010, 14:36:39 ты ж начальник :beer: Создал тему.Название: Re: Маша Отправлено: buka от Апрель 24, 2010, 17:20:48 Цитировать Кстати, под впечатлением этой задачи у меня родилась другая Так как на счет другой? Допустим, что задача почти та же, но Маша вместо ответа "угадал" даёт один из 3-х ответов - "угадал" (если угадал), "перебрал" (если назвал число большее, чем у Маши на тот момент) или "недобрал" (если назвал число меньшее, чем у Маши на тот момент). Ясно, что теперь Алёша может угадать за меньшее число попыток. Какова должна быть стратегия Алёши, чтобы он гарантированно получил ответ "угадал" за минимальное число попыток. Предлагается также оценить это число. Название: Re: Маша Отправлено: Илья от Апрель 25, 2010, 21:36:42 А операции она все те же проводит?
Название: Re: Маша Отправлено: Илья от Апрель 25, 2010, 21:44:07 Ну первая попытка будет: 50, дальше по аналогии в зависимости, если не добрал, то 3751, если перебрал, то
1876 Название: Re: Маша Отправлено: buka от Апрель 25, 2010, 23:24:37 А операции она все те же проводит? Да, конечноНазвание: Re: Маша Отправлено: buka от Апрель 25, 2010, 23:29:05 Ну первая попытка будет: 50, дальше по аналогии в зависимости, если перебрал, то 3751, если не добрал, то И сколько будет попыток?1876 У меня бы 1-я попытка отличалась бы от 50... Название: Re: Маша Отправлено: Илья от Апрель 26, 2010, 01:14:38 Цитировать И сколько будет попыток? Где-то около семи.Название: Re: Маша Отправлено: buka от Апрель 26, 2010, 02:06:13 Цитировать И сколько будет попыток? Где-то около семи.Название: Re: Маша Отправлено: Илья от Апрель 26, 2010, 13:09:06 Цитировать Если Вы начнёте с 50, то может оказаться больше... Проверим? :)Название: Re: Маша Отправлено: buka от Апрель 26, 2010, 15:40:27 Цитировать Если Вы начнёте с 50, то может оказаться больше... Проверим? :)Вы - 50. Маша - Недобор. (Т.е. Маша задумала бОльшее число) Вы - 3751 Маша - Перебор (Т.е. у Маши на этот момент число - меньше). Ваш ход. Название: Re: Маша Отправлено: Илья от Апрель 26, 2010, 15:58:02 11 631 852
Название: Re: Маша Отправлено: buka от Апрель 26, 2010, 16:37:22 11 631 852 ПереборНазвание: Re: Маша Отправлено: buka от Апрель 26, 2010, 19:36:40 Илья, мы оба взрослых. Стратегия ясна обоим, не так ли?
Вы выбрали число примерно в середине интервала. Получили ответ "Недобор" и сделали вывод, что Маша задумала число в верхнем полунитервале. После этого, Вы выбрали примерно середину этого полуинтервала, пересчитали, какое у Маши получилось бы число, если бы она задумала бы именно это и назвали его (в данном случае 3751 = 50*75+1). Получили ответ: "Перебор". Мой вопрос следующий: всегда ли это значит, что задуманное вначале Машей число должно лежать в нижнем четвертьинтервале (в данном случае 50 < М < 75) при таких ответах Маши (50 - недобор, 3751 - перебор)? Какое дополнительное условие должно быть возложено на границы Г1, Г2 и т.д., чтобы действитеьно соблюдалось Гк < М < Гл ? Название: Re: Маша Отправлено: Илья от Апрель 26, 2010, 20:14:00 122210657894305
Название: Re: Маша Отправлено: Илья от Апрель 26, 2010, 20:29:20 Цитировать Какое дополнительное условие должно быть возложено на границы Г1, Г2 и т.д., Не должно делиться на число Алеши ???чтобы действитеьно соблюдалось Гк < М < Гл ? Название: Re: Маша Отправлено: buka от Апрель 26, 2010, 21:30:05 Цитировать Какое дополнительное условие должно быть возложено на границы Г1, Г2 и т.д., Не должно делиться на число Алеши ???чтобы действитеьно соблюдалось Гк < М < Гл ? Название: Re: Маша Отправлено: Илья от Апрель 26, 2010, 22:06:00 Ну тогда первой 51 :)
Название: Re: Маша Отправлено: buka от Апрель 26, 2010, 22:16:07 Ну тогда первой 51 :) Да.В принципе и 52 и 53 аж до 63 не увеличат кол-во попыток в худшем случае - 100 < 127 :) Кстати, у меня есть ещё один вариант усложнения условия. Вам это интересно? Название: Re: Маша Отправлено: Илья от Апрель 26, 2010, 22:26:52 Да-да, конечно интересно.
Название: Re: Маша Отправлено: buka от Апрель 26, 2010, 22:53:23 Да-да, конечно интересно. Теперь я изменяю условие в части действий Маши.Она по-прежнему задумала число от 1 до 100 включительно и отвечает "Угадал/Недобор/Перебор", но, после ответа делает следующее: Если Машино текущее число имеет с предложенным Алёшей общий делитель отличный от 1, она делит своё число на наибольший общий делитель. Иначе - умножает своё число на Алёшино (но не прибавляет ещё единицу, как раньше). Какова наилучшая стратегия Алёши? Название: Re: Маша Отправлено: Илья от Апрель 27, 2010, 07:26:43 Ну, первая попытка у меня будет такая же: 51
Название: Re: Маша Отправлено: buka от Апрель 27, 2010, 15:56:42 Ну, первая попытка у меня будет такая же: 51 Сколько попыток Вам потребуется для гарантированного ответа (включая ответ)?И если можно, расскажите стратегию (в общих словах). Название: Re: Маша Отправлено: buka от Апрель 27, 2010, 21:06:33 Илья, Вам ещё интересно?
Название: Re: Маша Отправлено: sek140675 от Апрель 27, 2010, 21:07:07 Маша задумала целое число от 1 до 100. Алёша может называть любые натуральные числа. Если число, названное Алёшей, совпадает с тем, о котором думает Маша, считается, что Алёша победил, и Маша ему об этом сообщает. В противном случае Маша молча меняет своё число. Она делит его на Алёшино, если деление нацело возможно, иначе умножает своё число на Алёшино и прибавляет 1. Сможет ли Алёша победить? если проще числа с 1-10 быстрее и наглядее Название: Re: Маша Отправлено: buka от Апрель 27, 2010, 21:46:54 Маша задумала целое число от 1 до 100. Алёша может называть любые натуральные числа. Если число, названное Алёшей, совпадает с тем, о котором думает Маша, считается, что Алёша победил, и Маша ему об этом сообщает. В противном случае Маша молча меняет своё число. Она делит его на Алёшино, если деление нацело возможно, иначе умножает своё число на Алёшино и прибавляет 1. Сможет ли Алёша победить? если проще числа с 1-10 быстрее и наглядее С другой стороны - ведь речь не идёт о вычислениях. Речь идёт о стратегии... Название: Re: Маша Отправлено: Илья от Апрель 27, 2010, 22:15:41 Илья, Вам ещё интересно? Да, интересно. Но сегодня я уже спать. Оставим эту задачку до завтра.Кстати, я поторопился, первая попытка будет 53. Название: Re: Маша Отправлено: buka от Апрель 28, 2010, 00:11:43 Илья, Вам ещё интересно? Да, интересно. Но сегодня я уже спать. Оставим эту задачку до завтра.Кстати, я поторопился, первая попытка будет 53. А утром для Вас на закуску: Итак, я понял, что Вы выбрали ближайшее к середине простое число, бОльшее половины максимального. Это хорошо. Но рано или поздно придётся столкнуться с ситуацией, когда в интервале либо вообще уже нет простых чисел, либо они ближе к краю, чем к середине... Что Вы предпримете в этом случае? Название: Re: Маша Отправлено: Илья от Апрель 28, 2010, 06:58:04 Более того простые числа уже не "помогут" после первого хода, так как при умножении на простое число простого - простое число уже не получится и уже будет какой-то общий делитель скорее всего. Подумаем.
Название: Re: Маша Отправлено: buka от Апрель 28, 2010, 07:20:40 Более того простые числа уже не "помогут" после первого хода, так как при умножении на простое число простого - простое число уже не получится и уже будет какой-то общий делитель скорее всего. Подумаем. Илья, если я Вам скажу, что составные числа тоже хороши и даже могут быть лучше простых, Вы мне поверите?Название: Re: Маша Отправлено: Илья от Апрель 28, 2010, 07:30:25 Дальше, если перебор, я называю число кратное пяти и лежащее в середине полуинтервала, то есть 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). Сократили интервал еще в два раза. :)
Не, кандидатов побольше будет. :) Название: Re: Маша Отправлено: buka от Апрель 28, 2010, 07:59:54 Дальше, если перебор, я называю число кратное пяти и лежащее в середине полуинтервала, то есть 1325 ( 25*53), НОД у возможных кандидатов будет одинаковый - это 5 ( 5, 15, 35, 45), если недобор, то 75, то есть75*53=3975, так же будет иметь НОД 5 с какдидатами (55, 65, 85, 95). Сократили интервал еще в два раза. :) Ваше замечание справедливое, но из подобного свойства можно выжать больше.Не, кандидатов побольше будет. :) Чтобы ощутить всю прелесть этого свойства и тот эффект, который можно от него получить, предлагаю на время вернуться к исходной задаче, а именно: Маша задумала целое число от 1 до 100. Алёша может называть любые натуральные числа. Если число, названное Алёшей, совпадает с тем, о котором думает Маша, считается, что Алёша победил, и Маша ему об этом сообщает. В противном случае Маша молча меняет своё число. Она делит его на Алёшино, если деление нацело возможно, иначе умножает своё число на Алёшино и прибавляет 1. Сможет ли Алёша победить? То есть - абсолютно исходная задача, один к одному. Мы выяснили, что Алёша может победить. Причём затратит на это число попыток не бОльшее, чем если бы Маша не меняла бы число... Но оказывается, что Алёша может ГАРАНТИРОВАННО победить, с числом попыток ЗНАЧИТЕЛЬНО МЕНЬШИМ 100!!! Когда я вчера к этому пришёл, я просто оторопел, а когда оценил НАСКОЛЬКО меньше, был просто шокирован! После этого я задумался, а можно ли гарантированно победить в модифицированной задаче (т.е. с НОД и "Перебор/Недобор/Угадал") меньше чем за 7 попыток... Название: Re: Маша Отправлено: Илья от Апрель 28, 2010, 08:03:31 Цитировать ГАРАНТИРОВАННО победить, с числом попыток ЗНАЧИТЕЛЬНО МЕНЬШИМ 100!!! :oУ нас же нет ни какой инфы в исходной задаче. Название: Re: Маша Отправлено: buka от Апрель 28, 2010, 08:20:31 Цитировать ГАРАНТИРОВАННО победить, с числом попыток ЗНАЧИТЕЛЬНО МЕНЬШИМ 100!!! :oУ нас же нет ни какой инфы в исходной задаче. Когда я до этого допёр, я был шокирован! Конечно, речь не идёт, чтобы победить в 7 попыток, но победить в ~70 попыток и гарантированно - можно! А 70 вместо 100 - разве это не достижение! Ведь если бы Маша не меняла бы числа, то Алёше требовалось бы 100 попыток для гарантированной победы, и уменьшить это число на ~30 - это имхо не слабо! Название: Re: Маша Отправлено: buka от Апрель 28, 2010, 14:20:31 Илья, я Вас не заинтриговал? :)
Название: Re: Маша Отправлено: Илья от Апрель 28, 2010, 14:25:44 Илья, я Вас не заинтриговал? :) Заинтриговали, но вот после второй попытки я пока не знаю как дальше действовать, ведь я могу сказать число одно, а оно окажется меньше, если разделилось, то есть 100% уверенности у меня уже нет. Пока не знаю как с этим быть. ??? Наверное, что-то связанное с делителями...Название: Re: Маша Отправлено: buka от Апрель 28, 2010, 16:03:25 Илья, я Вас не заинтриговал? :) Заинтриговали, но вот после второй попытки я пока не знаю как дальше действовать, ведь я могу сказать число одно, а оно окажется меньше, если разделилось, то есть 100% уверенности у меня уже нет. Пока не знаю как с этим быть. ??? Наверное, что-то связанное с делителями...Если Алёша называет 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 попыток мы можем сэкономить :) ---------------------------------------------------------------------- Задавайте вопросы, сомнения и т.д. А потом мы вернёмся к задаче с НОД и "Угадал/Недобрал/Перебрал" :cool4: Название: Re: Маша Отправлено: Илья от Апрель 28, 2010, 16:13:48 3
Цитировать и 14 -> 7, 5 и 22 -> 11, 7 и 30 -> 15, ..., 21 и 86 -> 43, 23 и 94 -> 47 Задача оказалась даже интереснее, чем я думал. :good2:Остальные чётные разделились на 2, а остальные нечотные удвоились и к ним прибавилась 1-ца. Я подошел к ней довольно поверхностно. Название: Re: Маша Отправлено: Илья от Апрель 28, 2010, 16:36:20 Так, если решать данную задачку с последним условием / перебрал, недобрал, угадал/, то например первая попытка с числом 50, дает нам: 15 - 3, 75 - 3, 30-3
100/50=2, 20/10=2, 5/5=1, 10/10=1, 25/25=1 и т. д. Просто класс. :) Посмотрим у какого числа 1-100 больше всех делителей. :) Название: Re: Маша Отправлено: Илья от Апрель 28, 2010, 16:53:00 Если первое число 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,.... :) Название: Re: Маша Отправлено: buka от Апрель 28, 2010, 21:36:03 Если Вы вкусили всю прелесть исходной задачи (без "Недобор/Перебор"), то перейдём к модифицированной, т.е. "Угадал/Перебор/Недобор".
Сразу замечу, что благодаря "Перебор/Недобор" мы всегда можем угадать Машино число за 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-м и следующем шагах - тоже искусство. Ведь порядок трансформированных чисел отличается от исходного. Надо пересчитать трансформанты для каждого числа и просортировать их отдельно по каждому полуинтервалу. Но ведь сам процесс исследования интересен, не правда? Название: Re: Маша Отправлено: Илья от Апрель 28, 2010, 21:55:28 Ну первое число я уже предложил - это 60, там в результате деления получается куча единиц и второй вариант, будет 1, если конечно Маша скажет "перебор", а вот если скажет "недобор", то останется всего 40 кандидатов и там уже надо подумать какое следующее число предлагать.
Название: Re: Маша Отправлено: Илья от Апрель 28, 2010, 22:17:16 Занимаюсь проверкой возможных селекторов - удачное название. :)
Название: Re: Маша Отправлено: buka от Апрель 28, 2010, 22:34:07 Ну первое число я уже предложил - это 60, там в результате деления получается куча единиц и второй вариант, будет 1, если конечно Маша скажет "перебор", а вот если скажет "недобор", то останется всего 40 кандидатов и там уже надо подумать какое следующее число предлагать. Вы всё-таки хотите покорить 100 за 6 шагов?40 вариантов в верхнем интервале это плохо. Там ничего не сжимается и 40 требует 6 шагов, вынь и положь. Плюс 1-й шаг - итого 7... :( Чтобы верхний интервал взять за 5 шагов, там должно остаться 31 кандидат... А если уменьшить интервал? Скажем, до 95? Тогда можно посмотреть 64 как селектор. Он сократит все чётные. А остальные станут чётными, вернее, кратными 64. Короче, может 95 падёт :) Название: Re: Маша Отправлено: buka от Апрель 29, 2010, 00:43:26 Я проанализировал 60 в качестве селектора.
Очень хороший селектор. Может и 100 свалит... В верхнем полуинтервале тоже можно сжать на 6-7 Если на 2-м шаге можно будет сжать ещё на 1, думаю, 100 падёт. |