Zamolio bih za pomoć oko kombinatornog zadatka sa jednog opštinskog takmičenja.
Ukratko, treba pronaći broj načina da se u k poteza skakačem dođe sa jednog ugla šahovske table na suprotno (po dijagonali, konkretno, iz donjeg levog u gornji desni), gde je k minimalni broj poteza za takvo premeštanje.
Moj postupak:
Lako se dokazuje da je premeštanje nemoguće u manje od 5 poteza. Kako su ugaona polja iste boje, a skakač pri svakom potezu prelazi na polje suprotne boje, jasno da je u 5 poteza to takođe nemoguće, jer je to moguće ostvariti samo parnim brojem poteza. Pošto je to moguće u 6 poteza, što se takođe lako može pokazati, k=6.
Prema tome zadatak se može svesti na određivanje broja načina na koje se skakač može dovesti sa jednog ugonog polja u njemu dijametralno suprotno (po dijagonali, jasno da postoji simetrija ugaonih polja, tj. dolazak iz levog donjeg u gornji desni može se ostvariti u istom broju poteza kao iz levog gornjeg u desno donje polje) u 6 poteza.
Ovde sam nekakvim logičkim prebrojavanjem došao da je to 108, ali mi je prilično nejasno kako bih to matematički mogao da formulišem.
Takođe me interesuje kako bih mogao rešiti još opštiji kombinatorni zadatak koji sam sastavio sam inspirisan ovim- na koliko načina je moguće ovakvo premeštanje u n poteza, gde je n proizvoljan paran prirodan broj veći od 4.
[Ovu poruku je menjao Fermion dana 06.12.2010. u 11:10 GMT+1]
[Ovu poruku je menjao Fermion dana 06.12.2010. u 11:12 GMT+1]
[Ovu poruku je menjao Fermion dana 06.12.2010. u 11:38 GMT+1]