Hrpice

Spajam dve petice u jednu gomilu i uzimam 9 i ostaju 3 gomile: 1 1 1

U stvari sve skupljam u jednu gomilu i uzimam sve osim jedne.

:-)

Salu na stranu, Mihajlo, ako tako nastavis kako si krenuo dobio si partiju.

Pa onda u prvom slucaju gubis, posto ja spajam prve dve gomile i uzimam sve iz njih, tako da ostaje 1.

Bojan Bašić: obrisan nepotreban citat

[Ovu poruku je menjao Bojan Basic dana 07.12.2003. u 01:33 GMT]

... a da objavite pravila... ko poslednji vuče - gubi, je li?
Recimo - na potezu sam, ostala je jedna gomila na kojoj je jedan element - propušam potez :D

---

Pa tako pise u prvoj poruci.
Takodje pise i da je uzimanje obavezno. Znaci nema propustanja poteza. Take that! :P
:)

... ne piše da je zabranjeno kloniranje kolona. Kloniram kolonu i uzimam klona.
Ne piše ni da je zabranjeno spajanje kolona. To sigurno znači da je dozvoljeno :D

---

Ovo je jedna od prvih igara sa kojom sam počeo programiranje. Bio sam napisao program u Paskalu koji primenjuje uslovnu optimalnu strategiju i može uvek da pobedi igrača (još uvek imam program koga interesuje, voleo bi da mu ga dam). Međutim, da bi igranje sa kompjuterom bilo zanimljivo, dopustio sam da u svakom nivou igrač odabere ko prvi igra. Kao što ćete videti dole, to je vrlo važno za dalji tok igre. Pametnim izborom ko igra prvi, igrač može da pobedi kompjutera uvek.

Igra kao što je neko rekao ima uslovnu optimalnu strategiju, koja je matematički jako, jako lepa. NAPOMENA: originalna verzija je da POBEĐUJE onaj koji poslednji kamenčić uzme i ovde ću se ja toga držati ne umanjujući opštost (prostom inverzijom svake reči KOMPLETAN u NEKOMPLETAN i obrnuto, stvar se namešta i za slučaj kada gubi onaj koji poslednju uzme). Pokušaću da objasnim optimalnu strategiju:

Brojeve kamenčića u svakoj hrpi predstavite u binarnom sistemu i zapišite ih jedan ispod drugog. Zatim stavite (na primer) plus ispod svake kolone koja ima paran broj jedinica, a minus ispod kolona koje imaju neparan broj jedinica. Na primer, za gornju partiju (1, 3, 5, 7) imamo (OPET PAŽNJA: Analiziram partiju imajući u vidu napomenu da POBEĐUJE onaj koji uzima poslednji):

0 0 1 = 1
0 1 1 = 3
1 0 1 = 5
1 1 1 = 7
-----------------
+ + +

U prvoj koloni (0, 0, 1, 1) imamo dva keca i stavljamo plus ispod nje, jer je dva paran broj. U drugoj koloni (0, 1, 0, 1) imamo takođe dva keca i stavljamo plus. U trećoj koloni (1, 1, 1, 1) imamo četiri keca i opet stavljamo plus, jer je četiri paran broj.

Nazovimo poziciju gomila u kojoj su svi plusevi "KOMPLETNOM", a svaku drugu poziciju u kojoj ima bar jedan minus "NEKOMPLETNOM".

U ovoj igri je početna pozicija KOMPLETNA. Optimalna strategija kaže da tada igrač treba velikodušno da prepusti prvi potez svom protivniku. Matematička teorija nam dokazuje da će protivnik, ŠTA GOD IGRAO, poziciju učiniti NEKOMPLETNOM. Vi zatim, u vašem prvom potezu NEKOMPLETNU poziciju učinite KOMPLETNOM (Matematička teroija takođe kaže da je ovo UVEK moguće). Sada će vaš protivnik, šta god igrao, učiniti poziciju NEKOMPLETNOM. Vi je opet učinite kompletnom, i tako dalje i tako bliže. Prateći ovu strategiju, vaš poslednji potez će biti uzimanje svih kamenčića iz poslednjeg preostalog reda, čime ćete konačno učiniti situaciju KOMPLETNOM (biće sve nule, tj. biće u svakoj koloni paran broj kečeva, tj. situacija će biti KOMPLETNA). Na taj način ste pobedili.

