Задача или не съвсем...

[ql^2/8]

Доста време заобикалям тази задача, щото все още не съм
намерил отговор, който да ми хареса. И все още се чудя
наистина ли е задача или по-скоро е парадокс:

На двама гениални математици подшушнали по едно естествено число,
между 1 и 1000, като знаят, че числата им са съседни - с разлика 1.
Те могат да си задават последователно само един въпрос:
"Ти знаеш ли числото ми?"
Отговорите са само "Да" или "Не", при това отговарят честно!
Математиците нямат предварителни уговорки и тайни сигнали.
Може ли по такъв начин всеки от тях да разбере числото на съседа си?
Ако да - с колко въпроса?

[zxc0]

Да. От 1 до 499 въпроса. Обяснението ще трябва да почака, че в момента нямам никакво време. Дано някой го формулира дотогава.

[ql^2/8]

Да. От 1 до 499 въпроса. Обяснението ще трябва да почака, че в момента нямам никакво време. Дано някой го формулира дотогава.

Хубаво, че има три почивни дни...

Аз започнах от три числа и установих, че няма решение:
нека М2 има число 2.
М1: - Ти знаеш ли числото ми?
М2: (колебае се между 1 и 3) - Не. Ти знаеш ли числото ми?
М1: - Да. Ти знаеш ли числото ми?
М2: - Не...
и така до безкрай.
Парадоксалното е, че и двамата знаят отговора на въпроса, който задават.

Продължих с 4 числа: М2 има число 2.
М1: - Ти знаеш ли числото ми?
М2: - Не. (колебае се между 1 и 3) Ти знаеш ли числото ми?
Ако М1 е бил с число 1, той е знаел числото на М2 по начало, ако е бил с 3 - от
отговора на М2 е изключил възможността да е 4. И в двата случая вече знае:
М1: - Да. Ти знаеш ли числото ми?
М2: - Не... (така и не може да изключи нито 1 нито 3)
и така до безкрай.

[LameHelper]

Отговора според мен зависи от числата.

Случай 1 в който има отговор
Ако на М1 му дадат числото 1 а на М2 числото 2 и М1 пита М2. Съответно М2 незнае дали 1 или 3 и отговаря Не. Следва обратния въпрос и М1 отговаря с - ДА.
Тук отговора е с 2 въпроса

Случай 2 в който има отговор
Числата са същите но пръв пита М2. Тогава М1 директно отговаря - ДА.
Тук отговора е с 1 въпрос.

Случай 3 и 4 са аналогични но за числото 1000 и 999.

За всички други случаи с различни числа от тези аз не намирам решение

[spiritch]

За нечетен брой числа не става, за четен (без 4) може и да стане. Пробвай да не променяш броя на числата, а само разположението им в хилядарката. Май наистина става до 499 въпроса.

[Bibi]

Според мен поне за четни числа става и може да се докаже с индукция.
Ако знам, че когато имам числото N, задачата изисква най-много n въпроса. И че ако съм получила по-голямо от N, е сигурно, че няма да стигнат n въпроса.
И ако в момента имам числото N+1. Значи другарчето има или N, или N+2. Изчаквам да минат пътвите n въпроса. Ако и на последния той отговори с "Не", значи не е имал N, а N+2.
Т.е. вече аз мога спокойно да отговоря с "Да". Веднага след мен ще може и той.

П.С.
Май избързах. Ако числата не бяха ограничени, щеше да е по-лесно. Около центъра на интервала се появяват двусмислици.

[ql^2/8]

Седя и си мисля като гениален математик:
Имам числото 20, той има 21 или 19. Питам го: "Ти знаеш ли числото ми?"
И двамата знаем отговора. Каква информация получаваме?
Мога да съм сигурен, че числото му не 1. Ами че аз това го зная без да питам.
Странно ми е.

[etg]

Нека числата са N за математик X и N+1 за математик Y.
Ако X е започнал с въпросите са нужни 2хN въпроса, ако Y е започнал - 2хN-1.

Идеята ми е следната:
1. X пита Y
Y може да отговори с "Да" само ако неговото число е 1. Ако не е 1, отговаря с "Не"
2. Y пита X
X може да отговори с "Да" само ако неговото число е 1. Ако не е 1, отговаря с "Не"
Вероятно и двамата знаят отговорите, реално нищо ново не научават, но така се съгласяват, че и на двамата числото не е 1. Това е необходима стъпка, за да могат да продължат напред. Ако някой има числото 1 решението е ясно - той знае, че другият има 2, и казва "Да"

