Չորս բաժակների խնդիր
Չորս բաժակների խնդիր[1], Մարտին Գարդների տրամաբանական հանելուկը, որը հրապարակվել է Scientific American ամսագրի 1979 թվականի փետրվարյան թողարկման «Մաթեմատիկական խաղեր» սյունակում։
Ձևակերպում[խմբագրել | խմբագրել կոդը]
Չորս բաժակները գտնվում են պտտվող քառակուսի սեղանի անկյուններում։ Որոշ բաժակներ դրված են ուղիղ, իսկ որոշները՝ շրջված։ Աչքերը կապած մարդը պետք է բաժակները այնպես վերադասավորի, որ դրանք բոլորը լինեն նույն դիրքում, այդ դեպքում հնչում է զանգը։ Բաժակները կարող են հերթով վերադասավորվել հետևյալ կանոններին համապատասխան․ ցանկացած երկու բաժակ կարող է ստուգվել մեկ քայլով, և զգալով դրանց դիրքը, մարդը կարող է փոխել նրանցից որևէ մեկի կամ երկու բաժակների դիրքը։ Յուրաքանչյուր շրջումից հետո սեղանը կարող է պտտվել պատահական անկյան տակ։ Խնդիրն այն է, որպեսզի մշակվի ալգորիթմ, որը աչքերը կապած մարդուն թույլ կտա, որ նա համոզվի, որ բոլոր բաժակներ ունեն նույն դիրքը (ուղիղ կամ շրջված) վերջնական թվով շրջումներից հետո։ Ալգորիթմը չպետք է կախված լինի հաջողությունից[2]։
Լուծում[խմբագրել | խմբագրել կոդը]
Ալգորիթմը, որը երաշխավորում է, որ զանգը կհնչի ոչ ավելի, քան հինգ պտույտներից հետո, հետևյալն է․
- Առաջին հերթին ընտրում են անկյունագծով միմյանց հակառակ դրված երկու բաժակները և շրջում դրանք։
- Երկրորդ հերթին ընտրում են երկու հարևան բաժակներ։ Առնվազն նրանցից մեկը նախորդ քայլից հետո ուղիղ է։ Եթե մյուսը շրջված է, պետք է այն նույնպես շրջել։ Եթե զանգը չհնչի, ապա այժմ երեք բաժակները դրված են ուղիղ, իսկ մեկը՝ շրջված։
- Երրորդ հերթին ընտրում են անկյունագծային հակառակ զույգ բաժակներ․ եթե նրանցից մեկը շրջված է, պետք է ուղղել այն, և զանգը կհնչի։ Եթե երկուսն էլ ուղիղ են, պետք է մեկը շրջել։ Այժմ երկու բաժակ շրջված են և գտնվում են միմյանց կողքի։
- Չորրորդ հերթին ընտրում են երկու հարևան բաժակները և շրջում երկուսն էլ։ Եթե երկուսն էլ նույն դիրքն ունեն, ապա զանգը կհնչի։ Հակառակ դեպքում, այժմ երկու բաժակներն ել շրջված են, և նրանք գտնվում են միմյանց հակառակ անկյունագծով։
- Հինգերորդ հերթին ընտրում են անկյունագծով միմյանց հակառակ դրված երկու բաժակները և երկուսն էլ շրջում են, ինչից հետո զանգը կհնչի։
Ընդհանրացում[խմբագրել | խմբագրել կոդը]
Գլուխկոտրուկը կարելի է ամփոփել չորս բաժակների փոխարեն n բաժակների համար։ Երկու բաժակների համար դա լուծվում է մեկ քայլով՝ շրջելով ցանկացած երկու բաժակը։ Երեք բաժակների համար գոյություն ունի երկու պտույտի ալգորիթմ։ Հինգ և ավելի բաժակների համար գոյություն չունի ալգորիթմ, որը երաշխավորում է, որ զանգը կզանգահարի վերջնական քանակի պտույտների դեպքում[3]։
Հետագա ընդհանրացումը թույլ է տալիս ստուգել n բաժակից k բաժակ (երկուսի փոխարեն) յուրաքանչյուր հերթին։ Կարելի է գտնել մի ալգորիթմ, որը լուծում է խնդիրը վերջնական թվով քայլերի դեպքում, եթե k ≥ (1-1/p)n, որտեղ p-ը n-ի ամենամեծ պարզ բազմապատկիչն է[3]։
Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]
- ↑ Ehrenborg, Richard (1995). «The Blind Bartender's Problem» (PDF). Journal of Combinatorial Theory, Series A. 70 (2): 249–266. doi:10.1016/0097-3165(95)90092-6. Արխիվացված (PDF) օրիգինալից 2021 թ․ օգոստոսի 13-ին. Վերցված է 2021 թ․ նոյեմբերի 14-ին.
- ↑ «Braingle » 'Four glasses' Brain Teaser». Արխիվացված օրիգինալից 2021 թ․ նոյեմբերի 14-ին. Վերցված է 2021 թ․ նոյեմբերի 14-ին.
- ↑ 3,0 3,1 Havil, Julian (2007). «Chapter 4: The Spin of a Table». Nonplussed!. Princeton University Press. ISBN 978-0-691-12056-0.