Męczenie owiec
Pisałem onegdaj o grze Wilki i owce. No i doczekałem się dalszego ciągu – wydawnictwo Egmont podesłało do recenzji grę Owczy pęd. Jak mi się trafi jeszcze jedna barania gra, to awansuję na bacę. Szansa jest spora, bo wymyślacze gier lubią męczyć owieczki. Na portalu BoardGameGeek można znaleźc coś koło trzydziestu przykładów z nahalnymi zwierzątkami, niekoniecznie w roli głównej. A skoro tak dużo, to także nachalnymi
. Zresztą owce inspirują twórców różnych specjalności, a efekty bywają równie urocze jak inspiracja. Przykładem sodomistyczna nowelka o porzucającym żonę dla owcy lekarzu (Gene Wilder) w komedii Woody’ego Allena Wszystko co chcielibyście wiedzieć o seksie, ale baliście się zapytać.
Otworzyłem grę, a z pudełka wyskoczyły śliczne owieczki i proszą, żeby nimi zagrać. Jak tu odmówić. Był akurat Dzień Dziecka, więc postanowiłem zrobić frajdę także sąsiadowi. Zaprosiłem go, postawiłem Smädného Mnicha, zaserwowałem placuszki szparagowe z rydzami i piersią z perliczki (a może kaszankę, już nie pamiętam), wyjęliśmy wszystkie rekwizyty, rozłożyliśmy planszę i do dzieła. Ale sprawa nieprosta – trzeba przeczytać instrukcję, a to bite siedem stron z obrazkami. Nie wiem dlaczego wydawnictwo nie przysłało zamiast instrukcji jakiejś panienki, która by wszystko kusząco objaśniła, a potem popartnerowała. No nic, grunt że gra jest od 10 lat, czyli możemy. Żeby nie było nudno, czytamy i próbujemy grać równocześnie. Taka partia doświadczalna. Sąsiadowi spodobały się owieczki, wszystkie przysunął do siebie, ale w końcu musiał się podporządkować regułom i ulokować je na środku planszy. Nie spodobało mu się natomiast, że grę rozpoczyna osoba, która ma najdłuższe włosy (grać mogą 2, 3 lub 4 osoby). Zaczęliśmy się nawet zastanawiać, czy to nie wystarczy, abym zwyciężył.
Najpierw były przepychanki – jedne owce zachowywały się niegrzecznie, robiąc bałagan w regularnym szyku pod dyktando kostki. Dalsze ruchy wykonywaliśmy wykładając karty – na każdej był obrazek pokazujący, jak należy się ruszyć. Rodzajów ruchów było siedem, kart każdy miał tuzin (każdą wykłada się raz, więc po 12 kolejkach musi nastąpić koniec gry), a faz gry cztery. W pierwszej fazie trzeba było do siebie lgnąć, to znaczy lgnęły owieczki z tego samego teamu. W drugiej pojawiał się Atrakcyjny Roger, a w trzeciej ujawniało się magnetyczne oddziaływanie Czarnej Inez. Owieczki ciągnęło ku obojgu; którą przyciągnęło bliżej, ta zdobywała więcej punktów. Natomiast w czwartej fazie, o zgrozo, stadu zagrażał Szalony Bodzio z nożycami do strzyżenia i trzeba było przed nim uciekać jak najdalej, nawet na Słowację. Po zakończeniu eksperymentu sąsiad powiedział, że gra jest fikuśna. Zgodziłem się z nim i obaj poczuliśmy się jak dzieci, po czym baraszkując przystąpiliśmy do normalnej partii.
To było półżartem i ogólnie. A teraz bardziej serio i też ogólnie.
Grę Shear Panic zaprezentowali na targach gier w Essen w 2005 roku dwaj Szkoci, bracia Gordon i Fraser Lamont. Rok wcześniej obaj założyli wydawnictwo Fragor Games. Owcza gra była ich drugim dzieckiem, które okazało się całkiem udane. Po drobnych zmianach upraszczających reguły zadebiutowała na rynku niemieckim jako Haste Bock? – i chwyciła, a potem wyruszyła na podbój świata. I nic dziwnego, bo jest przede wszystkim grą-zabawką atrakcyjną, a poza tym oryginalną (zmienny poniekąd cel rozgrywki) i nie pozbawioną elementów strategicznych (decydowanie o kolejności wykładania kart z ruchami, wybór przesuwanej owcy i kierunku ruchu). Inna sprawa, co z tej strategii wynika, ale dokonywać wyborów i kombinować można i warto, bo to sprzyja także emocjom.
Łamiblog bez łamigłówki nie byłby sobą, ale z „owczopędną”, zwłaszcza w miarę zwięzłą, jest kłopot. Owczą mam jednak w zapasie, choć uprzedzam, że nie jest taka prosta. Dla zachęty obiecuję nagrodę, łatwo się domyślić jaką. Nagroda zostanie rozlosowana wśród osób, które do poniedziałkowego (9 czerwca) południa zamieszczą w komentarzu poprawne rozwiązanie. Takich komentarzy nie będę oczywiście ujawniał przed zakończeniem konkursu.
Dawno, dawno temu iluś górali umówiło się w ramach przeciwdziałania kułactwu, że w sytuacji, gdyby jeden z nich miał nie mniej, niż połowę owiec, które mają wszyscy razem, to każdy z pozostałych zabierze mu tyle owiec, ile ma sam. A gdyby się zdarzyło, że owce byłyby tylko u dwóch i u każdego tyle samo, to jeden z nich rozkułaczy drugiego. Który którego, o tym miał decydować rzut kostką do gry Owczy pęd 
.
Wiosną przystąpiono do realizacji umowy. Stwierdzono, że u wszystkich górali jest w sumie 128 owiec, po czym nastąpiło siedem rozkułaczeń. Proszę udowodnić (a nie tylko podać przykład lub przykłady), że po siódmym wszystkie owce znalazły się u… jednego kułaka.
Przyznam się bez bicia, że celowo daję nieproste zadanie, bo może nikomu nie uda się go rozwiązać, a wtedy moje stadko się powiększy, czyli owieczki z nagrody trafią do mojej zagrody .
Komentarze
Aby udowodnić, że po siódmym rozkułaczeniu wszystkie owce znalazły się u jednego kułaka, trzeba zapewne skorzystać z tego, że do rozkułaczeń w ogóle musiało dochodzić. Czyli że za każdym razem musiała istnieć jedna taka osoba, którą można było zgodnie z literą prawa pobawić majątku. A więc po kolei…
Aby doszło do 1) rozkułaczenia, musi w 1) kolejce istnieć góral, który ma co najmniej 64 owce. Nie może mieć mniej, bo tak zapisano w warunkach zadania.
64 + … (reszta ma najwyżej 64 do podziału)
Aby doszło do 2) rozkułaczenia, musi w 1) kolejce istnieć góral, który ma co najmniej 32 owce, tak aby po podwojeniu stanu posiadania mógł zająć pozycję lidera.
64 + 32 + … (reszta ma najwyżej 32 do podziału)
Aby doszło do 3) rozkułaczenia, musi w 1) kolejce istnieć góral, który ma co najmniej 16 owiec, tak aby po:
– podwojeniu stanu posiadania w 1) kolejce
– po podwojeniu stanu posiadania w 2) kolejce
mógł zająć pozycję lidera.
64 + 32 + 16 + … (reszta ma najwyżej 16 do podziału)
Aby doszło do 4) rozkułaczenia, musi w 1) kolejce istnieć góral, który ma co najmniej 8 owiec, tak aby po:
– podwojeniu stanu posiadania w 1) kolejce
– podwojeniu stanu posiadania w 2) kolejce
– podwojeniu stanu posiadania w 3) kolejce
mógł zająć pozycję lidera.
64 + 32 + 16 + 8 + … (reszta ma najwyżej 8 do podziału)
Aby doszło do 5) rozkułaczenia, musi w 1) kolejce istnieć góral, który ma co najmniej 4 owce, tak aby po:
– podwojeniu stanu posiadania w 1) kolejce
– podwojeniu stanu posiadania w 2) kolejce
– podwojeniu stanu posiadania w 3) kolejce
– podwojeniu stanu posiadania w 4) kolejce
mógł zająć pozycję lidera.
64 + 32 + 16 + 8 + 4 + … (reszta ma najwyżej 4 do podziału)
Aby doszło do 6) rozkułaczenia, musi w 1) kolejce istnieć góral, który ma co najmniej 2 owce, tak aby po:
– podwojeniu stanu posiadania w 1) kolejce
– podwojeniu stanu posiadania w 2) kolejce
– podwojeniu stanu posiadania w 3) kolejce
– podwojeniu stanu posiadania w 4) kolejce
– podwojeniu stanu posiadania w 5) kolejce
mógł zająć pozycję lidera.
64 + 32 + 16 + 8 + 4 + 2 + … (reszta ma najwyżej 2 do podziału)
Aby doszło do 7) rozkułaczenia, musi w 1) kolejce istnieć dwóch górali, którzy mają po tyle samo owiec i którzy po:
– podwojeniu stanu posiadania w 1) kolejce
– podwojeniu stanu posiadania w 2) kolejce
– podwojeniu stanu posiadania w 3) kolejce
– podwojeniu stanu posiadania w 4) kolejce
– podwojeniu stanu posiadania w 5) kolejce
– podwojeniu stanu posiadania w 6) kolejce
zajmą pozycje liderów ze stanem posiadania po 64 owce.
Z tego wynika, że ci dwaj ostatni górale muszą mieć po 1 owcy.
64 + 32 + 16 + 8 + 4 + 2 + 1 + 1 = 128
***
Przebieg działań:
po 7) rozkuł. 128
po 6) rozkuł. 64 + 64
po 5) rozkuł. 32 + 32 + 64
po 4) rozkuł. 16 + 16 + 32 + 64
po 3) rozkuł. 8 + 8 + 16 + 32 + 64
po 2) rozkuł. 4 + 4 + 8 + 16 + 32 + 64
po 1) rozkuł. 2 + 2 + 4 + 8 + 16 + 32 + 64
stan przed rozkuł. 1 + 1 + 2 + 4 + 8 + 16 + 32 + 64
***
Pozdrawiam
Ola
Panie Marku,
dowód jest, jak mi się wydaje, następujący:
W celach pomocniczych musimy udowodnić tezę, że po każdym „rozkułaczeniu” największa potęga dwójki, przez jaką dzieli się liczba owiec posiadanych przez każdego z górali, zwiększa się o jeden (jeśli naturalnie na skutek rozkułaczenia nie staje się zerowa – wtedy góral „odpada z gry”).
Załóżmy, że mamy do czynienia z równym podziałem między dwóch górali (czyli przypadek szczególny z „losowaniem”). Wtedy każdy ma – powiedzmy – po m owiec, po rozkułaczeniu zaś jeden posiada 0 (jego już nie bierzemy pod uwagę), a drugi 2m (jak widać największa potęga dwójki dzieląca jego stan posiadania zwiększa się o jeden), przy czym naturalnie w tym momencie rozkułaczanie się kończy.
Załóżmy teraz, że podział jest nierówny, to jest jeden góral ma m owiec (gdzie m >= 64 – teraz nawiązuję już do danych liczbowych z zagadki), a „pozostali” (jeden lub więcej) mają n1, n2, itd. owiec (inne przypadki, tzn. bez m >= 64 nas nie interesują, bo wtedy rozkułaczanie jest już skończone). Każdy z „pozostałych” górali ma po rozkułaczeniu 2*n1, 2*n2 itd. owiec, a zatem największa potęga dwójki, która dzieli liczbę jego owiec, wzrosła o 1. Najbogatszy z górali posiadał m = 128 – (n1 + n2 + …) owiec, a teraz ma ich m’ = 128 – (2*n1 + 2*n2 + …) = 128 – 2*(n1 + n2 + …). Ponieważ zawsze 0 <= m, m’ <= 128, to największa potęga dwójki, jaka dzieli m’ (w stosunku do potęgi dwójki, która dzieliła m) wzrasta o 1, gdyż jest ona ograniczona tylko przez odjemnik (czyli prawą stronę wyrażenia; liczba 128 to wystarczająco „zasobny” iloczyn dwójek do wyłączania przed nawias) i właśnie odjemnik jest teraz podzielny przez potęgę dwójki o jeden większą. A zatem wszystkie stany posiadania po rozkułaczeniu dzielą się przez potęgę dwójki o jeden większą, niż przed, jeśli naturalnie któryś z nich nie stanie się podczas tego rozkułaczania zerem.
Na podstawie powyższego łatwo pokazać, że po pierwszym rozkułaczeniu wszystkie niezerowe stany posiadania są podzielne co najmniej przez 2. Podobnie po drugim – co najmniej przez 4. Po trzecim – co najmniej przez 8. I tak dalej, aż do stwierdzenia, że po siódmym rozkułaczeniu, wszystkie niezerowe liczby owiec są podzielne co najmniej przez 128. No tak, ale wszystkich owiec jest 128. A zatem wszystkie należą teraz do jednego.. kułaka (i jest to koniec dowodu).
Rzecz jasna, „algorytm” dla 128 owiec może kończyć się też po mniej, niż 7 „krokach”, co warto zbadać, rozrysowując sobie kilka „rozdań”. Natomiast okazuje się, że więcej niż 7 kroków dla liczby 128 być nie może, czyli mamy ograniczenie logarytmiczne (co przy liczbach 128 i 7 nie mogło nie rzucać się w oczy:-).
Pozdrawiam serdecznie i w razie znalezienia luk, błędów itp., proszę o komentarz!
Każda runda rozkułaczania może być łatwo zobrazowana jeśli liczbę owiec przedstawimy w systemie dwójkowym.
Dla wszystkich „biednych” baców oznacza ona podwojenie liczby owiec, czyli dopisanie jednego zera do liczby. Dla jednego „kułaka” oznacza ona obcięcie wiodącej jedynki. i dopisanie zera (ponieważ pozostanie mu dwa razy tyle ile miał ponad 64 owce – pechowiec z 64 owcami żegna się z całym dobytkiem).
Ponieważ za każdym razem, każdemu z baców dokładamy po zerze, więc po sześciu rundach, wszyscy bacowie którzy jeszcze mają owce mają ich liczbę z sześcioma zerami, a jedyną taką liczbą mniejszą od 128 (=10000000) jest 64 (=1000000). Czyli do ostatniej rundy dojdą dwaj bacowie mający po 64 owce. Po siódmej zostanie już tylko jeden z nich, za to ze wszystkimi owieczkami.
Kluczem do rozwiązania jest fakt, że rund ma być dokładnie siedem. Większość startowych kombinacji liczb owiec kończy się dużo wcześniej. Aby było ich siedem, dokładnie dwóch baców musi mieć nieparzystą liczbę owiec (jedynka na najniższej pozycji – żeby dotrwali do siódmej rundy), a ponadto każda z siedmiu pozycji w zapisie musi zawierać jedynkę u któregoś z baców (aby w każdej rundzie znalazł się kułak).
Serdecznie pozdrawiam z Barcelony,
Jacek
Aby udowodnić tezę zadania przedstawmy liczbę owiec każdego górala w postaci dwójkowej i przed główną częścią dowodu poczyńmy kilka spostrzeżeń:
1. Aby można było przystąpić do rozkułaczenia któregoś górala, liczba jego owiec (w postaci dwójkowej) musi być 7-cyfrowa, bo tylko wtedy może mieć nie mniej, niż połowę wszystkich owiec.
2. Liczba owiec każdego górala, który rozkułacza podwaja się inaczej mówiąc na końcu tej liczby dopisujemy 0. To oznacza, że liczba jedynek w rozwinięciu dwójkowym liczby jego owiec pozostaje bez zmian i jedynie przesuwają się one wszystkie o jedną pozycję w lewo.
3. Liczba owiec górala rozkułaczanego oczywiście zmniejszy się i jeśli przed rozkułaczeniem miał N owiec, to po rozkułaczeniu będzie miał ich N-M, gdzie M jest liczbą wszystkich owiec górali rozkułaczających. Ponieważ M=128-N, to góralowi rozkułaczanemu pozostanie N-(128-N), czyli 2N-128 owiec. To oznacza, że w rozwinięciu dwójkowym liczby jego owiec na końcu (na najmłodszej pozycji) pojawi się zero (to wynika z mnożenia N przez 2) czyli wszystkie jedynki przesuną się w lewo i po odjęciu 128 zniknie najstarsza jedynka. Wniosek: wszystkie jedynki będą przesunięte w lewo a zniknięcie najstarszej jedynki zmniejszy ich liczbę o 1.
Z powyższego możemy bez trudu zauważyć, że wszystkie jedynki we wszystkich liczbach owiec po każdym rozkułaczeniu będą pszesunięte o jedną pozycję w lewo oraz, że zniknie jedynka z najstarszej (siódmej licząc od prawej) pozycji liczby owiec górala rozkułaczanego.
A teraz zasadnicza część dowodu:
4. Ponieważ każde rozkułaczanie zmniejsza liczbę wszystkich jedynek o 1, to 7 rozkułaczeń zmniejszy ich liczbę o 7.
5. Z założenia wynika,że na początku łącznie we wszystkich liczbach musi być 8 jedynek. Po siedmiu rozkułaczeniach pozostanie jedna.
6. Wszystkie jedynki muszą być rozmieszczone tak, aby dla każdej pozycji (od pierwszej najmłodszej do siódmej najstarszej) istniała liczba owiec z jedynką na tej pozycji. Jeśli tak nie będzie, to przed którymś rozkułaczeniem nie będzie spełniony p. 1.
7. Ponieważ na początku musi być 8 jedynek na siedmiu pozycjach, to na jednej pozycji muszą znależć się dwie jedynki. Na początku te dwie jedynki muszą być na pierwszej (najmłodszej) pozycji. Gdyby na początku dwie jedynki znalażły się na conajmniej drugiej pozycji, to suma owiec przewyższała by 128.
8. Dwie jedynki na najmłodszej pozycji po każdym rozkułaczeniu będą przesuwać się o jedną pozycję w lewo, co po szóstym rozkułaczeniu da dwóch górali mających po 64 owce. Pozostali górale już pozbędą się wszystkich owiec.
9. Siódme rozkułaczenie (po rzucie kostką) da nam jednego kułaka ze wszystkimi owcami.
I to by było na tyle,
Jazz_off
Oj, nie liczylbym na to za bardzo – po takiej zachecie (reklamie?) z cala pewnoscia wszyscy czytelnicy rzucą się do pracy, ew. zatrudniajac komputer, sasiada lub nauczyciela matematyki z liceum…
Zadanie nie jest takie trudne. Wystarczy zauważyć, że po pierwszym rozkułaczeniu każdy góral będzie miał parzystą ilość owiec. Liczba owiec każdego górala rozkułaczającego się podwaja, a ponieważ wszystkich owiec jest ilość parzysta (2^7), rozkułaczonemu góralowi pozostanie również parzysta ilość owiec (możliwe, że 0). Po drugim rozkułaczeniu, każdy góral ma liczbę owiec podzielną przez 4 (rozumowanie analogiczne), po trzecim – przez 8, po czwartym 16 itd… W końcu, po siódmym rozkułaczeniu każdy góral ma podzielną przez 2^7 liczbę owiec.
Ergo: jeden ma wszystkie 128, a reszta – 0
Po k-tym rozkulaczeniu (dla 0<=k<=7) kazdy goral ma liczbe owiec, ktora dzieli sie przez 2^k. Dowod indukcyjny:
– niech gorali bedzie n
– niech x(i,k) oznacza liczbe owiec i-tego gorala po k rozkulaczeniach
– poczatek dla k=0 – kazda liczba owiec dzieli sie przez 2^0 czyli przez 1 – oczywiste 😉
– zalozenie indukcyjne:
x(i,k-1) = 2^(k-1)*p dla kazdego 1<=i<=n, gdzie p jest dowolna liczba calkowita. Dowodzimy, ze x(i,k) = 2^k*q, gdzie q jest calkowite.
Niech m takie, ze x(m,k-1) jest maksymalne ze zbioru x(i,k-1) dla 1<=i= 64 (bo moze zajsc rozkulaczenie).
Niech S = 128-x(m,k-1) – suma pozostalych liczb
Mamy x(m,k) = x(m,k-1) – S = x(m,k-1) – 128 + x(m,k-1) = 2*x(m,k-1) – 2^7 = 2*2^(k-1)*p – 2^7 = 2^k*p – 2^7 = 2^k*(p-2^(7-k))
Dla k<=7 2^(7-k) jest calkowite, zatem p-2^(7-k) jest calkowite, zatem x(m,k) = 2^k*c, gdzie c jest calkowite.
Dla i roznego od m mamy: x(i,k) = x(i,k-1) + x(i,k-1) = 2*x(i,k-1) = 2*2^(k-1)*p = 2^k*p.
Czyli po k-tym rozkulaczeniu x(i,k) jest podzielne przez 2^k dla kazdego i.
Po 7 rozkulaczeniu mamy zatem, ze kazde x(i,k) jest podzielne przez 128, a taka sytuacja jest mozliwa wylacznie jesli jedno jest rowne 128, a pozostale sa rowne 0 – z definicji rozkulaczenia suma owiec jest zawsze rowna 128, jak rowniez nigdy zaden kulak nie moze miec ujemnej liczby owiec 😉
Pozdrawiam,
MK
Proponuję dowód szerszego twierdzenia , którego podany problem jest szczególnym przypadkiem (n=7).
Twierdzenie : dla 2expn (czyli 2 do potęgi n-tej) owieczek po n-tym rozkułaczeniu wszystkie owce znajdą się u jednego górala .
Sposób dowodu – przez indukcję .
Dla n=1 , czyli dla dwóch owieczek , musiało być dwóch górali , każdy z jedną owieczką , a po pierwszym rozkułaczaniu (rzut kostką) jeden z nich stał się właścicielem wszystkich dwóch owieczek .
Przyjmijmy , że dla n=k prawdziwe jest twierdzenie , że po k-tym rozkułaczeniu nieznana liczba górali posiadająca 2expk owieczek doprowadzi do stanu , że dokładnie jeden będzie miał wszystkie owce .
Dla n=k+1 liczba owieczek to 2x2expk . Po pierwszym rozkułaczeniu wszyscy górale będą mieli parzystą liczbę owieczek – ci którzy dostali owieczki dlatego , że podwoili stan swojego posiadania , a rozkułaczony dlatego , że suma wszystkich owieczek też jest parzysta (albo ma zero owieczek , co nie przeszkadza w dowodzie).
A teraz co druga owieczka pożera jedną owieczkę – owca kanibal ma wartość dwóch owieczek .
Mamy nieznaną liczbę górali , którzy mają 2expk owieczek-kanibali i jeszcze k rozkułaczeń .
Na mocy twierdzenia pośredniego po kolejnych k rozkułaczeniach dokładnie jeden góral będzie miał wszystkie 2expk owieczki-kanibale o całkowitej wartości 2x2expk owieczek . cbdo
Żywię nadzieję , że dowód jest poprawny , a wszystkie owieczki zaraz po przeprowadzeniu tego dowodu zostały wyplute i czują się dobrze .
Pozdrawiam
AC
Żeby po siódmym rozkułaczeniu któryś góral miał 128 owiec, po szóstym dwóch musiało mieć po 64. Po piątym po 32, po czwartym po 16, po trzecim po 8, po drugim po 4, po pierwszym po 2. na początku albo dwóch po 1, albo jeden mial 1, drugi 65(czyli o 1 więcej niż połowa).
Witam,
To rzeczywiście bardzo przyjemne zadanie. W sam raz na mentalną ucieczkę z zatłoczonego, buchającego żarem autobusu, w którym ludzie jak te owieczki w zagrodzie stłoczeni…
Wracając do zadania. Wystarczy zauważyć, że w kazdym kroku, każdy z górali albo rozkułacza, albo sam jest rozkułaczany. Jeżeli rozkułacza to podwaja ilość posiadanych owieczek. Jeżeli zaś jest rozkułaczany to ilość pozostawionych mu owieczek można opisać wzorem n – [128 – n] = 2n mod 2^7 (przy założeniu, że wcześniej miał n owieczek i n < 128). Zatem niezmiennikiem całej operacji jest: „W k-tym kroku, każdy z górali ma liczbę owieczek podzielną przez 2^k”.
Jeżeli rozkułaczeń było 7 to w siódmym kroku każdy z górali ma liczbę owieczek podzielną przez 128. Czyli wszyscy poza jednym maja zero, a zwycięzca ma ich 127 (bo chyba z jedną owieczkę górale upiekli i zjedli świętując definitywny koniec kułactwa na halach).
Pozdrawiam,
maczek
Podejrzewam, ze znalazlem „modelowe” rozwiazanie, bo jest tak ladne, ze nie chce mi sie wierzyc zeby mozna bylo prosciej…
1. Oznaczmy ilosc owiec danego gorala przez x. Wowczas ilosc owiec po rozkulaczeniu u tego gorala wynosi 2x (mod 128), bo:
– jesli x = 64 (jest co najwyzej jeden taki goral, nazwijmy go Antek), to pozostali gorale maja razem (128 – x) owiec, kazdy z nich podwaja swoj stan posiadania, wiec razem beda mieli (256-2x) owiec, czyli Antek ma reszte = 128 – 256 + 2x = 2x – 128 = 2x (mod 128).
– ostatni przypadek zawiera tez x=64, kiedy po rozkulaczeniu goral ma 0 = 128 (mod 128) owiec.
2. Zatem dany (kazdy) goral po 7 rozkulaczeniach ma 2^7 * x (mod 128) = 128x (mod 128)=0 owiec. (lub 128)
I juz.
Uwagi:
– dziala to dla kazdego gorala wzietego z osobna.
– w ostatnim kroku musialo byc dwoch gorali, kazdy majacy po 64 owce -> jeden dostal zero, drugi 128.
– podejrzewam, ze maksymalna ilosc gorali to 8 (1,1,2,4,8,16,32,64).
Bardzo Fajna gra. Moge ja polecic. A poniewaz juz ja mam, nie musze rozwiazywac zadania 🙂 i moge skupic sie na grze i strategiach, ktorych w niej nie brakuje.
Panie Marku przepraszam za zaśmiecanie Pana skrzynki, ale w poprzednich moich rozwiązaniach jakimś niezrozumiałym dla mnie sposobem zjadło parę linijek przy wklejaniu tekstu. Proszę je usunąć bo po co mają tu zaśmiecać.
Prawidłowe rozwiązanie poniżej
Moje rozwiązanie, trochę pokrętne, ale mam nadzieję, że zrozumiałe:
Z treści wynika, że było siedem rozkułaczeń, po których został tylko jeden góral z owcami. Z tego wniosek, że po szóstym rozkułaczeniu musiało zostać tylko dwóch górali, z których każdy miał po 64 owce. I to właśnie będzie przedmiotem poniższego dowodu, Mało tego, nie będziemy się przyglądać wszystkim góralom, ale stadku tylko jednego, w którym po szóstym rozkułaczeniu te 64 owce muszą się znaleźć.
Na początku był góral i miał pewną liczbę owiec, a owiec tych miał nie więcej niż 127 (128 było wszystkich owiec, a skoro dochodziło do rozkułaczeń, to co najmniej jeden inny góral z co najmniej jedną owieczką musiał istnieć). Wielkość stada naszego górala po każdym rozkułaczeniu zmieniała się następująco:
1/ jeśli miał mniej niż 64 owce, to podczas rozkułaczenia jego stado zwiększało się dwukrotnie
2/ jeśli miał co najmniej 64 owce, to z jego stada odejmowano taką ilość owiec, ile mieli pozostali górale (czyli 128 minus wielkość jego stada)
Jeśli nasz góral miał 64 owce, a nie było to po szóstym rozkułaczeniu, to miał pecha, bo swoje stado musiał rozdzielić pomiędzy pozostałych górali, których było co najmniej dwóch (bo zgodnie z opisem zadania po tym jak było dwóch górali, każdy z 64 owcami, mogło nastąpić tylko jedno, czyli siódme rozkułaczenie)
Wróćmy do tych dwóch zasad zmiany wielkości stada o których było wcześniej. Można je zapisać jako następujące dwa równania iteracyjne:
n = n * 2 , dla n = 64
gdzie n to liczba naturalna z przedziału od 1 do 128
Zanalizujmy teraz jak będzie się zachowywać wielkość stada po każdej iteracji, tudzież zwanej rozkułaczeniem. Załóżmy dla uproszczenia że przed pierwszym rozkułaczeniem wielkość stada (n) jest mniejsza niż 64, więc po pierwszym rozkułaczeniu (oczywiście rozkułaczany będzie inny góral) wielkość stada wyniesie n*2. Załóżmy że nadal jesteśmy poniżej 64 owiec, czyli rozkułaczamy innego nieszczęśnika i wielkość naszego stada wynosi już n*4, czyli n*2^2. Załóżmy że nasz biedny góral przekroczył magiczną barierę 64 owiec i tym razem to on będzie rozkułaczany, w takim wypadku wielkość stada będzie wynosić n*2^3-128, co można zapisać jako n*2^3-2^7, czyli 2^3*(n-2^4).
Z powyższego jasno wynika, że niezależnie od wyżej poczynionych założeń w każdej kolejnej iteracji/rozkułaczeniu wielkość stada staje się pewną wielokrotnością kolejnych potęg liczby 2. Z tego prosty wniosek, że po szóstym rozkułaczeniu wielkość stada musi być wielokrotnością liczby 2^6 czyli 64. Wiemy też, że jest co najmniej dwóch górali, więc wielkość stada naszego górala musi liczyć co najwyżej 127 owiec, a jedyną wielokrotnością liczby 64 w tym przedziale jest ona sama. Czyli mamy dowód na to, że po szóstym rozkułaczeniu górale którzy mają jeszcze owce muszą ich mieć dokładnie 64 i górali tych też będzie dwóch, a który z nich zostanie jedynym kułakiem z owcami po kolejnym rozkułaczeniu (proponuję nazwać go superbacą) zdecyduje rzut kostką do gry Owczy Pęd (oby nie rzut ciupaszką 😉
Pozdrawiam
Nie wiem co się dzieje, wklejam dwa równania, a później w poście pojawia się tylko jedno. dziwy oj dziwy. Próbuję po raz ostatni:
Moje rozwiązanie, trochę pokrętne, ale mam nadzieję, że zrozumiałe:
Z treści wynika, że było siedem rozkułaczeń, po których został tylko jeden góral z owcami. Z tego wniosek, że po szóstym rozkułaczeniu musiało zostać tylko dwóch górali, z których każdy miał po 64 owce. I to właśnie będzie przedmiotem poniższego dowodu, Mało tego, nie będziemy się przyglądać wszystkim góralom, ale stadku tylko jednego, w którym po szóstym rozkułaczeniu te 64 owce muszą się znaleźć.
Na początku był góral i miał pewną liczbę owiec, a owiec tych miał nie więcej niż 127 (128 było wszystkich owiec, a skoro dochodziło do rozkułaczeń, to co najmniej jeden inny góral z co najmniej jedną owieczką musiał istnieć). Wielkość stada naszego górala po każdym rozkułaczeniu zmieniała się następująco:
1/ jeśli miał mniej niż 64 owce, to podczas rozkułaczenia jego stado zwiększało się dwukrotnie
2/ jeśli miał co najmniej 64 owce, to z jego stada odejmowano taką ilość owiec, ile mieli pozostali górale (czyli 128 minus wielkość jego stada)
Jeśli nasz góral miał 64 owce, a nie było to po szóstym rozkułaczeniu, to miał pecha, bo swoje stado musiał rozdzielić pomiędzy pozostałych górali, których było co najmniej dwóch (bo zgodnie z opisem zadania po tym jak było dwóch górali, każdy z 64 owcami, mogło nastąpić tylko jedno, czyli siódme rozkułaczenie)
Wróćmy do tych dwóch zasad zmiany wielkości stada o których było wcześniej. Można je zapisać jako następujące równania iteracyjne:
n = n * 2 , dla n = 64
gdzie n to liczba naturalna z przedziału od 1 do 128
Zanalizujmy teraz jak będzie się zachowywać wielkość stada po każdej iteracji, tudzież zwanej rozkułaczeniem. Załóżmy dla uproszczenia że przed pierwszym rozkułaczeniem wielkość stada (n) jest mniejsza niż 64, więc po pierwszym rozkułaczeniu (oczywiście rozkułaczany będzie inny góral) wielkość stada wyniesie n*2. Załóżmy że nadal jesteśmy poniżej 64 owiec, czyli rozkułaczamy innego nieszczęśnika i wielkość naszego stada wynosi już n*4, czyli n*2^2. Załóżmy że nasz biedny góral przekroczył magiczną barierę 64 owiec i tym razem to on będzie rozkułaczany, w takim wypadku wielkość stada będzie wynosić n*2^3-128, co można zapisać jako n*2^3-2^7, czyli 2^3*(n-2^4).
Z powyższego jasno wynika, że niezależnie od wyżej poczynionych założeń w każdej kolejnej iteracji/rozkułaczeniu wielkość stada staje się pewną wielokrotnością kolejnych potęg liczby 2. Z tego prosty wniosek, że po szóstym rozkułaczeniu wielkość stada musi być wielokrotnością liczby 2^6 czyli 64. Wiemy też, że jest co najmniej dwóch górali, więc wielkość stada naszego górala musi liczyć co najwyżej 127 owiec, a jedyną wielokrotnością liczby 64 w tym przedziale jest ona sama. Czyli mamy dowód na to, że po szóstym rozkułaczeniu górale którzy mają jeszcze owce muszą ich mieć dokładnie 64 i górali tych też będzie dwóch, a który z nich zostanie jedynym kułakiem z owcami po kolejnym rozkułaczeniu (proponuję nazwać go superbacą) zdecyduje rzut kostką do gry Owczy Pęd (oby nie rzut ciupaszką 😉
Pozdrawiam
Hmmm…. Alez to zadanie przeciez nie jest az tak trudne. I chyba problem nie jest do konca odpowiednio sformulowany.
Zacznijmy:
jest bardzo wiele mozliwosci, w ktorych rozkulaczanie albo sie nie zacznie, albo skonczy po mniej niz 7 „rundach” sytuacja w ktorej jeden baca ma wszystkie owce a reszta nie ma zadnych (np. dla trzech bacow rozklad 46, 42, 40 rozkulaczanie nawet sie nie zacznie – zaden z nich nie ma nie mniej niz polowe). Zatem (udowodnione przez kontr-przyklad) NIE mozna powiedziec ze „dla wszystkich mozliwych rozkladow liczby owiec” po 7 rundach rozkulaczanie skonczy sie tragiczna w skutkach pomylka komunizmu … czyli ze jeden baca zgarnie wszystko.
Wiec sformulowanie zadania powinno jednak brzmiec „powiedz ilu na poczatku bylo bacow i po ile owieczek mieli”
I to jest juz rozwiazywalne – oto historia (od konca):
7. 128
6. 64 64
5 32 32 64
4 16 16 32 64
3 8 8 16 32 64
2 4 4 8 16 32 64
1 2 2 4 8 16 32 64
1) Rozkułaczeń było siedem, czyli było osiem kolejnych stanów, w których każdy góral posiadał określoną liczbę owiec (albo nie posiadał wcale),
2) Liczbę górali oznaczam jako n,
3) Oznaczmy xi jako ilość owiec, którą posiada góral (o numerze porządkowym i) w OSTATNIM (ósmym) stanie.
Zatem stan nr 8 ma postać:
[ (x1) (x2) (x3) (x4) … (xn) ]
4) xi może być równe 0 albo może być liczbą naturalną z przedziału od 1 do 128,
5) Przyglądamy się stanowi nr 8 i decydujemy, który z górali był ostatnio rozkułaczony. Niech będzie to góral nr 1. Zatem każdy z pozostałych górali, w stanie nr 7, będzie miał (xi/2) owiec. Dokonajmy obliczeń, które umożliwią nam wyrazić liczbę owiec pierwszego górala w stanie nr 7:
x’1 – liczba owiec pierwszego górala w stanie nr 7
x1 = x’1 – (x2/2 + x3/2 + x4/2 + … + xn/2)
x1 = x’1 – ( (1/2) * suma(xi) – (1/2) * x1)
x1 = x’1 – ( (1/2) * 128 – (1/2) * x1)
po przekształceniach:
x’1 = (1/2)*x1 + 64
Stan nr 7 ma zatem postać:
[ ((1/2)*x1 + 64) (x2/2) (x3/2) (x4/2) … (xn/2) ]
6) Jeśli oznaczymy stan jako:
[ (x’1) (x’2) (x’3) (x’4) … (x’n) ]
To stan poprzedni w stosunku do niego będzie miał postać:
[ (x’1/2) (x’2/2) (x’3/2) (x’4/2) … ((1/2)*x’i + 64) … (x’n/2) ]
Tu ważna uwaga: ilość owiec równą ((1/2)*x’i + 64) będzie miał tylko ten góral, który został właśnie rozkułaczony (nie wnikamy, co będzie jak ten sam góral będzie rozkułaczany cały czas, a co jak za każdym razem inny itp.).
Proszę też zauważyć, że nie ma znaczenia wg której z dwóch reguł (podanych w treści zadania) góral został rozkułaczony: stan poprzedni zawsze będzie się wyrażał takimi samymi wzorami jak te wyżej podane. Jeśli górali było dwóch i każdy miał 64 owce, to przyrównując ilość owiec rozkułaczonego górala do 64 otrzymamy, że x’i=0, a ilość owiec drugiego górala to 128.
7) Dla porównania, podaję dwie alternatywne wersje stanu nr 6.
Gdy rozkułaczony został ponownie góral nr 1:
[ ((1/4)*x1 + 96) (x2/4) (x3/4) (x4/4) … (xn/4) ]
Gdy rozkułaczony został góral nr 2:
[ ((1/4)*x1 + 32) ((1/4)*x2 + 64) (x3/4) (x4/4) … (xn/4) ]
Otrzymamy powyższe wzory gdy przyjmiemy stan nr 7 za następny i zastosujemy przekształcenia opisane w punkcie nr 6.
8 ) Na tej zasadzie otrzymujemy postać stanu nr 1:
[ ((1/128)*x1 + p1) ((1/128)*x2 + p2) ((1/128)*x3 + p3) … (xi/128) (x(i+1)/128) … (xn/128) ]
pi – pewna liczba naturalna, której wartość zależy od tego kiedy i ile razy dany góral został rozkułaczony. Jeśli góral nie był rozkułaczony ani razu, to pi=0.
9) Jak napisałem w punkcie nr 3, xi to ilość owiec w stanie ósmym. Spoglądając na postać stanu pierwszego dostrzeżemy, że nie może być inaczej: musi być tak, że jeden góral miał w stanie ósmym 128 owiec. Gdybyśmy bowiem podstawili za xi wartości inne niż 0 albo 128, to oznaczałoby, że ilość owiec któregoś górala w stanie nr 1 nie jest liczbą całkowitą (a większych niż 128 podstawić nie możemy). A skoro suma owiec w każdym stanie ma być równa 128, to oznacza to, że w stanie ósmym tylko jeden góral ma 128 owiec, a reszta nie ma wcale.
Rozkułaczenie siódme musi być rozkułaczeniem ostatnim, bo nie ma takich wartości xi, które spełnią warunki zadania dla hipotetycznego stanu nr 0:
[ ((1/256)*x1 + p1) ((1/256)*x2 + p2) ((1/256)*x3 + p3) … (xi/256) (x(i+1)/256) … (xn/256) ]
Dowód przeprowadziłem, mam nadzieję, bez pomyłek. Myślę, że można przeprowadzić analogiczny dowód rozpatrując kolejne stany od początku, a nie od końca jak tutaj. Wybrałem jednak tą wersję, bo uznałem, że łatwiej ją będzie opisać, a zwłaszcza ostatnie wnioski doprowadzające ostatecznie do dowodu.
Pomyślałem, że należałoby uzupełnić dowód o pewną uwagę. Otóż wartość pi w stanie nr 0 nie musi być liczbą naturalną. Mimo to, i tak w stanie nr 0 nie ma takich wartości xi, które spełniłyby warunki zadania.
Poza tym, pi jest równe 1 w stanie nr 1 dla górala, który został rozkułaczony tylko raz, między stanem siódmym a ósmym.
Mam nadzieję, że te zależności są czytelne i da się je dostrzeć spoglądając na schemat z punktu nr 6.
A co sie dzieje w sytuacji, gdy u czterech baców są po 32 owce?
Michale, oczywiście nic się nie dzieje, bo nie ma kogo rozkułaczać.
mp
Znalazłem prostszy , nieindukcyjny dowód (bez owczego kanibalizmu) , chociaż również oparty na spostrzeżeniu z dowodu indukcyjnego .
Otóż po pierwszym rozkułaczeniu wszyscy górale , którzy mają owieczki – mają ich parzystą ilość . Ci , którzy dostali ponieważ podwoili stan swojego posiadania , a rozkułaczony (jeżeli coś mu zostało) ponieważ całkowita liczba owieczek jest parzysta .
Po drugim rozkułaczaniu wszyscy górale , którzy mają owieczki – mają ich liczbę podzielną przez 4 . Ci którzy dostali ponieważ podwoili parzystą liczbę posiadanych owieczek , a rozkułaczony (jeżeli coś mu zostało) ponieważ całkowita liczba owieczek jest podzielna przez 4 .
I tak dalej do szóstego rozkułaczenia .
Po szóstym rozkułaczeniu wszyscy górale , którzy mają owieczki – mają ich liczbę podzielną przez 64 . Aby mogło dojść do siódmego rozkułaczenia musi być ich co najmniej dwóch , a ponieważ liczba posiadanych przez nich owieczek jest podzielna przez 64 to jest ich dokładnie dwóch i obaj posiadają po dokładnie 64 owieczki .
W siódmym rozkułaczeniu na pewno rzucają kostką z wiadomym wynikiem – jeden z nich zostaje superkułakiem . cbdo
Pozdrawiam
AC
Aby proces rozkułaczania mógł odbyc się w 7 etapach, muszą być spełnione dwa podstawowe warunki:
– liczba posiadaczy owiec musi być od 2 do 8
– jeden z nich musi mieć na początku 64 lub więcej owiec
Jeżeli liczbę owiec należących do kazdego właściciela przedstawimy jako sumę potęg liczby 2, to 7 rozkułaczeń może zajść tylko wtedy, gdy żadna z tych potęg nie występuje więcej niż dwa razy. Ponadto zerowa potęga dwójki musi wystąpić dokładnie dwa razy, czyli muszą być dokładnie dwie liczby nieparzyste. Po 6 rozkułaczeniach, ci co zaczynali od nieparzystej liczby owiec, będą mieli po 64 owce i siódme rozkułaczenie spowoduje, że u jednego znajdą sie wszystkie owce.
Dowód na to, że wszystkie 128 owce po siedmiu rozkułaczeniach znajdą się u jednego górala można oprzeć na pomyśle podziału na połowy odcinka ponumerowanego liczbami od 0 do 128.
Pierwszym punktem podziału będzie 64, w drugim podziale otrzymujemy punkty o numerach 32 i 96. Dalej postępując w ten sposób dochodzimy do siódmego podziału, któremu odpowiadają punkty: 1,3,5,…,127.
Zauważmy, że po siódmym podziale wszystkie punkty odcinka 0-128 (oprócz krańcowych 0 i 128) są wyznaczone. Punkty 0 i 128 można potraktować jako miejsca zerowego podziału, które bezpośrednio wyznaczają rozwiązanie.
Wiedząc, że siedem podziałów odcinka wystarcza do wyznaczenia każdej liczby odcinka 0-128 wiemy tym samym, że siedem rozkułaczeń wystarczy, aby wszystkie 128 owce znalazły się u jednego górala.
Oczywiście przypadek dla 128 owiec można uogólnić na 2^n owieczek z n-rozkułaczeniami.
………………………………………………………………
Wspomnianej komedii Woody’ego Allena nie znam, ale widziałem film, w którym w jednej ze scen bohater grający rolę taksówkarza wspomina miłe chwile spędzone z owieczką:
http://pl.youtube.com/watch?v=dCKxro6s7e8
Pozdrawiam
Nie znałem. Benigni jest świetny.
A tu równie znakomity Gene Wilder na pierwszej randce z owieczką
http://www.youtube.com/watch?v=tzr5Cubph9Y
mp
Czy ta zagadka była trudna? Moim zdaniem nie, a przynajmniej nie dla rozwiązującego. Podejrzewam natomiast, że trudna to ona może być dla Pana Marka, który będzie musiał najpierw czytać wszystkie wypociny 😉 , a potem jeszcze oceniać ich prawidłowość. To dużo bardziej skomplikowana i zdecydowanie bardziej pracochłonna sprawa niż weryfikacja rozwiązań łamigłówek, w których wychodzi konkretny wynik.
Zamieszczane dotychczas zadania zazwyczaj posiadały tylko jedno możliwe rozwiązanie. Jeśli było ich więcej, to i tak co najwyżej kilka, a wszystkie, założę się, dobrze znane Autorowi. A nawet gdyby tak nie było (jak raz kiedyś w przypadku Hexa-Trexu, w którym trochę się rozmnożyły), to i tak były stosunkowo łatwe do zweryfikowania.
Tutaj jest całkiem inaczej. Po pierwsze: liczba rozwiązań jest nieograniczona (co najwyżej pomysłowością rozwiązujących). Po drugie: na pewno wszystkie nie są znane. Po trzecie: nie ma prostej, ogólnej metody na sprawdzenie poprawności i trzeba wgryźć się w tok rozumowania (co też ten piszący miał na myśli? 😉 ).
Także, Panie Marku, wydaje mi się, że zafundował Pan sam sobie niezłą łamigłówkę. Szczerze współczuję i życzę dużo siły.
Pozdrawiam
AB
Dane: górale mają razem 128 owiec, rozkułaczanie następowało 7 razy
Warunki początkowe:
A) góral posiada mniej niż połowę, czyli od 1 do 63 owiec: jego stan posiadania oznaczymy ‚m’ (mało).
B) góral posiada nie mniej niż połowę, czyli 64 lub więcej owiec: jego stan posiadania oznaczymy ‚d’ (dużo).
Dla tych warunków początkowych mogą zajść następujące przypadki rozkułaczania:
A1) po pierwszej rundzie rozkułaczania góral będzie posiadał 2*m owiec i może wówczas wystąpić warunek A) lub B). Załóżmy, że wciąż występuje warunek A), wówczas po kolejnych rozkułaczeniach góral będzie posiadał 2*2*…*m owiec, czyli 2[R]*m owiec.
Oznaczenie 2[R] to R-ta potęga liczby 2.
W takiej sytuacji po siódmym rozkułaczeniu góral bedzie miał 2[7]*m=128*m owiec. Jak widać taka możliwość spełniona jest tylko wtedy, jeśli m=1 (bo wszystkich owiec było razem 128), na koniec góral bedzie miał wtedy wszystkie 128 owiec.
W tym przypadku została do rozpatrzenia sytuacja, kiedy po którymś rozkułaczeniu góral ma nie mniej niż połowę wszystkich owiec. Nazwę tę sytuację A2 i wrócę do niej później.
B1) góral ma 64 lub więcej owiec, czyli d=64+n. Pozostali górale mają w sumie 64-n owiec i tyle otrzymają po pierwszym rozkułaczeniu, czyli naszemu góralowi zostanie 64+n-(64-n)=2*n owiec i znowu może wystąpić warunek A) lub B). Załóżmy tym razem, że wciąż występuje warunek B), więc wciąż góral będzie rozkułaczany. Po drugim rozkułaczeniu zostanie mu więc: 2*n1 owiec. Można zapisać więc dla górala:
na początku: 64+n
po pierwszym: 2*n = 64+n1 (z tego n1=2*n-64)
po drugim: 2*n1 = 2*(2*n-64) = 64+n2 (z tego n2 = 2*(2*n-64)-64
po trzecim: 2*n2 = 2*(2*(2*n-64)-64)
…
po siódmym: 2*n6 = 2*(2*(2*(2*(2*(2*(2*n-64)-64)-64)-64)-64)-64)-64
Jeśli to przekształcimy (ale nie będę tym zaciemniał tutaj dowodu), to otrzymamy, że po kolejnym rozkułaczeniu R, góral posiada: 2[R]*(n-2[R-1]+1).
W takiej sytuacji po siódmym rozkułaczeniu góral bedzie miał 2[R]*(n-2[R-1]+1) = 128(n-63) owiec. Jak widać taka możliwość spełniona jest tylko wtedy, jeśli n=63 (wtedy góralowi na koniec nie zostało nic) lub n=64 (wtedy góral na koniec ma wszystkie 128 owiec).
Dla tego warunku została nam jeszcze sytuacja, że po którymś rozkułaczeniu góral posiada mniej niż połowę owiec. Wówczas wystąpi rozpatrywany już przypadek A1, ale oczywiście tylko pozostałe kilka rozkułaczeń. Zakładając, że X razy góral miał nie mniej niż połowę owiec, zapiszę to następująco:
po X-owym rozkułaczeniu: 2[X]*(n-2[X-1]+1) = m
a po kolejnych, aż do siódmego: 2[7-X]*m = 2[7-X]*2[X]*(n-2[X-1]+1) = 2[7]*(n-2[X-1]+1) = 128(n-2[X-1]+1)
widać więc, że na koniec góral może mieć wszystkie 128 owiec, lub żadnej.
I teraz powracam do zaniechanej drugiej sytuacji, którą nazwałem A2, aby o niej nie zapomnieć. Mamy tu następujący przypadek:
po X-owym rozkułaczeniu: 2[X]*m = 64+n, (z tego n = 2[X]*m-64
a po kolejnych, aż do siódmego: 2[7-X]*(n-2[7-X-1]+1) = 2[7-X]*(2[X]*m-64-2[6-X]+1) = 2[7-X]*2[X]*m+2[7-X]*(-64-2[6-X]+1) = 2[7]*m+2[7-X]*(-64-2[6-X]+1) = 128*m+2[7-X]*(-64-2[6-X]+1)
Widać więc, nie próbując nawet tego liczyć, że na koniec góral mógłby mieć wszystkie 128 owiec, lub żadnej.
Oczywiście może następować mieszanie się tych przypadków A) i B) rozkułaczania, ale jak widać zawsze po siódmym rozkułaczeniu istnieją tylko dwie możliwości posiadania owiec przez górala. Albo ma on wszystkie owce, albo nie ma żadnej, czyli wszystkie owce musi mieć inny góral. Zawsze więc wszystkie owce znajdą się u jednego tylko górala.
Jeśli ktoś chciałby być tym góralem, niech policzy ile powienien mieć owiec przed rozpoczęciem rozkułaczania, aby zgarnąć wszystkie, a jeśli nie chce mu się liczyć niech spróbuje 1 lub 64 🙂
Podpowiedź dla górala miała być oczywiście 1 lub 65 🙂
Pozwolę sobie zamieścić dwa dowody. Dlaczego – wyjaśniam na końcu tego komentarza.
…………………………………..
Dowód nr 1.
Typowo matematyczny, prosty i nieco nudny ;-).
1.
Zakładając, że dany baca przed kolejnym rozkułaczeniem ma X owiec, sprawdźmy ile może mieć po.
Wariant A: jeśli rozkułaczono kogoś innego, to otrzyma on tyle owiec ile sam miał wcześniej, a więc łącznie ma teraz 2X.
Wariant B: jeśli padło na niego, to każdy z pozostałych zabierze mu tyle, ile tamten posiadał, czyli wszyscy razem zabiorą mu 128-X owiec. Naszemu bacy pozostanie więc:
X-(128-X) = 2X-128 = 2(X-64).
2.
Tw. pomocnicze:
Dla każdego n będącego liczbą całkowitą (w skrócie będę dalej pisać LC) od 1 do 7 włącznie, istnieje taka LC k, że po n-tym rozkułaczeniu dowolny baca będzie mieć Xn = k*2^n owiec.
Dowód metodą indukcji matematycznej:
Dla n=1 zostało to już pokazane w punkcie 1. (baca będzie mieć X*2^1 lub (X-64)*2^1 owiec, czyli k wyniesie w tej sytuacji X lub X-64).
Krok indukcyjny:
Z: Xn = k*2^n,
T: X(n+1) = m*2^(n+1),
gdzie k,m – dowolne LC, n – LC od 1 do 6 (6, a nie 7, ponieważ udowadniamy dla n+1).
D:
Opierając się na spostrzeżeniu z punktu 1. po kolejnym, n+1 rozkułaczeniu baca może mieć albo
2*Xn = 2*k*2^n = k*2^(n+1) owiec,
albo 2*(Xn-64) = 2*(k*2^n-2^6) =
= [k-2^(6-n)]*2^(n+1) owiec. W pierwszym przypadku m = k, w drugim m = k-2^(6-n), w obydwu jest to LC, bo n nie przekracza 6.
Teza lematu została zatem udowodniona.
(Aby tego dowieść, nie trzeba bylo stosować indukcji, ale tak mi było najłatwiej pod względem formalnym.)
3.
Wszystkich owiec jest 128. W każdej chwili ich liczba u każdego z górali musi się więc zawierać w przedziale od 0 do 128. Biorąc jednak pod uwagę to, że z udowodnionego w punkcie poprzednim twierdzenia wynika wprost, iż po ostatnim, siódmym rozkułaczeniu liczba ta będzie podzielna przez 128 (2^7), oznacza to, że pozostają tylko dwie krańcowe możliwości: albo 0, albo 128 (pośrednie odpadają). A zatem zwycięzca bierze wszystko, a pozostałym przypadnie po liczbie „okrągłej” 😉 .
Co było do udowodnienia.
…………………………………..
Dowód nr 2.
W dużej części również matematyczny, ale trochę bardziej „łamigłówkowy”, dość trudny do opisania (dlatego pozwolę sobie na skróty), ale za to może mniej szablonowy. Przeprowadzony metodą „od tyłu”.
Aby się nie myliło z poprzednim, numerację kolejnych punktów rozpocząłem od 11.
11.
Na wstępie zauważmy, że:
11a. Jeśli jakiś baca zostanie rozkułaczony kompletnie, to nie ma już szans na „powrót do gry”.
11b. Stracić wszystkie owce można wyłącznie wtedy, gdy posiadamy połowę z nich (64). Wtedy reszta ma łącznie również 64 i gdy każdy z pozostałych zabierze tyle, ile sam posiada, nam nie pozostanie nic.
11c. Aby zagarnąć wszystkie owce, trzeba również chwilę wcześniej mieć połowę z nich.
11d. Ponieważ jednak posiadanie połowy zazwyczaj oznacza utratę wszystkich, sytuacja z punktu poprzedniego jest możliwa wyłącznie wtedy, gdy na „placu boju” pozostanie dwóch ostatnich górali, każdy z 64 owcami. Wówczas jeden zgarnie wszystkie, a drugi wszystkie straci.
12.
Jak widać z opisanych wyżej spostrzeżeń „magiczną” liczbą jest 64. Zastanówmy się jakie drogi do niej prowadzą.
Możliwe są dwie: albo rozkułaczając kogoś (czyli mając wcześniej 32 owce i dostając drugie tyle), albo będąc samemu rozkułaczanym (czyli mając 96 owiec – reszta ma wówczas 32 i tyleż nam zabiera). Zatem pierwszą z tych liczb otrzymujemy poprzez dzielenie przez 2, a drugą poprzez dzielenie przez 2 i dodanie 64. Są to operacje odwrotne do działań pokazanych w dowodzie nr 1, punkt 1 (tam było 2X lub 2(X-64) ) i są prawidłowe nie tylko dla liczby 64, ale również każdej innej.
13.
Narysujmy drzewo. W wierzchołku umieszczamy liczbę 64 – to będzie pierwszy poziom tego drzewa. Z tego wierzchołka wychodzą dwie gałęzie, na końcach których są liczby 32 i 96 – to drugi poziom. Z obydwu tych węzłów wychodzą kolejne pary gałęzi z liczbami 16 i 80 oraz 48 i 112 tworzącymi trzeci poziom. Dalej konstruujemy czwarty poziom (8, 72, 40, 104, 24, 88, 56, 120) i tak dalej aż do siódmego. Oczywiście nie trzeba wyliczać i rysować całości. Wystarczy tyle co opisałem, resztę można sobie wyobrazić. To drzewo pokazuje wszystkie możliwe drogi dojścia do 64 owiec. Trzeba teraz zauważyć kilka interesujących jego cech opisanych w następnych punktach.
14.
Pierwsze spostrzeżenie to fakt, że każda z tych liczb jest mniejsza od 128. Weźmy pod uwagę gorszy przypadek, czyli liczby powstające przez dzielenia poprzednika przez 2, a następnie dodanie 64. Aby liczba taka była nie mniejsza od 128, to przed dodawaniem musiałaby być nie mniejsza niż 64, a przed dzieleniem nie mniejsza niż 128. A więc kółko się zamyka. Żeby mieć 128 lub więcej, to trzeba wcześniej mieć przynajmniej 128. A zaczynamy przecież od 64. Z liczbami, dla których ostatnią operacją było samo dzielenie sprawa jest jeszcze prostsza. Wszystkie będą też oczywiście większe od 0.
15.
Pierwszy poziom drzewa, jak już napisałem, tworzy jedna liczba 64. Drugi poziom – dwie liczby, trzeci cztery. Każdy następny dwukrotnie więcej niż poprzednio. Ostatni, siódmy poziom tworzą zatem 64 liczby, a wszystkich, łącznie z wierzchołkową, będzie 127. Dalej wykażę, że wszystkie są różne.
16.
Najpierw zauważmy, że muszą się od siebie różnić liczby znajdują się na innych poziomach. Wynika to z faktu, że liczby na niższym poziomie powstają przez dzielenie przez 2 liczb na bezpośrednio wyższym. A stąd zmienia się ich podzielność przez potęgi dwójki. Do tego dzielenia może dochodzić dodanie 64, ale z interesującego nas punktu widzenia (wykładnik tych potęg nie przekracza 6) jest to operacja neutralna. A w związku z tym mamy: 64 z poziomu pierwszego jest podzielna (bo równa) przez 2^6. Liczby poziomu drugiego będą podzielne przez 2^5, ale przez 2^6 już nie. Podobnie liczby z poziomu trzeciego będą się dzielić przez 2^4, ale nie przez 2^5 itd. Na ostatnim, siódmym poziomie będą liczby nieparzyste. Punkt ten przy okazji pokazuje, że nie bedzie żadnych problemów z podzielnością – wszystkie liczby są całkowite.
17.
Aby wykazać, że muszą się między sobą różnić również liczby znajdujące sie na tym samym poziomie naszego drzewa, trzeba zacząć od dość oczywistej sprawy: Liczby powstałe na skutek dzielenia i dodania 64 będą od 64 większe, natomiast powstałe w wyniku samego dzielenia – mniejsze (poprzednik jest mniejszy o 128). A zatem żadna z liczb otrzymanych pierwszą metodą nie może się równać otrzymanej metodą drugą. Nie mogą być też sobie równe liczby otrzymane tym samym sposobem, bo to oznaczałoby, że ich poprzedniki musiały być równe. I znowu, podobnie jak w p.14., kółko się zamyka: aby była równość, musi ona wystąpić już wcześniej, a od momentu gdy mamy przynajmniej dwie liczby (poziom 2), to są one różne.
18.
Pora na podsumowanie obserwacji opisanych w punktach 14.-17. Mamy 127 różnych liczb całkowitych dodatnich i mniejszych od 128. A zatem w skład drzewa wchodzą wszystkie liczby z interesującego nas przedziału, tzn. wszystkie potencjalne liczby owiec jakie mogły się znaleźć na początku u każdego z górali.
19.
Wniosek końcowy jest taki, że niezależnie od tego, ile dany baca miał owiec na starcie, najpóźniej po szóstym rozkułaczeniu przypadnie mu „magiczna” liczba 64. A to, czy będzie ona szczęśliwa, czy pechowa, będzie już zależało od rzutu kostką do gry „Owczy pęd”. 😉 Tak czy inaczej w wyniku siódmego rozkułaczenia wszystko zyska lub wszystko straci, a więc wszystkie owce znajdą się tylko u jednego bacy.
Co było do udowodnienia.
…………………………………..
Dlaczego zamieściłem aż dwa dowody?
Po pierwsze: ze złośliwości – aby Pan Marek miał więcej do czytania. 😉
Po drugie: muszę nadrabiać zaległości (dawno mnie tu nie było). 😉
Po trzecie: dwa dowody, to pewnie dwa losy w konkursie. 😉
🙂 , 🙂 , 🙂
Tyle żartem, a teraz na poważnie.
Pierwszy dowód jest krótszy, prostszy, bardziej zrozumiały, łatwiejszy do weryfikacji i przez to bezpieczniejszy.
Jednak drugi (który nawiasem mówiąc chronologicznie dla mnie był pierwszym) ma również swoje zalety. I nie chodzi tu o to, czy jest ciekawszy lub mniej szablonowy, bo to rzecz względna. Natomiast w przeciwieństwie do pierwszego pozwala zauważyć wiele, moim zdaniem interesujących, prawidłowości.
Wymienię tu kilka z nich:
1. Aby mogło być 7 rozkułaczeń musi istnieć baca (czyli w praktyce dwóch) o nieparzystej początkowej liczbie owiec. W przeciwnym przypadku, o ile układ się nie ustabilizuje (czyli u każdego znajdzie się mniej niż połowa owiec i rozkułaczanie się zatrzyma), wszystkie owce znajdą się u jednego z górali wcześniej.
2. Nie są możliwe układy oscylujące, tzn. że dwóch lub więcej baców będzie się nawzajem rozkułaczać bez końca. Możliwe są tylko dwie sytuacje: albo układ się ustabilizuje, albo jeden zgarnie wszystkie. Przy dwóch góralach możliwa jest tylko ta druga sytuacja.
3. Im początkowa liczba owiec u danego bacy znajduje się niżej na drzewie, tym większą ma on szansę stracić wszystkie.
4. Szansę na przejęcie wszystkich owiec mają tylko ci górale, których początkowa liczba owiec znajduje się najwyżej na drzewie.
5. Jeżeli tych, których początkowe liczby owiec znajdują się w danej sytuacji najwyżej na drzewie jest więcej niż dwóch to nikt nie przejmie wszystkiego.
6. Podobnie będzie, gdy na którymś z pozostałych (niższych) poziomów będą początkowe liczby owiec więcej niż jednego bacy.
Itd… itd… można by jeszcze długo wymieniać.
W zrozumieniu tych mechanizmów bardzo pomaga układ dwójkowy. Po konwersji liczby owiec danego bacy do postaci binarnej można bardzo szybko zobaczyć, co go czeka. Sam dowód nr 2 jest również wówczas dużo prostszy.
A na koniec jeszcze ogólna refleksja natury nieco filozoficznej:
Nie należy na siłę dążyć do sprawiedliwości, bo ta sprawiedliwość szybko może przeobrazić się w „sprawiedliwość”.
Jak wiadomo wszyscy są równi, ale niektórzy równiejsi.
Pozdrawiam
AB
Pozdrowienia dla Robert_C 🙂