[info]smbatgogyan

Արդեն 3-րդ շաբաթն է հայտնի մտքեր են ինձ այցելում

Previous Entry Add to Memories Tell a Friend Next Entry
Տրամաբանական խնդիր 4
[info]smbatgogyan
June 8th, 11:08
Թագավորին հյուրընկալելու համար դուքսը պատրաստվում է 240 տակառ գինի բացել: Սակայն թագավորի ժամանելուց երկու օր առաջ դուքսի ծառաները բռնում են հարևան դուքսի ծառային, որը խոստովանում է, որ տակառներից մեկը թունավորել է, և որ այդ տակառից գոնե մեկ կաթիլ խմողը 24 ժամվա ընթացքում կմահանա: Սակայն նա չի ասում, թե որ տակառն է թունավորած:
Դուքսն ունի 5 ծառա: Ինչպե՞ս գտնել թունավոր տակառը:

Թարմացված: rubywedge լուծեց խնդիրը, ներկայացնում եմ այլ լուծում` 243 տակառի համար



Տակառները համարակալենք հաշվարկի երեքական համակարգով, այսինքն

00000, 00001, 00002, 00010, 00011, 00012, 00020, 00021, 00022,
00100, 00101, 00102, 00110, 00111, 00112, 00120, 00121, 00122,
00200, 00201, 00202, ....................................
......................................................
22200, 22201, 22202, 22210, 22211, 22212, 22220, 22221, 22222

Քանի որ 3^5=243, ուրեմն այստեղ կա 243 թիվ:

Այնուհետև հրամայում են, որ առաջին օրը

1 ծառան խմի այն տակառից, որ համարակալման մեջ առաջին թվանշանը 0-է
2 ծառան խմի այն տակառից, որ համարակալման մեջ երկրորդ թվանշանը 0-է
3 ծառան խմի այն տակառից, որ համարակալման մեջ երրորդ թվանշանը 0-է
4 ծառան խմի այն տակառից, որ համարակալման մեջ չորրորդ թվանշանը 0-է
5 ծառան խմի այն տակառից, որ համարակալման մեջ հինգերորդ թվանշանը 0-է

Հետո, երկրորդ օրը կրկնում են նույնը, բայց հրամայում են խմել այն տակառից (եթե արդեն չի մեռել), որի համապատասխան թվանշանը 1 է, այսինքն

1 ծառան խմի այն տակառից, որ համարակալման մեջ առաջին թվանշանը 1-է
2 ծառան խմի այն տակառից, որ համարակալման մեջ երկրորդ թվանշանը 1-է
3 ծառան խմի այն տակառից, որ համարակալման մեջ երրորդ թվանշանը 1-է
4 ծառան խմի այն տակառից, որ համարակալման մեջ չորրորդ թվանշանը 1-է
5 ծառան խմի այն տակառից, որ համարակալման մեջ հինգերորդ թվանշանը 1-է

Հիմա, եթե առաջին ծառան մեռել է առաջին օրը, ապա թունավոր տակառի առաջին թվանշանը 0-է, եթե մահացել է երկրորդ օրը, ապա 1-է, իսկ եթե երկրորդ օրվա վերջում նա դեռ կենդանի է, ապա թունավոր տակառի առաջին թվանշանը 2-է:

Այդպես, յուրաքանչյուր ծառայի օգնությամբ կիմացվի համապատասխան թվանշանը, ինչի օգնութամբ էլ կգտնվի թունավոր տակառը:

Այժմ խնդրի ընդհանրացում, եթե կա n ծառա և k օր, ապա հնարավոր է (k+1)^n օրում գտնել թունավոր տակառը:
Tags:
( 43 comments — Leave a comment )
1-2 min, apsos hstak chpaheci:

Skzbum takarner@ bajanum enq 5 xmbi (amen xmbum 48 takar), xarnum amen xmbi takarneric miqich gini bajaki mej ev talis bolor caranerin. Hajord or@ "vtangavor" 48 takaranoc xumb@ bajanvum e arden mnacac 4 caraneri, u tenc sharunak minjev takari gtnvel@.
(Reply) (Thread)
chexav. Duqsn yndameny 2 or zhamanak uni
(Reply) (Parent) (Thread)
A, oke, lucum@ hetadzgvec anoroshaki jamanakov
(Reply) (Parent) (Thread)
chisht uxxutyambes mtacum :)
(Reply) (Parent) (Thread)
apsos jamanak chunem -- planner kan Hamming code-i nman ban sarqel, bayc de 5 bitov 240 bit verahskox EDC karoxa real chlini... irikunn em nayelu ;)
(Reply) (Parent) (Thread)
"Բլոնդինկայի" լուծում`
Առանց երկար մտածելու ծառաները ծեծում են միմյանց մինչև որ մեղավոր ծառան չխոստովանի թե որ տակառն է թունավոր:
(Reply) (Thread)
а если он забыл какя бочка отравлена ? :)
(Reply) (Parent) (Thread)
если использовать захваченного слугу у нас 6 человек.
делим 240 бочек на C56+C46+C36+C26+C16 частей (ну или что-то типа того).
из первой части пьет первый слуга, из второй части - первый и второй, и так далее, с перестановками, но одновременно пьют максимум 5 человек :) у нас 60 с чем-то уникальных перестановок, в конце получается 2 толи три бочки и как минимум один живой слуга...
Цифры считать лень, но должно сработать :)
(Reply) (Thread)
но у нас 5 человек
(Reply) (Parent) (Thread)
хотя решение правильное, но объяснил хуево :)
(Reply) (Parent) (Thread)
ну как сумел, так и объяснил :)
(Reply) (Parent) (Thread)
неа, решение не правильное
(Reply) (Parent) (Thread)
ну я тебе отправил решение :)
(Reply) (Parent) (Thread)
а я ответил, что решение не правильное
(Reply) (Parent) (Thread)
да объснил плохо и к тому же не во всех случаях верно

