Страниц: 1 ... 38 39 [40] 41 42 ... 44
  Печать  
Автор Тема: Гениальные математики  (Прочитано 225519 раз)
0 Пользователей и 1 Гость смотрят эту тему.

Каждому из двух гениальных математиков сообщили по натуральному числу меньше 1000, причём им известно, что эти числа отличаются на 1. Они поочерёдно спрашивают друг друга: "Известно ли тебе моё число?" Можно ли таким способом узнать число соседа, если математики не только гениальны, но и абсолютно честны друг перед другом? Если да, то за сколько вопросов?
(Алфутова, Устинов. Алгебра и теория чисел. N 1.49.)

зы: уточняю условие: "Могут ли математики таким способом узнать числа друг друга, если они не только гениальны, но и абсолютно честны друг перед другом? Если да, то за сколько вопросов?"
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #585 : Май 07, 2011, 09:42:08 �

Это временно) Таки Вы удовлетворены объяснением?
Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
Kubinator
Новенький
*
Offline Offline

Сообщений: 40

СПАСИБО
-вы поблагодарили: 3
-вас поблагодарили: 12


Просмотр профиля Email
Ответ #586 : Май 07, 2011, 09:56:03 �

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

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

Это математически нестрогое доказательство. Пусть у Вас та же задача в исходной формулировке, для всего натурального ряда. Докажите, что необходимо количество вопросов того же порядка, что задуманные числа. Доказательство есть, но тут оно не приведено.
Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #587 : Май 07, 2011, 10:44:11 �

Это, батенька, бюрократический формализм. Просто берём мои рассуждения и оформляем строго как мат.индукцию. И база, и переход очевидны.
Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #588 : Май 11, 2011, 12:17:33 �

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

формулировка задачи здесь действительно упрощенная, о чем, кстати, говорилось в обсуждении этого топика вот здесь: http://nazva.net/forum/in...01.msg40494.html#msg40494 и потом еще неоднократно.
и ответ (n или n+1) также был передложен на 2 странице топика Ильей и потом тоже неоднократно  обсуждался.
что касается формулировки задачи в исполнении авторов из указанного мною источника, то, вероятно, там не случайно в формулировке указано "число соседа", а не как в уточненной мной формулировке "числа друг друга". тогда есть известное корректное решение указанной (обрезанной Embarrassed) задачи, которое уже тоже обсудили, когда число соседа гарантировано угадывает лишь один из математиков.
основное же обсуждение свелось к разрешению вопроса: возможно ли сократить количество задаваемых вопросов для известного (конечного) интервала так, чтобы оба математика смогли узнать "числа друг друга".

зы: а пока стройного доказательства невозможности корректного решения предложенного варианта никто не озвучил, настоящий топик будет по-прежнему будоражить пытливые умы форумчан Tianchik



Последнее редактирование: Май 11, 2011, 13:01:43 от Smith Записан
Вилли ☂
Гений-Говорун
*
Offline Offline

Сообщений: 1572

СПАСИБО
-вы поблагодарили: 532
-вас поблагодарили: 722





Просмотр профиля
Ответ #589 : Май 11, 2011, 12:56:50 �

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

В том-то и загвоздка, какой алгоритм подсчета выбрать.
Этот ответ будет верным, при приведенном алгоритме, который вполне может оказаться не оптимальным.

Как вариант:
 - каждым ответом движемся к цели десятками (+10), как только перешагнули подошли к своей 10 - по одному (+1)
 - каждым ответом движемся к цели по простым числам, как только перешагнули - по одному назад (-1)
 - да мало ли можно напридумывать

П.С. выше описанные варианты не подходят (по крайней мере без доработок)
Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #590 : Май 11, 2011, 13:11:43 �

Да хосспаде ты божэ ты мой...

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

2. Если после очередного ответа одно из чисел, соседних с числом, загаданным математику, становится недопустимым - тогда (и только тогда) он может понять, какое число у другого математика.

3. После ответа "нет" становятся недопустимыми те (и только те) числа, у которых недопустимо одно из соседних, а чётность совпадает с чётностью числа, загаданного отвечавшему математику.

4. После ответа "да" становятся недопустимыми те (и только те) числа, у которых оба соседних числа допустимы, а чётность совпадает с чётностью числа, загаданного отвечавшему математику.