Ukoliko je početna pozicija NEKOMPLETNA (što nije u slučaju (1,3,5,7)), vi treba da igrate prvi i situciju učiniter KOMPLETNOM. onda je vaš protivnik učini NEKOMPLETNOM i u'vatili ste ga u šemu. Vaš je do kraja.

Ova strategija je uslovno optimalna, zato što naravno morate da odlučujete ko igra prvi. Dakle, postoji uslov ko igra prvi. Zbog ovoga, ne možete uvek pobeđivati a da protivnik ne posumnja.

...

Da bi razjasnili samu strategiju, hajde da razmotrimo vašu igru. noviKorisnik je igrao prvi, a početna situacija je KOMPLETNA. Dakle, on je već sada izgubio ukoliko ima za protivnika igrača koji zna optimalnu strategiju. Šta god igra, poziciju čini NEKOMPLTENOM. Situacija nakon njegovog poteza (iz prve gomile uzima jedan kamenčić) je:

0 0 0 = 0 (prazne redove ubuduće nećemo pisati)
0 1 1 = 3
1 0 1 = 5
1 1 1 = 7
-------------
+ + -

Kao što vidimo, postoje tri načina da poziciju učinimo kompletnom: možemo uzeti iz drugog, trećeg ILI četvrtog reda (potpuno svejedno) jedan kamenčić i na taj način obrisati jedan bit koji je kvario parnost. Zaista, srki se odlučuje za jedan kamenčić poslednjeg reda. Napomenimo da je kojim slučajem igrao BILO ŠTA različito od tri navedena poteza koji namešteju KOMPLETNOST, prepustio bi novomKorisniku NEKOMPLETNU situaciju, te bi on korigujući je mogao da uzme konce u svoje ruke i pravilnom igrom do kraja pobedi. Dakle, JEDNA GREŠKA I STVAR SE PREOKREĆE U RUKE PROTIVNIKA. Međutim, srki namešta parnost i čini KOMPLETNOST:

0 1 1 = 3
1 0 1 = 5
1 1 0 = 6
-------------
+ + +

noviKorisnik šta god sad da igra, kvari nameštenu KOMPLETNOST i čini poziciju NEKOMPLTENOM. Odlučuje se za pet kamečića iz trećeg reda:

0 1 1 = 3
1 0 1 = 5
0 0 1 = 1
-------------
- - -

Sada srki ima samo jedan izbor: da "1 0 1" napravi da bude "0 1 0". Ako odigra bilo šta drugo puko je, pod pretpostavkom da je noviKorisnik korisni nesvesno ovu strategiju. Srki se odlučuje za navedeni izbor:

0 1 1 = 3
0 1 0 = 2
0 0 1 = 1
-------------
+ + +

Iskusni igrači znaju napamet neke bitne KOMPLETNE pozicije. Svakako najvažnija je (1,2,3). Od ostalih nabrojmo samo (1,4,5), (3,5,6) i (1,6,7). Sada je noviKorisnik, kao i uostalom od samog početka igre, u beznadežnoj poziciji. Jedina šansa mu je da srki negde u toku igre pogreši. noviKorisnik se ovde odlučuje za dva kamenčića iz prvog reda.

0 0 1 = 1
0 1 0 = 2
0 0 1 = 1
-------------
+ - +

Srki sada greši: NE igra jedini pravilan potez, tj. ne briše bit iz drugog reda. MEĐUTIM, vi ste igrali sve naopako tako da on ustvari po vašoj verziji pobeđuje, a srki ovde i nije pogrešio nego je grešio za sve prethodne partije! (Ko razume shvatiće.) Dakle:

0 0 1 = 1
0 0 1 = 1
0 0 1 = 1
-------------
+ + -

Neka sada noviKorisnik fiktivno igra...

0 0 0 = 0
0 0 1 = 1
0 0 1 = 1
-------------
+ + +

... nameštajući parnost. Srki sada kvari parnost:

0 0 0 = 0
0 0 0 = 0
0 0 1 = 1
-------------
+ + -

... i noviKorisnik ga najzad namešta i pobeđuje:

