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

[Ia_grib]

А мне кажется, что либо задача не совсем корректно сформулирована, либо ответ "Нет, не могут". А может я просто не понял условия. Обосную:
В тексте задачи сказано "Они поочерёдно спрашивают друг друга: "Известно ли тебе моё число?"", т.е. каждый из них спрашивает известно ли ему число своего коллеги или нет. Поскольку точно никто не может знать ни одного числа кроме своего собственного, они так и будут до бесконечности задавать друг другу этот вопрос...
P.S. Поправьте, если я ошибся
P.P.S. Извините, если ответ уже звучал, но 43 страницы топика читать влом как-то

[Вилли ☂]

P.S. Поправьте, если я ошибся
P.P.S. Извините, если ответ уже звучал, но 43 страницы топика читать влом как-то

Вы ошибаетесь, алгоритм есть и он приведён где-то в начале темы (на первых страницах, да ещё и на десятке других, в процессе того как новые люди "доходили" до ответа - писали "свой" вариант дублируя имеющийся алгоритм)
Ну а остальные 40 страниц обсуждений заняла оптимизация алгоритма, но до сегодняшнего дня тщетная.

Задачка действительно интересная. Советую Вам подумать над ней и почитать хотя бы первые странички обсуждения.
Удачи!

[proro4estvo]

К сожалению,я не сильно понимаю что утт происходит,и как уже было описано выше,читать все 44 страницы я не собираюсь). Однако одно могу сказать точно,математиками придется угадывать число,НО,у нас не оговаривается то,что его нужно именно угадать.По условию задачи каждый из математиков знает свое число,и число собеседника будет отличатся на единицу,формально,каждый из них знает число собеседника.Это вариант 1 из 2-х. Математики ведь только честные у нас). По этому ответить "нет" они просто не могут,и после первого же вопроса последует более ли менее вменяемый ответ "да". То есть у нас будет всего 1 вопрос? Так? Если ответ должен быть другим,прошу простить,тогда я его просто не вижу).

[Вилли ☂]

Не совсем.
Математики не знают числа оппонентов. Они лишь знают, что загадано число +1 или -1 от их числа. Но какое именно не знают.
Теперь они придумывают алгоритм (используя описанный вопрос и честный ответ ДА / НЕТ), который позволяет им вычислить (не угадать!) число оппонента.

Уже на третьей странице написан кратко алгоритм:
Показать скрытый текст

пусть у меня к примеру число 2, а у вас 3. начинаем с первого вопроса (цифра 1)
я начинаю первым и спрашиваю:
знаешь?
вы не знаете. т.к. думаете: у него 2 или 4.
теперь вы меня спрашиваете, я понимаю, что, если бы у вас было число 1, вы бы сразу сказали - да!
а раз - нет, то у вас - 3, поэтому я говорю - да!

т.е. если я спрашиваю первым, то 2 вопроса = числу у меня (n=2).
если же первым спрашиваете вы, то добавляется 1 лишний вопрос, поэтому ответ будет найден за n+1 вопросов

примерно так

[dektig]

Достаточно двух вопросов исходя из десятичной системы счисления. Известно, что числа меньше 1000, т.е. гениальные математики понимают, что если одному дали число 999, то он автоматом знает число второго математика ( 998). В разряде единиц цифра 8 стоит от правого рубикона, равного 0, на 2 единицы. И "нечетный" математик должен отвечать на вопрос, учитывая СНИЖЕНИЕ четного на единицу и отставание от рубикона на 1.

Т.о.первым должен всегда задавать вопрос математик с нечетным числом.
Математики также предполагают в качестве рубикона не только 0, но и 5, относительно которых будут строиться ответы.Например загаданы числа 567 и 568. Оба математика знают, что единицы чисел находятся в  промежутке между 5 и 0.Вопрос задает математик с нечетным числом ( 567): Ты знаешь мое число?
Тот отвечает, зная что спрашивающий предполагает число меньшее на 1 и отстающее на 2 от 0, -ДА. При этом он пока не знает какое число первого математика ( либо 567, либо 569) и задает следующий вопрос: Ты знаешь? Тот отвечает НЕТ ( т.е. его число не больше четного на 1).

Пусть заданы числа 455 и 456. Математик с нечетным числом понимает ( как и второй предполагает), что единицы его числа лежат ( могут лежать) на рубиконе. Он задает вопрос: Ты знаешь? Второй отвечает НЕТ. Т.о. давая понять, что его число не меньше рубикона равного 0 на 2 единицы, а значит рубикон =5 ( либо 454, либо 456). Второй задает следующий вопрос. Первый отвечает, зная что его число не меньше рубикона на 1, - НЕТ. Т.о.второй математик понимает, что число =455.

Пусть загаданы числа 399 и 400. "Нечетный" математик спрашивает, естественно, первым. Второй отвечает, предполагая наличие нулевого рубикона,- НЕТ. ( т.е. он не отстает от 0 на 2 единицы).Т.о. нечетный сразу узнает число "четного" математика. Второй спрашивает. "Нечетный" отвечает - НЕТ. "Четный" математик понимает, что число нечетное=399, т.к. "нечетный" математик, работая на понижение на 1,ответил бы ДА только в случае если его число больше, чем у четного на единицу.

2 способ. Оба математика перевели свои числа в двоичную систему. Зная, что концы отличаются друг от друга но один знак, задают вопросы по принципу: "ДА"=1, "НЕТ"=0. Всего чтобы распознать концовки записи двоичных чисел нужно 4 вопроса.

А если бы математики не знали, что их числа отличаются на 1, переведя их в двоичную систему, они узнали бы числа друг друга за 9 вопросов.

[Вилли ☂]

Не могут они выбирать кто начинает, иначе ответ будет известен сразу*.
Я уже это писал на 33 странице 

а если первый вопрос задаст то у кого ...

Если они могут выбират' кто начинает, то на первый же вопрос сразу можно  отвечат' - "ДА".
Т.к. понятно число соперника.
Кстати не важно какой диапазон чисел брат' (-беск, +беск)

Показать скрытый текст

Представ'те Ваше число в двоичном виде (хотябы первые 2 цифры)
первая цифра 0 или 1 говорит нам чётное у нас число или нет. (кстати её же знает наш соперник. Если у него четное, то у нас нет)
вторая цифра и определяет порядок. Всё, что стоит дал'ше нам не интересно.
Итак:
Начинает тот у кого 0 на втором месте.
- "Ты знаеш' моё число?"
- "ДА 3826345!"

А тепер' пример:


А: 11  (1011)
Б: 12  (1100)

Б: - "Ты знаеш' моё число?"   (т.к. у него 0, он начал)
А: - "ДА" *смотрит в таблицу* "12"


Вас спросили (у соперника "0" на втором месте), Вы отвечаете:
у вас 12 четн. и на втором месте 0
 => у соперника (или 11 или 13) не четн. на втором месте 0 (т.к. он начал / спросил)
 => (см. таблицу) у него бол'ше Вашего (+1)

Таблица:

 у Вас                у него
четн.      и 0    -> не четн. 0 (+1)
четн.      и 1    -> не четн. 0 (-1)
не четн. и 0    -> четн.    0 (-1)
не четн. и 1    -> четн.    0 (+1)


Итак возможные "расстановки" тол'ко у одного 0 (как выше)
У обоих 0. Оба орут - "Ты знаеш' моё число?" (как выше, причем оба уже его знают)
У обоих 1. Оба молчат 5сек. И после оба уже знают, что там 1, и след. оба знают числа других.

[dektig]

Не могут они выбирать кто начинает, иначе ответ будет известен сразу*.
Я уже это писал на 33 странице 

а если первый вопрос задаст то у кого ...

Если они могут выбират' кто начинает, то на первый же вопрос сразу можно  отвечат' - "ДА".
Т.к. понятно число соперника.
Кстати не важно какой диапазон чисел брат' (-беск, +беск)

Показать скрытый текст

Представ'те Ваше число в двоичном виде (хотябы первые 2 цифры)
первая цифра 0 или 1 говорит нам чётное у нас число или нет. (кстати её же знает наш соперник. Если у него четное, то у нас нет)
вторая цифра и определяет порядок. Всё, что стоит дал'ше нам не интересно.
Итак:
Начинает тот у кого 0 на втором месте.
- "Ты знаеш' моё число?"
- "ДА 3826345!"

А тепер' пример:


А: 11  (1011)
Б: 12  (1100)

Б: - "Ты знаеш' моё число?"   (т.к. у него 0, он начал)
А: - "ДА" *смотрит в таблицу* "12"


Вас спросили (у соперника "0" на втором месте), Вы отвечаете:
у вас 12 четн. и на втором месте 0
 => у соперника (или 11 или 13) не четн. на втором месте 0 (т.к. он начал / спросил)
 => (см. таблицу) у него бол'ше Вашего (+1)

Таблица:

 у Вас                у него
четн.      и 0    -> не четн. 0 (+1)
четн.      и 1    -> не четн. 0 (-1)
не четн. и 0    -> четн.    0 (-1)
не четн. и 1    -> четн.    0 (+1)


Итак возможные "расстановки" тол'ко у одного 0 (как выше)
У обоих 0. Оба орут - "Ты знаеш' моё число?" (как выше, причем оба уже его знают)
У обоих 1. Оба молчат 5сек. И после оба уже знают, что там 1, и след. оба знают числа других.

А им и не надо выбирать. Это вытекает из их логических ( ОДИНАКОВО гениальных) умозаключений. Выше мною объяснено, почему получивший нечетное число спрашивает первым.
Если вы этого не можете понять, то это не значит, что это не верно!

А во втором варианте вообще без разницы, кто первым спросит, т.к. переход в двоичную систему предполагает максимум 2 разных знака в конце двоичного числа.

[Вилли ☂]

Выше мною объяснено, почему получивший нечетное число спрашивает первым.
Если вы этого не можете понять, то это не значит, что это не верно!

А во втором варианте вообще без разницы, кто первым спросит, т.к. переход в двоичную систему предполагает максимум 2 разных знака в конце двоичного числа.

Я действительно не совсем понял Ваш алгоритм, но заметил пару нарушений правил / изменения условий.
Про это и написал.

Т.о.первым должен всегда задавать вопрос математик с нечетным числом.

Это другая задача.
Алгоритм / решение описано постом выше. Решение за 0 вопросов. Стоит раскрыть рот одному из них (или помолчать 5 сек) - второй уже знает ответ.

Тот отвечает, зная что спрашивающий предполагает число меньшее на 1 и отстающее на 2 от 0, -ДА. При этом он пока не знает какое число первого математика ( либо 567, либо 569) и задает следующий вопрос:

Нарушение правил. Честные математики не могут врать!

2 способ. Оба математика перевели свои числа в двоичную систему. Зная, что концы отличаются друг от друга но один знак, задают вопросы по принципу: "ДА"=1, "НЕТ"=0. Всего чтобы распознать концовки записи двоичных чисел нужно 4 вопроса.

Нарушение правил. Честные математики!
Ответ "ДА" только, если математик знает число оппонента, ответ - "НЕТ", если не знает.

[dektig]

НЕТ и ДА - это не ответы, в обычном понимании, а кодировка своего числа. ДА и НЕТ =+,- от рубежа, ПОЗИЦИЯ от 0 и 5. Т.е. опрашиваемый математик ответом ДА или НЕТ не врет, а обозначает местоположение единиц в числе относительно "рубежей".
Как и в случае с двоичным кодом. ДА=1, НЕТ=0.

[Вилли ☂]

Если математикам разрешить как-либо передавать информацию (выбирать кто начинает первый; подмигиванием; интонацией; кодированием "ДА" означает "1" и д.р.), то вопросов задавать не нужно см. приведённый алгоритм.

Ответ известен сразу после передачи сигнала "у меня '0' на втором месте двоичного представления числа", как его закодировать (например выкрикнуть вопрос первому; или ответить "ДА", подразумевая этот 0 либо как-то ещё).
Задача в этой трактовке не рассматривается, как заведомо уже решенная.


Если придерживаться строго условий изначальной задачи.
Вопрос:  "Известно ли тебе моё число?"
Ответ (честный):  "ДА" / "НЕТ"
То решение за n / n+1 вопросов (или n/2) уже есть и найти более короткое не удалось.
Может у Вас получиться.


П.С. Если на вопрос "Известно ли тебе моё число?" отвечают "Да", при этом не зная числа, то это ложь.

По подсказке некоторых Форумчан, попытался абстрагироваться от 10-тичной системы счисления. Вот:
Двоичная (слева меньшие цифры):

010010010100101001010101...
110010010100101001010101...

001010010100101001010101...
110010010100101001010101...

значимые остальное можно отбросить, не влияет на результат
причем первый '0' означает четность числа (1-неч). Каждый математик знает четное у него число или нет и знает четность соперника

вторая цифра означает:
   * совпадение означает - нечетное число больше, четное меньше
   * НЕ совпадение означает - четное число больше, нечетное меньше

итого остается:
00 - 0
10 - 1
01 - 2
11 - 3

Логично, т.к. если у меня 1, то у соперника либо 0, либо 2
и если у меня 2, то у соперника либо 1, либо 3
это ВСЕ возможные варианты.
Их всего 4 (даже 2)
Зачем нам 500 вопросов задавать, если есть только 4(2) варианта?

Дальше чего-то не думается
Т.е нужно только узнать "0" или "1" и Вашего коллеги.

Но он Вам ето сообшит' не может, пока сам не будет уверен в вашем числе.

[dektig]

Вилли! Я тоже не могу понять, почему нужно задавать 500 вопросов, если разница не в СОТНЯХ, не в ДЕСЯТКАХ, а в ЕДИНИЦАХ. А их всего 10. Т.е. максимум 10 вопросов! Но можно меньше. И мною это показано! И это не вранье, т.к. оба математика это предполагают, зная о позиции своей единицы и четности своего числа и оппонента.
Как же это можно не понять?)))

ДА. И после каждого вопроса математик обозначает СВОЕ число!