Страница 1 от 2 12 ПоследноПоследно
Резултати от 1 до 15 от общо 19

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

Сподели във Facebook Сподели в Twitter Изпрати на Email Сподели в LinkedIn
  1. Member
    Тук е от
    Sep 2009
    Мнения
    831
    #1

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

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

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

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

  2.  
     
  3. Senior Member
    Тук е от
    Dec 2010
    Мнения
    1,600
    #2

    Отговор: Задача или не съвсем...

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

  4. Member
    Тук е от
    Sep 2009
    Мнения
    831
    #3

    Отговор: Задача или не съвсем...

    Цитат Първоначално публикувано от zxc0 Виж публикацията
    Да. От 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)
    и така до безкрай.

  5. Junior Member
    Тук е от
    Mar 2012
    Живее в
    Варна
    Мнения
    76
    #4

    Отговор: Задача или не съвсем...

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

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

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

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

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

  6. Member
    Тук е от
    Sep 2010
    Живее в
    Стара Загора
    Мнения
    157
    #5

    Отговор: Задача или не съвсем...

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

  7. Senior Member Аватара на Bibi
    Тук е от
    Nov 2004
    Мнения
    2,757
    #6

    Отговор: Задача или не съвсем...

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

    П.С.
    Май избързах. Ако числата не бяха ограничени, щеше да е по-лесно. Около центъра на интервала се появяват двусмислици.
    Този пост е редактиран от Bibi; 20-09-14 в 15:17.

  8.  
     
  9. Member
    Тук е от
    Sep 2009
    Мнения
    831
    #7

    Отговор: Задача или не съвсем...

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

  10. etg
    etg е на линия
    Administrator
    Тук е от
    Dec 2000
    Мнения
    1,393
    #8

    Отговор: Задача или не съвсем...

    Нека числата са 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

  11. Senior Member Аватара на Bibi
    Тук е от
    Nov 2004
    Мнения
    2,757
    #9

    Отговор: Задача или не съвсем...

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

    Понеже говорим за гениални математици, те дори без да се наговарят биха могли да съобразят, ако е по-изгодно първия въпрос да го задава човекът с четното число. И така част от неопределеността ще отпадне.
    Обаче при числа, близки до 1000, това се обръща.
    А при 500 и 501 самото броене започва да става двусмислено.
    Този пост е редактиран от Bibi; 22-09-14 в 11:48.

  12. Member
    Тук е от
    Sep 2009
    Мнения
    831
    #10

    Отговор: Задача или не съвсем...

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

  13. etg
    etg е на линия
    Administrator
    Тук е от
    Dec 2000
    Мнения
    1,393
    #11

    Отговор: Задача или не съвсем...

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

  14.  
     
  15. Member
    Тук е от
    Sep 2009
    Мнения
    831
    #12

    Отговор: Задача или не съвсем...

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

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

  16. Senior Member Аватара на Bibi
    Тук е от
    Nov 2004
    Мнения
    2,757
    #13

    Отговор: Задача или не съвсем...

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

  17. Member
    Тук е от
    Sep 2009
    Мнения
    831
    #14

    Отговор: Задача или не съвсем...

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

  18. etg
    etg е на линия
    Administrator
    Тук е от
    Dec 2000
    Мнения
    1,393
    #15

    Отговор: Задача или не съвсем...

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

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

Сподели във Facebook Сподели в Google Plus Сподели в Twitter Изпрати на Email Сподели в LinkedIn
Страница 1 от 2 12 ПоследноПоследно

Подобни теми

  1. Bing притеснява Google, но не съвсем...
    От kod във форум Новини от SetCombG.com
    Отговори: 0
    Последно: 07-10-10, 17:17
  2. Отговори: 3
    Последно: 10-01-10, 14:29
  3. Безплатен монтаж от Технополис или не съвсем ?
    От swaaapy във форум Въпроси свързани с монтажа
    Отговори: 1
    Последно: 11-06-09, 06:27
  4. Отговори: 12
    Последно: 16-04-07, 18:00

SetCombG.com
SetCombG.com е портален сайт и Форум за битова техника, телевизори, климатици, лаптопи и смартфони, създаден през 1999 година.
Заедно сме над 20 години!
Следвай ни
Горе