Задача:
В стая имаме 100 номерирани чекмеджета. В тях има карти с числата от 1 до 100 в произволен ред.
Умник 1 влиза, проверява съдържанието на всички чекмеджета и ако желае, разменя две карти и излиза.
Влиза умник 2 и получава задача да намери карта с даден номер, като отвори не повече от 50 чекмеджета.
Намерете стратегия.
Двамата умници предварително се наговарят първия да остави подсказка на втория в първото чекмедже и при това са уточнили, че подсказката е за съседното второ чекмедже.
И понеже не може в първото чекмедже директно да постави номера на картата във второто (щото тя е във второто), то може да постави картата която е:
карта в първо = 100 - картата във второто
Например, първия е видял, че във второто чекмедже има карта с номер 28, затова в първото поставя карта 72
---------------
Хе-хе, много жега, отивам за хладно душче !
Всъщност, може да се окаже, че умник 2 търси 69 и това,
че знае къде са 72 и 28 може да не му е от полза.
Умник 1 (преди да влезе) знае ли коя карта търси Умник 2?
Аз си държа на идеята Умник 1 да подсказва с първото чекмедже на Умник 2.
И тъй като той може да му подскаже с число от 1 до 100, то това значи, че той може да му предаде седем битова информация - т.е., всеки бит да описва поредица от 14 числа (например бит=1 да означава, че нечетните са повече в съответната поредица от 14 числа). И разбира се, седмия бит няма да е за поредица от 14 числа, а ще е за поредица, от а ще е за последната поредица но от 16 числа.
Така си е, умник 1 подсказва с някое чекмедже на умник 2.
Само че, числата до сто не са пълни 7 бита, трябва да са 128.
И освен това ако знаем къде нечетните са повече, как с 50 опита
ще намерим точно определено число?
Аз пък имам друга идея, но нямах възможност да я споделя.
Всяка пермутация на 100 чекмеджета може да се разбие на независими цикли. Най-много един от тези цикли може да бъде с дължина повече от 50.
Ако Умник1 забележи, че в конкретния случай числата са разбъркани така, че да има такъв дълъг цикъл. той би могъл с разместване на 2 карти да го счупи на два по-къси от 50 (това трябва да докажа).
След което Умник2 има ясна статегия - ако търси числото 47 например, той отваря чекмедже 47. Вижда числото, което се намира вътре и отваря чекмеджето със съответния номер. И така, след най-много 50 отваряния ще открие търсеното число.
Това първото (цикли с дължина не повече от 50), май също трябва да се докаже, защото в главата ми се върти такъв контрапример - в чекмедже с номер N, има карта с номер N+1, за всяко N от 1 до 99
... за N=100 - каквото остане, единствено е !
Сумата от дължините на циклите е 100, затова не може да има два цикъла с дължина 51.
Твоят пример е за един-единствен цикъл, който е с дължина 100. Ако се е случило такова разместване, Умник1 може да го разбие на два независими цикъла с дължина 50 всеки.
Е тогава остава въпроса "да подхванеш правилния цикъл".
Ако са например 5 цикъла с дължина 20, то картата ще излезе най-много на 20-тото отворено чекмедже, но само ако сме подхванали цикъла в който е картата.
Този пост е редактиран от MitkoS; 10-09-19 в 20:31.
Да. Но цикълът, в който е картата, минава през чекмеджето с търсения номер.
Хлъц ?Първоначално публикувано от Bibi
Като за по-прости може ли ?
По-просто е с пример. Ако запишем пермутацията като цикли, да кажем (1 7 45 21 3 90)(2 66)...
То това означава, че в първото чекмедже има 7, във седмото има 45,... в 90-тото има 1. Което и число от тези шест от първия цикъл да ни трябва, ние ще отворим въпросните 6 чекмеджета, докато стигнем до него. И само тях.
Как това решава въпроса за два цикъла с дължина 50 - може да тръгнем с лошия цикъл, да отворим 49 чекмеджета за да разберем, че в първия ход сме сбъркали
А при 5 цикъла с дължина 20 ?!
Или пък 100 цикъла с дължина 1 ?
Новини
Форум
Актуално
сървър
2Одобрявам
Отговор с цитат