0 0 0 = 0
0 0 0 = 0
0 0 0 = 0
-------------
+ + +

Ponavljam, kod vas je sve naopako, pa ustvari srki pobeđuje.

...

Sigurno se pitate kako to sve sa silnim nulama i jedinicama da izvedete bez papira i olovke. Posle mnogo partija, ceo se proces u glavi odvija, te protivnik uopšte ne zna ništa o nulama i jedinicama. Ukoliko znate napamet neke važne KOMPLETNE kombinacije (navedene gore), igru činite još jednostavnijom.

Pozdrav svima.

Gresis! Nisam pogresio. Treba igrati potpuno istu strategiju u obe igre samo se zavrsnica razlikuje tako da nisam gresio sve prethodne partije. Evo probaj ti da igras drugacije pa ces videti da ces izgubiti (odnosno da ces ti uzeti poslednji kamencic).
A i nismo mi igrali naopako. To je samo druga verzija igre. Isto tako moze za ovu verziju da se kaze da je naopaka.

Inace svaka cast na detaljnom objasnjenju strategije! Bilo bi dobro da bude jos ovakvih tema.
Pozdrav

Opet je srki u pravu.
Inače dobro je ono postavio BOOK .Čestitam .Samo mislim da se ne mora pamtiti
mnogo dobitničkih kombinacija.Dovoljno je znati (2;2) (1;2;3).Ko je nesiguran onda
još eventualno (3;3) (1;1;2;2).Nije pristojno kod igranja švrljati neke nule i jedinice,
jer to vrijeđa protivnika.

Ja na ovaj problem gledam kao na igranje udaljene opozicije u šahovskoj pješačkoj
završnici.Opoziciju održavam oduzimanjem para "okruglih" binarnih brojeva:1 2 4 8 itd.(Naravno u mislima).

Evo kroz jedan šaljiv primjer da to pokažem:
-Najprije upecam štuku (to je čova koji misli da sve zna),a predhodno instruiram
neko dijete da se naivno pojavi i zakuva samnom igru.Naravno dijete dobija.
-Štuka se ubaci u igru a ja pomažem malo klincu , i naravno dijete opet dobija.
-Onda se zaoštri igra (pivo).

Ja predložim protivniku da napravi nekoliko (4-5 recimo) gomilica.
On napravi naprimjer ovako:9 8 7 5 2.
Ja ga ponudim da bira ko će ići prvi.Recimo da on prepusti meni.
Ja u mislima izvršim ovaj račun: Sa prve i druge hrpe skinem po 8 , a sa treće
i četvrte po 4.Ostaje mi ovo 1 0 3 1 2.(Već sam u dobitničkoj šemi jer mogu poku-
piti 1 sa prve ili treće ili četvrte hrpe).
Napravim naprimjer ovo:9 8 6 5 2 , a protivnik recimo 8 6 5 2 .Treba li još
da gnjavim šta sam uradio u sledećem potezu ? Znam da će srki pogoditi!

E sad još dodatno možemo ojaditi štuku , ako mu u sred partije , ponudimo
ako želi promijeni ono pravilo zadnjeg uzimanja.Ovo treba uraditi kad "zaključi"
da nema dobar potez.(Ovu pakost nisam izmislio ja već srki).

---

Uzimas 7 iz prve gomilice i ostaje 6 5 2 1.

HAHAHA!!!!
Genijalno!!!! Ostane mu 1 2 3 i vidi da je izgubio i ti mu kazes da promenite pravila i da onaj koji poslednji vuce dobija i opet je puko :-)))))

e - super šo se krenulo s objašnjenjima! Malko sam još pospan, ako nije problem... da se još ovo razjasni.

BOOK, hvala na trudu. Samo da napomenem još jednom da sam krenuo igru s ubeđenjem da dobija ko vuče poslednji potez. Bilo je zanimljivo pratiti da li će srki odigrati pogrešno - i dočekam famoznu situaciju 1 1 1 (to! - ali javlja se zzzz i čestita srkiju - jer poslednji gubi).

---

Samo da vas rastužim.Ona štuka to sam bio ja.Cijeli dan sam plaćao pivo
nekom glupom dripcu koji me je baš na onaj način navukao na tanak led.

