[es] - Kombinatorika zadatak

Fermion
ucenik

Član broj: 273771
Poruke: 237
*.mbb.telenor.rs.

+13 Profil

^{06.12.2010. u 09:56 - pre 162 meseci}

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]}

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.

+2790 Profil

Re: Kombinatorika zadatak

^{06.12.2010. u 11:44 - pre 162 meseci}

Polja šahovske table su čvorovi grafa, a za polja A i B postoji ivica koja povezuje A i B akko skakač može sa polja A da skoči na polje B. Problem se svodi na određivanje broja puteva po tom grafu od jednog ugla do drugog prelazeći tačno 6 ivica.

Neka je G bilo koji graf sa n čvorova i M matrica formata n x n, koja i preseku i-te vrste i j-te kolone ima jedinicu ako se iz i-tog čvora može direktno preći u j-ti čvor, a u protivnom 0. Tada se i preseku i-te vrste i j-te kolone matrice M^k nalazi broj načina na koji se od i-tog čvo ra može doći u j-ti čvor

a) u tačno k poteza ako su na glavnoj dijagonali matrice M nule,
b) u najviše k poteza ako su na dijagonali matrice M jedinice..

E, sad, ovo je nepraktično za opštinsko takmičenje, jer treba matricu formata 64 x 64 dići na šesti stepen.

Praktičnije rešenje bi bilo sledeće:

Za polja A i B ću reći da su susedna ako skakač može da skoči sa polja A na polje B. Za polje ću reći da je k polje ako skakač može iz polja A1 da dože na to polje u tačno k poteza. Nacrtaj šahovsku tablu i primenjuj sledeći postupak:

U k-toj iteraciji upisuješ u k-1 polja uređene parove čija je prva komponenta k-1, a druga broj načina da se iz polja A1 dođe u to polje u tačno k-1 poteza.

U prvoj iteraciji upisuješ par (0,1) u polje A1. U (k+1)-voj iteraciji u k-polje P upisuješ par (k,m), gde se m određuje na sledeći način: Neka su susedna k-1 polja polju P polja Q₁,...,Q_n i neka su u njih upisani parovi (k,m₁),...,(k,m_n). Tada je m=m₁+...+m_n.

U polju H8 ćeš u sedmoj iteraciji dobiti par (6,b), gde je b rešenje.

Postupak se može ubrzati korišćenjem simetrija. Prvo, možemo pretpostaviti da skakač sa polja A1 u prvom potezu skače na polje B3, a ne na C2. Time ćemo dobiti broj načina da se stigne do polja H8 u šest poteza podeljen sa dva. Dalje, kada odredimo 3-polja, onda možemo odrediti na koja se polja može stići sa polja H8 u tri poteza i na koliko načina. Zatim za parove P, Q polja takvih da se na polje P može stići sa A1 u tri poteza, odnosno na polje Q sa polja H8 u tri poteza, pri čemu su P i Q susedna polja pomnožiti broj načina da se u tri poteza stigne od polja A1 do polja P i broj načina da se u tri poteza stigne od polja H8 do polja Q i onda sve te zbirove sabrati.

Takođe, obzirom da znamo da se od A1 do H8 ne može stići u manje od 6 poteza, možemo da nakon upisivanje para (k,m) u neko k polje više ne upisujemo u isto polje (l,n) niti za jedno l>k.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.teletrader.com.

+2790 Profil

Re: Kombinatorika zadatak

^{06.12.2010. u 12:55 - pre 162 meseci}

Dobro si odredio da je 108. Evo programskog rešenja na jeziku C++:

Code:
#include <iostream>
#include <cstdlib>

using namespace std;

struct polje {
    int rastojanje, broj_puteva;
};

polje tabla[8][8];

bool susedi(int i, int j, int i1, int j1) {
   return abs(i - i1)*abs(j - j1) == 2;
}

int main(int argc, char *argv[]) {
    const int nedefinisano = 1000;

    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            tabla[i][j].broj_puteva = 0;
            tabla[i][j].rastojanje = nedefinisano;
        }
    }

    tabla[0][0].broj_puteva = 1;
    tabla[0][0].rastojanje = 0;

    for (int k = 1; k <= 6; ++k) {
        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (tabla[i][j].rastojanje == k - 1) {
                    for (int i1 = 0; i1 < 8; ++i1) {
                        for (int j1 = 0; j1 < 8; ++j1) {
                            if (tabla[i1][j1].rastojanje >= k && susedi(i, j, i1, j1)) {
                                tabla[i1][j1].rastojanje = k;
                                tabla[i1][j1].broj_puteva += tabla[i][j].broj_puteva;
                            }
                        }
                    }
                }
            }
        }
    }

    for (int i = 7; i >= 0; --i) {
        for (int j = 0; j < 8; ++j) {
            cout << " " << tabla[i][j].rastojanje << "," << tabla[i][j].broj_puteva;
        }

        cout << endl;
    }

    return EXIT_SUCCESS;
}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu