Szoval a kovetkezo a feladat:
Vannak az 1, 2, 3, ..., n szamok, ezeket felirod valamilyen sorrendben egy korbe (igazabol a konkret kor mindegy, annyi a lenyeg, hogy az utolso utan az elso jon). Ezutan megnezed, hogy teljesul-e ra, hogy minden szam oszthato a ket szomszedjanak (ugye ezert van korben, hogy az elsonek es az utolsonak is legyen 2-2 szomszedja - ok egymas szomszedai) kulonbsegevel.
Ha sikerul valahogy elhelyezni, akkor az az n jo, ha nem, akkor meg be kell valahogy latnod, hogy azt nem lehet ugy elhelyezni.
Na, ez volt maga a feladat (csak azert irtam le, mert ha jol lattam, tobb forumtarsnak problemaja akadt az ertelmezesevel).
Ez a feladat amugy egy tipikus visszalepeses kereseses "constraint" problema, mint mondjuk az N kiralyno (adott, nem tul nagy N-re). Szimmetriakat ki lehet hasznalni benne, meg hogy ha valahonnan mar nem lehet befejezni, akkor le lehet nyesni az ottani keresesi fat.
Mondjuk kikotheted, hogy az 1. helyen mindenkepp az 1 szerepeljen. Ezt megteheted, mert ha letezik megoldas, akkor egyszeruen elforgatod a kort abba a pozicioba, ahol az 1-es van az elejen. Ugyanigy kikotheto, hogy a 2. helyen levo szam legyen kisebb az utolsonal (mert mindketto az 1-es szomszeda, szoval ha van egy olyan megoldas, ahol forditva van, tukrozod a kort).
Ezutan celszeru modszeresen vegiglepkedni a kitoltesen, es kizarni azokat, ahonnan a kitoltes mar nem befejezheto, aztan tovabb nezni olyannal, ami meg eselyes. Vagy ha ranezesre latszik egy kitoltes, akkor megprobalni azt, es utana tovabblepni a kovetkezo n-re/vagy feladatra. (ugye csak az szamit, hogy van-e megoldas vagy sem, nem kell az osszes)
Aztan ha az 1 van az elejen, akkor - az ugye csak 1-gyel oszthato, tehat a ket szomszedjanak (2-es es n. index) is szomszedos szamnak kell lennie.
n=5-nel mondjuk elkezded:
1, probaljuk meg a 2-t utana. Eddig jo, az utolso helyen 3 kell legyen (2 szomszeda, es 1 mar szerepelt), szoval most 1, 2, ?, ?, 3 a szamsor (ahol a ? 4 es 5 valamilyen sorrendben). 4 nem lehet a 2 utan, mert 2 szomszedai azonos paritasuak, 5 meg azert nem, mert 2/(5-1) nem egesz.
Akkor a 2 nem jo a 2. helyen, 3 nem lehet, mert akkor az utolso 2, es az egyik szimmetria feltetelunk nem teljesul. Megprobaljuk meg a 4-et: 1,4,x,y,z, akkor z csak 5 lehet (4 nagyobb szomszeda), szoval lehetne 1,4,2,3,5 vagy 1,4,3,2,5, de egyik sem jo, mert 5/(1-3) es 3/(4-2) sem jo. Vissza az elejere, 1-gyel kezdunk, de 5 mar nem johet utana, mert annal nem lesz nagyobb szam az utolso helyre. Ellentmondasra jutottunk, n=5 nem kitoltheto.
Ez igy leirva eleg hosszadalmas, de eleg gyorsan vegiggondolhato, ha nem kell gepelned. Ehhez hasonloan vegigcsinalod a tobbit is. Persze butan vegigporgetve n!-al aranyos a permutaciok szama, de esszel ez lent tarthato.
--
Any A.I. smart enough to pass a Turing test is smart enough to know to fail it. -Ian McDonald