Гениальные математики

[Tomar]

П.С. Мне условие "гениальности математиков" как раз и говорит о их слаженных действиях.
Выборе одинакового (или не конфликтующего) алгоритма действий.
"Мысли умных людей сходятся" (с)

Полностью согласен... но алгоритм есть, а кол-во вопросов очень смущает... отсюда такие метания и рассуждения.

[Вилли ☂]

Афтар топика сказал, что решения в книге, из которой задача, нет.

Ну в этом то и загвоздка.
По сути должно хватит' не более 4 вопросов

[Tomar]

Афтар топика сказал, что решения в книге, из которой задача, нет.

отанокак...

Ну в этом то и загвоздка.
По сути должно хватит' не более 4 вопросов

тоесть я прав, что ищу более короткий вариант.
А то...))) "квадратура круга" получится...

[vp_arth]

не стал читать все 39  страниц... там был ответ?
итак диалог

1: известно мое число?
2: нет
1 думает: (значит у него не 1 и не 1000, иначе бы он знал)
2: известно мое число?
1: нет
2 думает: (значит 2<его число<999)
1: известно мое число?
2: нет
1 думает: (значит 3<его число<998)
2: известно мое число?
1: нет
2 думает: (значит 4<его число<997)... но мое число 4 - значит у него 5!
1: известно мое число?
2: да!

[vp_arth]

минимальное количество вопросов = min(n, 1000-n)

[Лев]

Был вариант покороче, читайте страницы с 25-й

[Sirion]

Комментарии не осилил. Вполне вероятно, решение в них уже есть - но ведь никому не будет хуже, если я его повторю?

Допустим, у математика, который спрашивает первым, нечётное число (случай чётного совершенно симметричен, нужно просто каждое число Х, фигурирующее в дальнейшем тексте, заменить на 1001-Х). Если у него 1 - игра заканчивается после нуля вопросов. Он промолчит, и второму математику (у которого 2) тоже станет всё понятно. Следовательно, если первый математик задаёт свой первый вопрос, второй уже может смело исключать 1 из рассмотрения. То есть игра продолжается с переменой хода на интервале 2..1000.
Если у второго 2 или 1000, он уже знает, что у первого 3 или 999 соответственно. Он отвечает "да", первый тоже всё понимает, игра заканчивается. Иначе он задаёт свой вопрос, роли снова меняются, интервал снова сокращается на единицу с каждой стороны. Таким образом, 500 вопросов достаточно, чтобы сократить интервал до нуля...

Это - неверное решение. На самом деле, существует возможность, что математики так никогда и не выяснят, у кого какое число. Точнее, не выяснит один из них.

Для удобства возьмём интервал 1..4, у первого - число 3, у второго - число 2. Первый не может без вопросов определить число второго, поэтому задаёт вопрос. Второй уже знает, что у первого не 1 - следовательно, 3. Он отвечает "да" - но информации первый из этого никакой не извлекает, ведь точно так же второй бы ответил, если бы у него было число 4. Так они и будут вечно выяснять:"Знаешь? - Да. Знаешь? - Нет."

Может показаться, что эта ситуация возникла из-за того, что мы разрешили первому промолчать, если у него 1. Однако нет. Проверьте сами: если даже первый обязан спрашивать, парадокс всё равно возникнет

В оригинале эта задача (а она старше указанного учебника алгебры) формулируется для всех натуральных чисел. Там сокращение интервала (ну, назовём это интервалом) идёт только с одной стороны, поэтому парадокс не возникает, и задача корректна.

[Вилли ☂]

В оригинале эта задача (а она старше указанного учебника алгебры) формулируется для всех натуральных чисел. Там сокращение интервала (ну, назовём это интервалом) идёт только с одной стороны, поэтому парадокс не возникает, и задача корректна.

Мечтаю получить ссылку на решение задачки.

[Sirion]

Это точно форум умных людей? Берём "неправильное" решение "неправильной" задачи и аккуратно, нежно дорабатываем напильником.

[Um_nik]

Это решение неинтересное. И, ест-но, уже было не раз озвучено. Да-да, с дополнением.
Мы (ну т.е. форумчане) пытаемся найти более короткое решение.

[Sirion]

Более короткого решения быть не может в принципе, это доказуемо. Но этот факт, очевидно, не мешает вам его искать)
Да, при числах 500 и 501 возникнет та же ситуация, что и в приведённом примере с интервалом 1..4 и числами 2,3. Довольно сложно найти более короткую бесконечность, не так ли?
Господи, куда я попал...

[Um_nik]

Докажите.

Не хотелось бы вас расстраивать, но попали Вы туда, где люди куда вежливее вас (ну кроме меня).

[Sirion]

Доказывается элементарно. Какую информацию можно извлечь из отрицательного ответа на вопрос? Ту и только ту, что ответчик ещё не исключил один из двух возможных вариантов числа спрашивающего. Таким образом исключаются те варианты числа ответчика, которые находятся по краям текущего диапазона допустимых значений.

Отсюда, собственно, напрямую следует практически всё, мной изложенное.

[Sirion]

А вообще, жаль, что на этом форуме есть только "симпаффки", но нет "антипаффок". Интересно было бы посмотреть, сколько бы я набрал

[Um_nik]

Меньше меня