другое решение:
начну со второго дня
во второй день степень двойки от кол-ва оствшихся слуг должно равняться кол-ву проверяемых бочек. Например если осталось 5 слуг , то бочек должно быть не больше 2^5 = 32, не остался один слуга то кол-во бочек будет 2 , в случае всех мертвых останется один и этот будет отравленным. (числа получаются как сумма коеффицентов бинома Ньютона , в случае 5 будет 1+5+10+10+5+1 = 32).

тогда в первый день должны пробовать следующим алгоритмом:

32 бочки не пробует никто, каждый отдельно пробует по 16, каждые две пробуют по 8 , каждые 3 по 4 и т.д. Получается 32 + 16 * 5 + 8 * 10 + 4 * 10 + 2*5 + 1 = 243

тоесть имея 5 слуг можно за два дня пробовать дажбе 243 бочки






(Reply) (Parent) (Thread)
ճիշտ է, ըստ Նյուտոնի բինոմի (2+1)^5 = 2^5 + 2^4 * 5 + 2^3*10+ 2^2 * 10 + 2^1*5+1 : Գևորն էլ էր այդ ուղղությամբ սկսել, ուղղակի (1+1)^5 դրա համար քիչ էր ստացվել մոտը:
(Reply) (Parent) (Thread)
համ էլ ես չէի գրել, որ սխալ է: Նշել էի որ թերի է ու ոչ բոլոր տարբերակներն ես հաշվի առել:
(Reply) (Parent) (Thread)
de eli sxal er, qani vor teri er, hamel bajanum@ miqich urish dzever
(Reply) (Parent) (Thread)
չէ, չեղավ:
1. Բռնած ծառային կախել են:
2. Քո գրած թվերի գումարը կազմում է 62
(Reply) (Parent) (Thread)
5-ով վոոբշե 30-ա ստացվում :(: Բայց միտքը լավն Էր: Լավ , տենենք Էլ ինչ կարելիա մտածել:
(Reply) (Parent) (Thread)
Լավ, իսկ վեռչին վարիանտ կարելիա տիրոջնել օգտագործել ՞ :)
(Reply) (Parent) (Thread)
Իսկ եթե սենց փորձենք`
Քանի որ հայտնի է, թե գինին խմողը 24 ժամից մահանում է, ապա թվերը հուշում են, որ ամեն մի ծառային կարելի է տալ փորձել մի տակառից, մի ժամվա ընթացքում: Այդ դեպքում երկու օրվա ընթացքում 5 ծառաները կփորձեն բոլոր 240 տակառների գինին:
Հենց որ ծառաներից մեկն կմահանա, հաշվում ենք 24 ժամ հետ նրա մահանալու ժամից և պարզում ենք որ տակառն էր թունավոր:

Բայց այս լուծումն իմաստ ունի միայն եթե ուղիղ 24 ժամից է թույնը սպանում, իսկ ես կասկածում եմ, որ խնդիրն այդպես է:
(Reply) (Thread)
Չկպավ
>> 24 ժամվա ընթացքում կմահանա

ոչ թե 24 ժամից, այլ 24 ժամվա ընթացքում
(Reply) (Parent) (Thread)
кто решил, пусть ставит решение -- те вам не соревнование. хотите соревноваться, пожалуйста -- ACM, TopCoder, SPOJ, разное. предлагаю одно правило -- у каждого только одна попытка; например я свою уже использовал.
(Reply) (Thread)
Это мой колодец!!!
(Reply) (Parent) (Thread)
ну именно поэтому что тут не соревнование, пытаться можно сколько угодно я думаю. Иначе в чем смысл ?
(Reply) (Parent) (Thread)
Это к тому, что иногда просто пишут, что решили, давая шанс на решение другим. Вместо этого просто предлагаю ввести то правило и постать решение (что не обязательно будет правильным) со спокойной совестью. Хотя и необязательно, можно и без правил, да.
(Reply) (Parent) (Thread)
Пока что никто не решил.
(Reply) (Parent) (Thread)
это будет наш секрет
(Reply) (Parent) (Thread)
За двое суток (48 засов) можно сделать всего две пробы с получением достоверного результата (то есть отравленный слуга может умереть именно через 24 часа, а не раньше) мне решить не удалось.
При помощи трех проб - решение есть.
(Reply) (Thread)
При двух тоже существует решение
(Reply) (Parent) (Thread)
Делим 240 бочек на 5 групп:

1. 30 бочек
2. 80 бочек
3. 80 бочек
4. 40 бочек
5. 10 бочек

Из первой группы при первой попытки не пьет никто
Вторую группу делим на 5 подгрупп по 16 бочек - из каждой подгруппы будет пить один слуга.
Третью группу делим на 10 подгрупп по 8 бочек - из каждой подгруппы будет пить по двое слуг
Четвертую делим на 10 подгрупп по 4 бочки в каждой - - из каждой подгруппы будет пить трое слуг.
Пятую делим на 5 подгрупп по 2 бочки - из каждой будут пить по четверо слуг.

В итоги после первой пробы имеем один из вариантов:
1. Все слуги остались живы - отравленное вино в первой группе.
2. Один слуга умер, отравленное вино во второй группе и нам точно известна подгруппа с отравленным вином (из 16-и бочек).
3. Двое слуг умерли, отравленное вино в третьей группе, подгруппа из 8-и бочек известна
4. Трое слуг умерли, отравленное вино в 4-ой группе, подгруппу знаем, в подгруппе 4 бочки.
5. Четверо слуг умерли. Отравленное вино в 5-ой группе, подгруппа из 2-х бочек известна.

До начала второй пробы имеем:

5 слуг 30 бочек для проверки или...
4 слуг - 16 бочек
3 слуг - 8 бочек
2 слуг - 4 бочки
1 слуга - 2 бочки

Ну а дальше - все просто. По двоичной системе ( два в степени количества живых слуг ) типа слуга жив/мертв (true/false) все легко проверяется. В первом варианте, даже могло бы быть 32 бочки.

P.S. Слуг жалко...
(Reply) (Thread)
Верно!!!

Решение становится еще проще, если представить числа в троичнои системе. 240< 243 = 3^5
(Reply) (Parent) (Thread)
Да, просто в троичной я как-то не привык
(Reply) (Parent) (Thread)
Մեկ այլ լուծում գրեցի, բայց նախքան այն կարդալը առաջարկում եմ մտածել, թե k օրում n հատ ծառայով քանի՞ տակառից է հնարավոր գտնել թունավորը:
(Reply) (Parent) (Thread)
Դե եթե այս դեպքում 3^5 էր, ապա 5 դա ծառանեոի քանակն է, իսկ 3, հավանաբար փորձերի քանակից հանած 1:
(Reply) (Parent) (Thread)
փորձերի քանակին ԳՈՒՄԱՐԱԾ 1 :)
(Reply) (Parent) (Thread)
гы опередил меня :)
(Reply) (Parent) (Thread)
դու իդեան մոտավորապես հասկացել էիր, ուղղակի չէիր վերջացրել: Պոստում ուրիշ լուծում եմ դրել:
(Reply) (Parent) (Thread)
Журнальчик прикольный у вас, можно было бы уже и на собственный домен перебираться
(Reply) (Thread)
( 43 comments — Leave a comment )
Archive
November 2009
S
M
T
W
T
F
S
1234567
891011121314
15161718192021
22232425262728
2930     
Tags
, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , …
Powered by LiveJournal.com

Advertisement

Advertisement

Home