Potworne ciasteczka
Czy pamiętają Państwo, gdzie się pojawiał Ciasteczkowy Potwór? A kto kojarzy się naszemu premierowi z Ciasteczkowym Potworem? Łatwe zagadki? W takim razie proponuję coś nieco trudniejszego na podobny temat.
Ciasteczkowy Potwór lubi „znęcać się” nad ciasteczkami przed ich pożarciem, jak kot nad złowiona myszą. Wczoraj wysypał wszystkie, jakie miał, na stół i ułożył z nich 15 stosików. W pierwszym było jedno ciasteczko, a w każdym następnym o jedno więcej, czyli w sumie 120. CP poprosił swojego kuzyna, by ten wskazał kilka dowolnych stosików, a następnie z każdego wskazanego przez kuzyna zjadł taką samą liczbę ciasteczek. Potem zabawa, czyli wskazanie i konsumpcja – zgodnie z identycznymi jak poprzednio zasadami – powtórzyła się. I jeszcze raz, i znów… Teraz CP chodzi i przechwala się, że ostatnie ciasteczko pochłonął w czwartej turze. Czy to możliwe?
Kuzyn potwierdza, że taka sytuacja miała miejsce, ale uważa, że to jego zasługa, bo to on wskazywał odpowiednie stosiki i określał jaką liczbę ciasteczek CP powinien z każdego skonsumować. O rozstrzygnięcie sporu poproszono Orła Sama. Ten ułożył na dwóch stołach ustawionych za szybą pancerną kilka stosików ciasteczek. Na jednym stole były cztery stosiki liczące 11, 5, 4 i 2 sztuki, na drugim pięć sześć – 17, 16, 11, 4, 2, 1. Strony toczące spór poproszono o wskazanie, w ilu co najmniej turach i w jaki sposób można skonsumować wszystkie ciasteczka najpierw z jednego, a potem z drugiego stołu, zakładając, że w każdej turze należy – jak poprzednio w zabawie – zjeść taką samą ich liczbę z dowolnie wybranych stosików.
CP, jak się spodziewano, natychmiast rzucił się ku ciasteczkom. Walnął jednak głową w szybę i na chwilę stracił przytomność. Gdy się ocknął, usiłował najpierw pożreć szklaną przeszkodę, co jednak nie było łatwe, bo mu się zęby ślizgały.
Kuzyn Ciasteczkowego Potwora po dłuższej chwili podał prawidłowe rozwiązania. Jakie?
Komentarze
Ciasteczka z pierwszego stołu można zjeść w trzech turach:
5 ciasteczek z pierwszego i drugiego stosiku (6, 0, 4, 2)
4 ciasteczka z pierwszego i trzeciego stosiku (2, 0, 0, 2)
2 ciasteczka z pierwszego i czwartego stosiku
Ciasteczka z drugiego stołu wymagają czterech tur:
11 ciasteczek z pierwszego, drugiego i trzeciego stosiku (6, 5, 0, 4, 2, 1)
4 ciasteczka z pierwszego, drugiego i czwartego stosiku (2, 1, 0, 0, 2, 1)
2 ciasteczka z pierwszego i piątego stosiku (0, 1, 0, 0, 0, 1)
1 ciasteczko z drugiego i szóstego stosiku
albo:
10 ciasteczek z pierwszego, drugiego i trzeciego stosiku (7, 6, 1, 4, 2, 1)
4 ciasteczka z pierwszego, drugiego i czwartego stosiku (3, 2, 1, 0, 2, 1)
2 ciasteczka z pierwszego, drugiego i piątego stosiku (1, 0, 1, 0, 0, 1)
1 ciasteczko z pierwszego, trzeciego i szóstego stosiku
Dodatkowo można by dodać warunek (zarówno do zadania z 15 stosikami, jak i do zadań z 4 i 6 stosikami), że w każdej turze należy wskazać taką samą ilość stosików.
Jeśli chodzi o tych 15 kupek od 1 do 15 ciasteczek to po prostu ciekawe zadanie na wykorzystanie systemu dwójkowego lub potegi dwójki. Zjadanie zaczynamy od zjedzenia 8 ciasteczek w kupkach od 8 do 15, potem 4 ciasteczek od 4 do 7 oraz od 12 do 15 kupki, potem w 2,3, 6,7, 10,11 i 14,15 kupce zjadamy po dwa ciasteczka i na koniec same pojedyncze ciasteczka w czwartej turze. Czyli najpierw po 8 w drugiej polowie kupek, potem po 4 ciasteczka w drugich polowach polowek a potem po 2 ciasteczka w drugich polowach „ćwiartek” i nakoniec zostaje po ciasteczku w co drugiej kupce.
11,5,4,2 :
1.zjadamy po 5 ciasteczek: 6, 0, 4, 2
2. zjadamy po 4 ciasteczka: 2, 0, 0, 2
3. zjadamy po 2 ciasteczka: 0, 0, 0, 0
1,2,4,11,16,17 :
1. zjadamy po 10 ciasteczek: 1,2,4,1,6,7
2. zjadamy po 4 ciasteczka: 1,2,0,1,2,3
3. zjadamy po 2 ciasteczka: 1,0,0,1,0,1
4. zjadamy po 1 ciasteczku: 0,0,0,0,0,0
Jak pięć, skoro sześć stosików stoi na drugim stoliku? 🙂
1) Tak, to możliwe. Najpierw należy zjeść po 8 ciastek z każdej kupki, która zawiera przynajmniej osiem ciastek, później po cztery z każdej kupki, w której są przynajmniej cztery ciastka, następnie po dwa z każdej kupki, z której się da i finalnie: zjeść wszystkie pojedyncze ciasteczka.
2) Do opróźnienia pierwszego stołu konieczne są trzy tury, bowiem gdyby wystarczyły dwie, oznaczałoby to, że po pierwszej turze na każdej kupce jest tyle samo ciastek, a to oznacza, że na początku były co najwyżej trzy kategorie równolicznych kupek: ta, z której zjedzono wszystkie ciastka, ta, z której nie zjedzono ciastek wcale i ta, z której zjedzono część ciastek i na każdej kupce zostało tyle co na kupce z kategorii drugiej. Mamy natomiast cztery kupki o różnej ilości ciastek.
Jak to zrobić w trzech turach? Sposobów jest kilka, ja podaję ten, który najbardziej spodoba się Potworowi, czyli taki, gdzie w pierwszej turze zjadamy największą możliwą ilość ciach:
11, 5,4,2 zjadamy po 5 ciach z dwóch największych kupek
6,-,4,2 zjadamy po 4 ciacha z dwóch kupek
2,-,-,2 zjadamy po 2 ciacha
3) W punkcie 2 pokazaliśmy, że żeby opróżnić stół w 2 turach na stole mogą być tylko 3 wysokości stosów.
Aby w wyniku operacji zjadania z pewnych trzech kategorii równoważności powstała jedna, suma wysokości dwóch tych kategorii musi się równać trzeciej.
Takiej sytuacji na naszym stole nie ma, tak więc pierwszy ruch spowoduje zmniejszenie ilości kategorii o co najwyżej 1, czyli po pierwszym ruchu uzyskamy min. 5 wysokości. Ergo – potrzebujemy przynajmniej 4 ruchów.
Zachłanny przykład rozwiązania:
17, 16, 11,4,2,1 zjadamy po 11 z każdej kupki, z której się da
6,5,-,4,2,1 zjadamy po 4 z każdej, z której się da
2,1,-,-,2,1 zjadamy dwuciastkowe kupki
-,1,-,-,-,1 zjadamy ostatnie ciastka
To wszystko przy założeniu, że operacje oczyszczania obu stołów wykonujemy niezależnie od siebie.
Przy odczytaniu treści zadania następująco: mamy dwa stoły, jak zjadając ciastka z obu stołów równocześnie, opróżnić je w najmniejszej ilości ruchów, przy czym drugi stół nie może być opróżniony w ruchu, po którym na pierwszym coś zostaje, wystarczą również 4 ruchy:
11, 5,4,2|| 17,16,11,4,2,1 zjadamy po 11 tam gdzie się da
-,5,4,2|| 6,5.-,4,2,1 zjadamy po 4
-,1,-,2||2,1,-,-,2,1 zjadamy po 2
-,1,-,-||-,1,-,-,-,1 zjadamy ostatnie ciacha
Myliłby się jednak ten, kto uważa, że zachłanny algorytm typu: za każdym razem zjedz tak dużo ciastek, jak potrafisz, będzie optymalny pod względem ilości tur.
Przypuszczam, ale dowodu na to nie widzę, że optymalny algorytm to taki: wyszukaj wszystkie pasujące (czyli typu a+b=c) trójki wysokości, zjedz z tylu kupek, z ilu się da cały ten stos a czy b, który powtarza się w największej ilości pasujących trójek. Jeśli w danym momencie nie ma żadnej trójki, zjedz jak najwięcej ciastek tak, aby opróżniając przynajmniej choć jeden stos utworzyć taką trójkę.
Istotnie, tak mogło się zdarzyć, że CP zjadł ciasteczka w czterech turach i rzeczywiście ten rekord zawdzięcza kuzynowi.
Podobnie rzecz ma się ze stosikami na pierwszym stole. Tam też potrzeba minimum czterech tur. Natomiest drugiego stołu nie można opróżnić szybciej niż w pięciu turach.
Liczba tur zawsze zależeć będzie od kuzyna. No może z wyjątkiem, gdy CP ma do pochłonięcia tylko jedno ciasteczko.
Nie umien sobie jeszcze odpowiedzieć na pytanie o strategię w ogólnym przypadku, ale myślę, że jest to tylko kwiestią czasu.
Pozdrawiam,
Czytając to zadanie przypomniało mi się inne, nie tyle ze zjadaniem ciasteczek co ze zjadaniem/usuwaniem cyfr:
z cyfr od 1 do 9 proszę utworzyć liczbę 9-cyfrową (każda cyfra pojawia sie tylko raz), liczba ta ma być podzielna przez 9. Jeśli usuniemy ostatnią cyfrę (z prawej strony), to ta 8-cyfrowa liczba ma byc podzielna przez 8, jeśli usuniemy następna cyfrę z prawej strony, to liczba ma byc podzielna przez 7, i tak dalej, aż do ostatniej cyfry, która ma być podzielna przez 1.
Wiązie, pamiętasz może skąd znasz zadanie z usuwaniem cyfr od końca?
Wydaje mi się ono dziwnie znajome:)
mp
Jazz, oczywiście CP swój rekord zawdzięcza kuzynowi (kuzyn mógłby być złośliwy i za każdym razem wskazywać pojedynczą kupkę), jednak nie do przecenienia jest jego własny wkład – przecież mógł sobie postanowić, że w każdej turze będzie zjadał tylko jedno ciasteczko z każdej kupki, przedłużając sobie przyjemność. Tak naprawdę CP i kuzyn grają tutaj w jednej drużynie, mają ten sam cel – minimalizację ilości tur.
Natomiast widzę chyba ciekawszą odmianę tej zabawy: załóżmy, że Orzeł Sam ma pewną ilość ciastek, dajmy na to 51, jak na drugim stoliku. Jak powinien je rozłożyć, żeby Potwór z kuzynem potrzebowali możliwie największej ilości tur do spałaszowania wszystkich? Czy dla każdej liczby mniejszej niż 120 wystarczą 4 tury?
Ciekawa rzecz, gdy tylko uświadomiłem sobie, że moja odpowiedź jest błędna, to niemal natychmiast udało mi się zmniejszyć minima.
Podobnie jak poprzednio napisałbym, że istotnie, tak mogło się zdarzyć. CP mógł zjeść ciasteczka w czterech turach:
Na początku:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
Po pierwszej turze:
1, 2, 3, 4, 5, 6, 7 _, 1, 2, 3, 4, 5, 6, 7
Po drugiej:
1, 2, 3, _, 1, 2, 3, _, 1, 2, 3, _, 1, 2, 3
Po trzeciej:
1, _, 1, _, 1, _, 1, _, 1, _, 1, _, 1, _, 1
I po czwartej reszta.
Natomiast stosy ciasteczek z pierwszego stołu można pochłonąć w trzech turach.
Na początku:
11, 5, 4, 2
Po pierwszej turze:
9, 5, 4, _
Po drugiej:
5, 5, _, _
I po trzeciej reszta.
A stosy ciasteczek z drugiego stołu można zjeść w czterech turach.
Na początku:
17, 16, 11, 4, 2, 1
Po pierwszej turze:
6, 5, _, 4, 2, 1
Po drugiej:
2, 1, _, _, 2, 1
Po trzeciej:
_, 1, _, _, _, 1
I po czwartej reszta.
Dalej obstaję przy tym, że liczba tur zawsze zależeć będzie od kuzyna z wyjątkiem przypadku, gdy CP ma do zjedzenia tylko jedno ciasteczko.
Nadal nie znam (jeszcze) ogólnej strategii.
Pozdrawiam
Pamiętam, że czytałem to zadanie na jakimś blogu angielskim, było zatytułowane: „dividers from 9 to 1” albo podobnie. (poszukam linka, pewnie mam jeszcze gdzieś w ‚linkowni’ swojej )
Pytałem, ponieważ to zadanie przypominałem już kiedyś w Łamiblogu.
Nie podam dokładnych namiarów, bo może ktoś nie znający tej łamigłówki będzie chciał się z nią zmierzyć.
Zapewne pociągnę ten temat w następnym wpisie.
Pozdrav
mp
Ech, postawione sobie samej wczoraj w nocy pytanie okazało się łatwiejsze niż mi się zdawało: już używając 31 ciastek Orzeł Sam może skonstruować taką zagadkę, którą Ciasteczkowy będzie musiał zjadać przez 5 tur. Jestem zawiedziona…
Uwaga Tarii na temat odmiany rozwiązywanego w tym wpisie zadania przypomniała mi wczesną młodość masterminda. Wówczas to modyfikowaliśmy ową grę na różne sposoby. Jedna z ciekawszych odmian polegała na tym, że kodujący nie musiął na początku wymyślać zgadywanego później układu. Mógł to robić w trakcie gry, modyfikując odgadywany układ, tak aby dotychczas udzielane odpowiedzi były zgodne z dotychczas zadawanymi pytaniami. Pozwalało to angażować myślowo obie strony – tak kodującą jak i zgadującą.
Pytanie postawione przez Tarię także wydaje mi się interesujące.
Pozdrawiam,
Jazz
@ Jazz Moje wczorajsze poczucie zawodu wynikało z tego, że uświadomiłam sobie, że dla dowolnej ilości ciastek skonstruowanie zagadki, która wymaga możliwie największej ilości rund jest bardzo proste, natomiast jeśli mamy już zagadkę, zwłaszcza taką, dla której istnieje rozwiązanie o liczbie rund mniejszej niż ilość kupek, znalezienie najlepszego rozwiązania jest dużo trudniejsze. Naszkicowany w moim poście z odpowiedzią ogólny algorytm wymaga ok. n^3 porównań wysokości kupek (n- ilość kupek), a i tak nie jest do końca prawidłowy :/