∑ Math BrotherhoodKOMBINATORIKA
Kombinacije · Putanje

Putanje na šahovskoj tabli

Svaka putanja sadrži sedam pomeranja udesno i sedam nagore.

Zadatak 10 Izvorni broj: 16

Na šahovskoj tabli dimenzije 8 × 8, u jednom potezu figura se može pomeriti jedno polje udesno ili jedno polje nagore. Broj svih mogućih putanja date figure od donjeg levog do gornjeg desnog polja šahovske table jednak je:

  1. A) 256
  2. B) 4096
  3. C) 3432
  4. D) 128
  5. E) 3600
  6. N) Ne znam.

Rešenje

Koliko poteza je potrebno?

Od prve do osme kolone potrebno je 7 pomeranja udesno, a od prvog do osmog reda 7 pomeranja nagore. Svaka dozvoljena putanja zato ima ukupno 14 poteza.

Kodiranje putanje

Pomeranje udesno označimo sa D, a nagore sa G. Putanja je niz od sedam slova D i sedam slova G. Svaki takav niz daje jednu putanju na tabli: figura nikada ne izlazi izvan table jer ni u jednom smeru ne napravi više od sedam koraka.

Izbor mesta za pomeranja udesno

Od 14 mesta u nizu biramo 7 za slovo D. Preostala mesta automatski pripadaju slovu G:

\[N=\binom{14}{7}=\frac{14!}{7!\,7!}=3432.\]

Rezultat

Tačan odgovor: C
\[\boxed{3432}\]

Krećemo se između polja, pa je potrebno 7 + 7 koraka. Osam koraka u svakom smeru odnosilo bi se na kretanje između krajnjih temena mreže od 8 × 8 kvadrata.