3. X пита Y
Y може да отговори с "Да" само ако неговото число е 2. Ако не е 2, отговаря с "Не".
4. Y пита X
X може да отговори с "Да" само ако неговото число е 2. Ако не е 2, отговаря с "Не"
И двамата вече знаят (след т.1 и т.2), че никой няма 1, така че ако някой има 2 той знае, че другият има 3. Ако никой няма 2 продължаваме.

5. X пита Y
Y може да отговори с "Да" само ако неговото число е 3. Ако не е 3, отговаря с "Не".
6. Y пита X
X може да отговори с "Да" само ако неговото число е 3. Ако не е 3, отговаря с "Не"
И двамата вече знаят (след т.3 и т.4), че никой няма 2, така че ако някой има 3 той знае, че другият има 4. Ако никой няма 3 продължаваме.

...

Процедираме така докато стигнем до N-1 - по два въпроса за всяко число. Ще са зададени 2х(N-1) на брой въпроси и двамата ще знаят, че никой няма число от 1 до N-1. X има числото N, така че вече знае, че числото на Y е N+1.

2х(N-1)+1 X пита Y
Y може да отговори с "Да" само ако неговото число е N. Ако не е N, отговаря с "Не".
2х(N-1)+2 Y пита X
X може да отговори с "Да" само ако неговото число е N. Ако не е N, отговаря с "Не". В случая отговаря с "Да", и така и Y разбира числото на X

Ако обаче Y обаче е почнал с въпросите стигаме до въпрос 2х(N-1)+1:
2х(N-1)+1 Y пита X
X може да отговори с "Да" само ако неговото число е N. Ако не е N, отговаря с "Не". В случая отговаря с "Да", и така и Y разбира числото на X

[Bibi]

Ако аз имам числото 3, другарчето има 2 или 4. Значи той или се колебае между 1 и 3, или между 3 и 5.
Ако чуе от мен веднъж НЕ и въпреки това продължи да се колебае, значи дилемата му не е била между 1 и 3. Значи знам, че той има 4.
Тук важното е, че той е отговорил с НЕ след като е чул един отговор от мен.
И броенето започва да зависи от това кой е питал първи.

Понеже говорим за гениални математици, те дори без да се наговарят биха могли да съобразят, ако е по-изгодно първия въпрос да го задава човекът с четното число. И така част от неопределеността ще отпадне.
Обаче при числа, близки до 1000, това се обръща.
А при 500 и 501 самото броене започва да става двусмислено.

[ql^2/8]

Добре де, ако аз имам числото 321, знам, че съседа м има 319 или 322,
защо не почнем изключването от 301, вместо от 1?
И вместо 320 въпроса да зададем 20?
,

[etg]

Защото на мен поне не ми хрумва как да се разберем от колко да почнем, ако не е от 1. Напълно е възможно да има много по-елегантно решение. Аз се опитах да намеря някакъв вариант за опростяване, но се въвличам в една рекурсия, от която няма излизане преди края на интервала.

[ql^2/8]

. . .
Понеже говорим за гениални математици, те дори без да се наговарят биха могли да съобразят,
ако е по-изгодно първия въпрос да го задава човекът с четното число.
Обаче при числа, близки до 1000, това се обръща.
А при 500 и 501 самото броене започва да става двусмислено.
. . .

Разсъжденията са верни. Когато числата са точно по средата - 500 и 501 работата се запича.
Затова когато този с 500 (щото е четен от първата половина) попита:
"Ти знаеш ли числото ми" - Оня с 501 отговаря "Да!"
Щото му е ясно, че са им скроили шапка. Ако другия имаше 502 (четен, ама от втората половина),
щеше да си трае и да не задава въпрос!
Същото се случва и ако този с 501 изпревари и зададе пръв въпроса (защото е нечетен от горната половина)
- получава "ДА" от този с 500 като първи отговор.

Само че, не е ясно дали условието допуска да си избират кой да започне?

[Bibi]

Намерих подобна задача в някакъв руски форум. Само че безкрайна (което в случая е по-лесно).
Знаят само, че числата им са поредни.
При това трябва да се докаже, че рано или късно поне единият ще знае числата.
Задачата беше класифицирана за 8-ми клас.

[ql^2/8]

Мда, задачата безкрайна а математиците безсмъртни.
Оказва се, че ако ограничим задачата - затормозяваме гениите...
А нещо в тази задача не ви ли намирисва на парадокса
за неочакваното обесване?

[etg]

И аз потърсих в нета и намерих подобна задача, оказва се, че явно няма по-лесно решение. Само че в посочената там задача има часовник, който реално замества питанията: Guessing Two Consecutive Integers

Имам обаче един въпрос, защото явно нещо ми убягва - какъв е проблема в това, че числата са ограничени?