Inače onaj opozicioni sistem nije do kraja razrađen.Baš pokušavam pa ako šta smislim napisaću.Namjerno sam malo štimovao prvu poziciju da bude "zgodna"
a i drugi potez takođe.
Šta bi srki vukao da je ostavljeno umjesto 8 6 5 2 ovo 9 7 6 5 2 ?Možeš li bez
olovke i papira i razumno brzo?

---

Naravno! Necu da varam. Evo kako razmisljam dok kucam. Treba da vucem sa grupice koja zadrzi 9 kamencica jer samo ona sadrzi 8 (2^3). Onda dalje treba da bude paran broj neparnih brojeva sto znaci da u toj gomilici treba da ostavim 0, 2 , 4 ili 6 kamencica. Dalje ima 3 grupice koje sadrze 2 i to su :2, 6 i 7 i to znaci da i moja nova grupica mora da sadrzi 2. Onda 3 grupice sadrza 4 pa znaci da i moja grupica mora da sadrzi 4 i znaci resenje je da ostavim 6.

Skidam 3 iz grupice sa 9 kamencica.

Milane, nemoj da se nerviras jer je sigurno i taj sa kim si igrao placao nekom drugom pivo a i da si mene navukao verovatno bih ja tebi placao pivo. Ovako sam imao vremena da razmislim kada si prvi put zadao zadatak. Ne verujem da neko od nas isto ne bi bio stuka.

A inace da razjasnim ono sa zavrsetkom. Treba igrati isto ali samo do onog koraka kada je u svim grupicama 1 osim u jednoj grupici. E onda iz te grupice vucemo onoliko koliko nam treba da bi bio neparan ili paran broj jedinica (zavisi od igre koju igramo).

Ovo je bilo lako, samo se treba setiti binarnih brojeva (znao sam igru od ranije, tako da nisam hteo da upropastim zabavu). Evo jedne mnogo teže igre, koja ima pobedničku strategiju, a ja častim pivom onog ko je uoči:

Postoji jedna gomila sa n predmeta. Prvi igrač uzima proizvoljan broj predmeta sa gomile, jedino ne sme da uzme sve odjednom. Igra se nastavlja na taj način što igrač na potezu sme da uzme najviše dvostruki broj predmeta uzetih od strane drugog igrača u prethodnom potezu. Pobeđuje onaj ko uzme poslednji predmet.

Imate nedelju dana "fore" da smislite strategiju, ja neću igrati ovo sa vama, ali pokušajte da pobedite mog "zamenika" koji je okačen uz ovu poruku.

---