5. Исходя из пунктов 1-4 и в предположении, что математикам загаданы числа 500 и 501, мы и получаем тот сценарий игры, о котором я говорил. На первом ходу интервал допустимых чисел сокращается на 1, последующие 998 ходов он сокращается на 2 (оставаясь при этом интервалом). На тысячном ходу останется лишь три допустимых числа - 500, 501, 502 (в предположении, что математик с числом 500 спрашивал первым). На все последующие вопросы математика с числом 501 второй математик будет отвечать "да" - из-за чего, в силу пунктов 3 и 4, ни одно из чисел {500, 502} не станет недопустимым, и математик с числом 501 никогда не сможет узнать число другого.


Тому, кто заявит, что приведённое выше рассуждение нестрого, неплохо бы пояснить свою позицию.
Последнее редактирование: Май 11, 2011, 13:13:48 от Sirion Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #591 : Май 11, 2011, 13:24:38 �

Ах да. Разумеется, мы исходим из предположения, что математики рассуждают, опираясь именно на допустимость. Скажем, если у одного из математиков число 500, он заранее знает, что у другого не может быть числа 1. Но после того, как он задаст другому вопрос, а другой ответит "нет", первый математик... как бы это сказать... "точно" знает, что числа 1 у другого быть не может, ни в какой галактике.

Если не пользоваться вот этим "точно", задача заведомо неразрешима для всех случаев, кроме {1,2} и {999, 1000}, поскольку ответы не будут уменьшать меру неопределённости.
Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
Вилли ☂
Гений-Говорун
*
Offline Offline

Сообщений: 1572

СПАСИБО
-вы поблагодарили: 532
-вас поблагодарили: 722





Просмотр профиля
Ответ #592 : Май 11, 2011, 13:49:38 �

Вы вседга обсуждаете одно и тоже решение и из этого пытаетесь вывести его уникальность.

Ладно, отвлечёмся.

Цитировать
Скажем, если у одного из математиков число 500, он заранее знает, что у другого не может быть числа 1.

Не наталкливает ли Вас на мысли, что первые, пусть хотябы 400 ответов будут "нет" и ОБА математика это ЗНАЮТ изначально еше до ИГРЫ, а стало быть ответы на них не несут НОВОЙ информации и как следствие НЕ ЯВЛЯЮТСЯ информативными (необходимыми).
Т.е. решение (рассудок подсказывает) - не оптимально.

Поиском оптимального (или лучшего, чем предложенно) мы тут и заняты.

Двигаться "по еденичке к решению" - не опримально
Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #593 : Май 11, 2011, 14:04:24 �

Понимаете ли... Цитируя топикстартера, мы ищем решение при условии, что "они не только гениальны, но и абсолютно честны друг перед другом". Кроме того, я так понимаю, что математики не должны ни о чём договариваться друг с другом до начала игры. Если эти условия убрать - достаточно двух вопросов, для худшего случая.
Нужно всё-таки определиться, какую задачу мы решаем. Иначе всё так и останется на уровне завуалированных обвинений в идиотии.
Последнее редактирование: Май 11, 2011, 14:05:58 от Sirion Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
Smith
Из мудрейших мудрейший
**
Offline Offline

Сообщений: 2950

СПАСИБО
-вы поблагодарили: 286
-вас поблагодарили: 305


PeAcE


Просмотр профиля
Ответ #594 : Май 11, 2011, 21:31:25 �

Нужно всё-таки определиться, какую задачу мы решаем. Иначе всё так и останется на уровне завуалированных обвинений в идиотии.
чего ж те еще надобно, старче? Cheesy
зы: я ж вроде написал уже здесь: http://nazva.net/forum/in....msg157297.html#msg157297
Записан
Tomar
Давненько
**
Offline Offline

Сообщений: 79

СПАСИБО
-вы поблагодарили: 3
-вас поблагодарили: 21



Просмотр профиля Email
Ответ #595 : Май 12, 2011, 05:17:05 �

Двигаться "по еденичке к решению" - не опримально

При некоторых условиях можно шаг сделать "2" - уже в 2 раза сократит кол-во вопрозоф
Записан
Tomar
Давненько
**
Offline Offline

Сообщений: 79

СПАСИБО
-вы поблагодарили: 3
-вас поблагодарили: 21



Просмотр профиля Email
Ответ #596 : Май 12, 2011, 05:45:01 �

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

   
Последнее редактирование: Май 12, 2011, 05:49:45 от Tomar Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #597 : Май 12, 2011, 08:43:58 �

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

   

Я ничего не понял из этого комментария только лишь по причине похмелья, или здесь действительно какой-то шизофазический бред?
Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
Tomar
Давненько
**
Offline Offline

