Matematické Fórum

1) V prvním tahu sebere první hráč koláček ve druhé řadě a druhém sloupci, pak používá vhodné zrcadlení tahů protivníka.

2) Eulerova věta nám říká, že F-E+V=1, kde F je počet usedlostí, E silnic a V křižovatek. Počet křižovatek ve tvaru X označme X. Celkový počet křižovatek je V=2X+114. Celkový počet míst, kde cesta ústí do křižovatky je 3*5+4*X+3*(X+111),  což se musí rovnat 2E(každá cesta ústí do křižovatky na dvou místech). Hodnotu F známe, E a V vyjádříme pomocí X a dosadíme do Eulerovy věty.

↑ Spasitel:Ano, zůstane jen první řádek a sloupec. Ale každý hráč z nich může odebrat víc jak jeden koláček, čímž závisost na n zmizí. Nechtěl jsem psát kompletní řešení, tak jsem schválně napověděl je "vhodné zrcadlení". Ale když rozmyslíme, podle čeho je úloha souměrná, snadno to zrcadlení najdeme a matematický důkaz korektnosti -- tj. že tah odpovídající strategii mohu uděat a že strategie opravdu vyhraje -- taky není těžký (použije se v něm ta souměrnost).

↑ x.soldier:Co tohle: Eulerova věta nám říká, že F-E+V=1, kde F je počet usedlostí, E silnic a V křižovatek. Počet křižovatek ve tvaru X označme X. Celkový počet křižovatek je V=2X+114. Celkový počet míst, kde cesta ústí do křižovatky je 3*5+4*X+3*(X+111),  což se musí rovnat 2E(každá cesta ústí do křižovatky na dvou místech). Hodnotu F známe, E a V vyjádříme pomocí X a dosadíme do Eulerovy věty.

Tak dobře, pokud ti jde o to, že se tu nevyskytuje slovo "graf": Uvažujme graf, v němž vrchly odpovídají křižovatkám, hrany silnicím a plochy ohraničené ze všech stran hranami usedlostem. Počet hran, vrcholů a ploch označme standardně E,V a F. Eulerova věta nám ... (dále nahraď křižovatky slovem "vrchol" atd.) Místo "Celkový počet míst, kde cesta ústí do křižovatky" napiš "součet stupňů vrcholů".

Ještě teda jeden dotaz k té eulerově větě. Na wikipedii jsem našel, že její vzorec je v − h + s = 2 (link). Slyším o ní poprvé, tak nevím, jestli vzorec s dvojkou není na něco jiného, tak bych se na to rád zeptal pro jistotu...

zdravím, není mi pár věcí jasných:

nevím proč tam máš V=2X+114.  Proč 114?

a taky nevím, jak chceš vyjádřit E a V pomocí X... nějak mi to nejde. Můžes mi prosím poradit jak jsi to myslel? Díky

chtěl bych se ujistit že te vzorec je dobře ja ho totiž taky našel všude jen roven 2. a nebo jeste toto http://encyklopedie.divoch.info/cs/Rovi … AFv_vzorec
a pokud se to ma opravdu timto vzorcem počitat tak jak jsi došel na ten vzorec ze stěnama myslim (3*5+4*x+3*(x+111))=2E
(už asi vim to 3*5 znamena že je tam 5 cest a křižovatky jsou tři.Tak proto mam pravdu??? )

diky za odpoved

Sorač že tu zase pišu, ale jen jsem chtel řict že už jsem to pochopil proč je ten vzorec taky jaky si napsal (v-e+s=1) 
Dikas moc Kondr!!!

Vyšlo mi to stejně...1014.

jen potvrzuji 1014!Dnes jsem byl u kovaře ten řikal že samo vzorec dobre dival se na křižovatky (ty jsem mel blbe pač jsem se prepsal s 333 jsem udelal 33 ale jinak řikal že když to dopočitam tak by to melo byt ok )

dobrá, pokud to rikal Kovar, tak by to melo byt dobre... Ostatne, odevzdava se to jemu...

no musis ukazat, ze pokud prvni hrac je chytry a na zacatku provede chytry tah, muze potom vhodnym zrcadlenim souperovych tahu vzdy nechat na soupere posledni otraveny kolacek. Nakresli si to treba pro n=5... a zacni snedenim 16ti kolacku... pak uz to snad pochopis jak ma hra VZDY pokracovat a VZDY zacinat

Pokud jde o formalizaci toho prvního příkladu: nejprve je potřeba strategii popsat a pak dokázat, proč funguje.

Po prvním tahu jde situaci popsat dvojicí čísel (a,b), kde a je počet koláčků v prvním sloupci a b počet koláčků  prvním řádku. Nyní indukcí dokážeme, že po tahu prvního hráče jsou vždy obě složky stejné, po tahu druhého hráče obě různé nebo obě nulové.

Po prvním tahu prvního hráče jsou obě složky rovny n. Druhý hráč buď sní všechny zbylé koláčky a obě složky budou nulové, nebo sníží pouze jednu. Bázový krok indukce funguje.

Předpokládejme, že po k-tém tahu druhého hráče byly dle indukčního předpokladu složky a,b různé. První hráč pak zahraje tah podle své strategie, takže obě složky srovná na hodnotu menší z nic. Druhý hráč pak buď sní všechny zbylé koláčky a obě složky budou nulové, nebo sníží pouze jednu a složky budou různé.

Tím je důkaz pomocného tvrzení hotov.

Z předchozího tvrzení je zřejmé, že první hráč může svůj tah udělat vždy, druhý pouze pokud nezačíná ve stavu (1,1). Protože v každém tahu ubude alespoň jeden koláček, hra musí skončit prohrou některého hráče. Tím bude druhý hráč.