Samo da zaokružim priču o prvom problemu:
-Možda je ostalo nekom nejasno zašto koristimo binarne okrugle
brojeve.Pa ovako se dođe do te logike:
Analiziramo igru sa jednom hrpicom a zatim sa dvije.Tu netrebaju.Samo održavamo
opoziciju čim je uhvatimo (isti broj u obe sve dok jedna ne postane manja od 2.
Probamo sa tri.Pokušamo li održati opoziciju kvareći jednu hrpicu moramo doći
do ove ideje.Naprimjer 6 4 2 posmatramo kao (4+2) (4) (2).šta god protivnik uzme
i ja ću sa neke druge hrpice.Ako uzme 1 sa druge ostaje (2+1).Ja tada pravim opoziciju uzimanjem 5 sa prve pa smo dobili (1) (2+1) (2).
-Sama završnica koju je objasnio srki nastaje kad protivnika primoramo da ostavi
samo jednu hrpicu u kojoj ima više od jednog elementa.Tada sa te hrpice uzimamo
sve ili ostavimo jedan , zavisno od toga koliko još jedinica ima i kakav je pobjednički ishod dogovoren.

-Kako buljiti u hrpice i binarno razmišljati ako ih ima mnogo i povelike su?
Na onom istom primjeru što je riješio srki 9 7 6 5 2 trebam nešto povući.

Najprije parcijalno riješim 6 5 2---2 1 2---1 .Sad posmatram problem kao 9 7 1.
7 7 bi bilo divno da nije one jedinice.Dakle treba skinuti još 1 sa najveće hrpe.

---

Bojane, igra je DIVNA! Nije naivna kao oni kamenčići ("hrpice":). Analizirajući igru došao sam do optimalne strategije.

Prvo za one koji su bežali sa časova matematike: FIBONAČIJEVI BROJEVI su oni brojevi koji pripadaju FINOBAČIJEVOM NIZU, a FIBONAČIJEV NIZ je niz zadat rekurentnom vezom: a(1) = 1, a(2) = 2, a(n) = a(n-1) + a(n-2), za svako n>2. Dakle, prvih nekoliko članova niza izgleda ovako: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Optimalna strategija (koju nije teško dokazati) izgleda ovako: Ukoliko je početni broj žetona Fibonačijev broj, protivniku prepuštamo potez. U suprotnom, ukupan broj žetona se predstavlja kao zbir fibonačijevih brojeva na takav način da je broj sabiraka najmanji mogući, te se uzima onoliko žetona kolika je vrednost najmanjeg sabirka (za one koji se malo više razumeju u matematiku: mi ovde ustvari radimo brisanje bita najmanje težine u fibonačijevom binarnom sistemu). U oba slučaja, nakon što igrač odigra svoj potez, primenjuje se isti algoritam za sve vaše poteze. Na taj način sigurno pobeđujete.

Postavlja se pitanje: Kako da odredimo najmanji broj sabiraka? Odgovor je jednostavan: od samog broja kog želimo da rastavimo na sabirke oduzmemo najveći od svih fibonačijevih brojeva koji je još uvek manji ili jednak od njega. Ovaj korak ponavljamo i za dobijenu razliku, i za novodobijenu razliku i tako sve dok ne stignemo do nule. Svi korišćeni "umanjioci" u navedenom algoritmu su članovi traženog niza, a broj žetona koji mi uzimamo je najmanji član u tom nizu, tj. poslednji "umanjilac".

Primetimo da ukoliko naš protivnik pokuša da primeni istu strategiju naići se na strašnu nevolju: opisani algoritam će od njega uvek tražiti da uzme više od duplo više žetona koje ste vi bili uzeli u vašem prethodnom potezu, a time i prekrši pravilo igre. Za razliku od njega, vi ćete uvek biti u poziciji da poštujete to pravilo. Jednostavna analiza, koju ostavljam čitaocu, nam pokazuje zašto je to tako.

Pozdrav svima.

Najpre da kažem da mi se ne sviđa što je Bojan odmah tresnuo onu spajalicu.Ovo
je zabava pa nije zgodno za nas koji neznamo rješenje da nam se kaže:Šta se
mučite evo vam odmah rješenja (ili polurješenja).Namjerno nisam gledao onaj program jer bi mi valjda sve bilo jasno.

BOOK je mislim dobro postavio onaj niz :1 2 3 5 8 13 21 34 .....tj. svaki naredni član je zbir dva prethodna.Uvaliti protivniku da vuče na jednom od tih brojeva je čista pobjeda.Nesmije skočiti (ako bi smio) na sledeći niži jer je razlika x2 veća od tog broja pa bi odmah izgubio.Oprezna igra (povuci jedan ili 2 ) takođe omogućava
da ga ponovo uvalimo na sledeći niži broj u tom nizu.
Pitanje je starta od broja "n".Ko dobija?Čini mi se da će prvi na potezu uvijek
dobiti partiju ako "n" nije član niza.Ovako:Ako je razlika između "n" i prvog manjeg
člana manja od polovice tog člana onda hrabro pokupi sve do tog broja.
Naprimjer n=31.Pokupim 10 i 0staje 21.

A šta ako je veći?(Naprimjer 32 33 ili slično tome u nekom višem području)
Čini mi se da treba ići baš na onaj broj koji bi kao maksimum omogućio onu
prvu radnju.(U ovom primjeru namjestim 31).
Stvarno još ovo razmatram jer nisam siguran pošto sam popio nešto više
piva pa mi je koncentracija slaba.

---

Da sad kad sam pažljivo pročitao šta je sve napisao , BOOK vidim da je to kompletno rješenje.

---

Opet ja malo da zakuvam. Nije najkraća pobjeda ona po programu koji je
napravio Bojan .Umjesto da od 31 vučeš 2 , bolje je vući 10.Ako hoćemo
najbrže do pobjede bez mrcvarenja protivnika !Ne valja ti program , nevaljaaaa..

---