Сообщений: 79

СПАСИБО
-вы поблагодарили: 3
-вас поблагодарили: 21



Просмотр профиля Email
Ответ #598 : Май 12, 2011, 08:54:57 �

Я ничего не понял из этого комментария только лишь по причине похмелья, или здесь действительно какой-то шизофазический бред?

Гы- прав народ оказывается, ты вправду хам)))

Не понял? А еще на форум умных людей пришел - задачка для гениальных математиков, а не хамоватых посредственностей.
Ну да ладно...
Поясняю!
Каждым вопросом я отнимаю от своего числа единичку и на следующий вопрос своего визави отвечаю "нет".
После того, как я получаю у себя "0", на вопрос визави я отвечаю "ДА" потому как знаю, что ОН еще не дошел до нуля - значитсо у него число больше, чем моё на идиничку (единичку... если што)
После моего "ДА" визави понимает, что у меня число меньше на идиничку (повторять?Smiley)...
Мы оба знаем числа свои...

мечись трезвый...

ЗЫ: Ах да... фстолбике результат вычитания единицы и ответ на вопрос
Последнее редактирование: Май 12, 2011, 08:59:21 от Tomar Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #599 : Май 12, 2011, 09:43:33 �

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

Во-первых, последовательность ответов может выглядеть так и только так: до некоторого момента - сплошные "нет", затем - сплошные "да". Почему так? Если математик в некоторый момент понял, какое число у другого, он уже не может перестать это понимать, и после одного ответа "да" остальные ответы также будут "да". Для другого математика, в свою очередь, ответы первого перестают нести информацию - поэтому если он в принципе способен понять, какое число у первого, он должен это сделать после первого же "да".

Пусть математикам загадана пара чисел (х, х+1). Здесь и далее первое число пары относится к математику, задававшему первый вопрос в игре. Не нарушая общности, пусть математик с числом х первым ответил "да". Пусть теперь загадана пара (х, х-1). Математик с числом х не мог ответить "да" первым - иначе получилось бы, что он, получая одну и ту же последовательность ответов "нет" от другого, тем не менее как-то различает две неразличимых ситуации. Значит, первым ответит "да" математик с числом (х-1). Пусть это произойдёт на вопросе под номером (Ы-1) (чтоб никто не догадался). Теперь рассмотрим ситуацию с точки зрения математика, которому загадано число х и он не знает, какое число у оппонента. Если математик с числом х на вопрос под номером (Ы-1) получает ответ "да", он понимает, что реализовалась ситуация (х, х-1), и вопрос под номером (Ы-1) становится последним. Если же он получает ответ "нет", он понимает, что реализовалась ситуация (х, х+1) и отвечает "да" на Ытый вопрос, после чего второй математик (см. предыдущий абзац) обязан также всё понять. Следовательно, ситуация (х, х+1) разрешается за Ы вопросов. Или, что то же самое, ситуация (х, х-1) разрешается на один вопрос быстрее ситуации (х, х+1).

Рассмотрим теперь ситуации (х, х-1) и (х-2, х-1) с точки зрения математика с числом (х-1). Рассуждая аналогично, приходим к выводу, что для разруливания ситуации (х-2, х-1) понадобится (Ы-2) вопроса. Продолжая спуск, мы получим, что для ситуации (1, 2) либо (2,1), в зависимости от чётности, понадобится (Ы-х+1) вопросов. Для разруливания ситуации (1, 2) необходимо и достаточно двух вопросов, для ситуации (2,1) - одного. Следовательно, Ы=х либо Ы=х+1, в зависимости от чётности.

Если же в ситуации (х, х+1) первым отвечает "да" тот математик, у которого число больше, мы совершенно аналогично сводим всё к случаям (999, 1000) и (1000, 999).

Ктулхический мозг математиков способен обойти тот парадокс, о котором я говорил. Например, они одновременно могут прийти к мысли забить на верхний (или нижний) предел. Если я правильно понял, пользователь Tomar чем-то в этом роде и воспользовался (возможно, его мозг зохаван Ктулху, ня?). Однако даже при этом им заведомо понадобится количество вопросов не меньше, чем расстояние от одной из границ интервала. В противном случае для передачи дополнительной информации кому-то из них придётся врать.
Последнее редактирование: Май 12, 2011, 09:52:35 от Sirion Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
Страниц: 1 ... 38 39 [40] 41 42 ... 44
  Печать  
 
Перейти в: