Kerekasztal lovagjai

[Idegfúzió]

A kerekasztal lovagjait csakis úgy szabad a kerekasztalhoz ültetni, hogy bármely két lovag közötti távolság egyedi legyen (azaz ne legyen olyan lovag, aki mellett jobbra is és balra is pontosan ugyanannyi széknyire ül egy-egy lovag).
Feladatok:
A) Egy 7 személyes kerekasztalhoz ültess le 3 lovagot!
B) Egy 13 személyes kerekasztalhoz ültess le 4 lovagot!
C) Legalább hány személyes kerekasztal kell 5 lovag leültetéséhez?
D) Add meg az előző feladat megoldásának általános képletét n lovagra!
E) Add meg a meg a "C" feladat ültetési rendjét!
F) Add meg az ültetési rend általános algoritmusát n lovagra!

/ Jelzem, hogy az F)-re nem tudom a választ... /

[G.Á]

A) pl:(1,2,4)
B) pl:(1,3,6,7)

[G.Á]

Igazából az A) résznél elegendő 6 szék, a B) résznél pedig elegendő 12 szék, feltéve hogy hogy X és Y személy között a távolság lehet ugyanakkora az óramutató járásával megegyező/ellentétes körüljárás esetén.

De persze ha ez nem megengedett, akkor a
C) megoldása, ha jól számoltam, 21.
D) megoldása pedig n(n-1)+1.

A bizonyítás az alapján történik, hogy mivel megkülönböztetjük a körüljárási irány szerint a távolságokat, 2n(n-1)/2 különböző távolság lesz.
Nyilván ha ezeket minimalizálni szeretnénk, akkor ezeknek 0,1,2...n(n-1)-1 -eknek kell lenniük.

A távolságok itt úgy értendőek, hogy ennyi (üres vagy elfoglalt) szék van a két elfoglalt pozíció között, ha sorban végigjárjuk az összeset valamilyen irányból.
Most válasszuk ki bármely kettő elfoglalt széket. Ezekhez kettőféle távolság fog tartozni (mindkét körüljárási irányhoz egy-egy), amelyhez ha hozzáadunk kettőt (a figyelembe nem vett székeket), megkapjuk a székek teljes számát.
Itt akár összeadhatjuk az összes távolságot is, figyelembe véve, hogy a teljes székek számának "n(n-1)/2"-szeresét fogjuk kapni, de könnyen látható az is, hogy a végeredmény akkor tud konzisztens lenni, ha a 0-át n(n-1)-1 -el párosítjuk, 1-et n(n-1)-2 -vel és így tovább.

Szerk: Ez utóbbi kicsit részletesebben. "n(n-1)/2" darab párt tudunk kiválasztani, ezért ha "K" a székek teljes száma: n(n-1)K/2=n(n-1) + [n(n-1)-1]n(n-1)/2 Ebből pedig K=n^2-n+1 .

[G.Á]

E) Pl: (1,2,5,7,14)

F)-re vonatkozóan talán az lehet a trükk, hogy minden esetben vissza kell vezetni a rendszert eggyel alacsonyabb fokúra.
Az E) feladatot pl: úgy vezethetjük vissza B)-re, hogy az első szék tetszőleges kiválasztása után, a másodiktól való távolsága 12 legyen. (Így a két szék közötti egyik áthaladás gyakorlatilag hasonló lesz, mintha az A) feladatban egyszerűen körbemennénk).
Valószínüleg ez lehet az alapötlet, de biztosan nem ennyire egyszerű a megoldás.

[Idegfúzió]

G. Á., jók a megoldásaid!
Az F) kérdésen még én is agyalok (néha napján). Az alapötletedet viszont sajnos nem sikerült megértenem, ha tényleg működni látszik akkor elmagyarázhatnád.

[G.Á]

Az általános algoritmust ugyan nem találtam meg, de bizonyos sejtéseket sikerült összegyűjteni:

Tekintsük az "N-lovag problémát"

Az első szék legyen az 1. , ekkor a második szék:
- (N-1)(N-2)+2 , ha N páratlan.
- (N-1)(N-2)+1 , ha N páros.

Ha N páratlan, tekintsük az N-1 -hez tartozó rendezett megoldást.
Rendezett megoldásnak azt a megoldást nevezzük, ahol az 1. és 2. szék is foglalt.
Illesszük ezt hozzá a megoldáshoz.

Ha N páros akkor nemtudom hogyan kellene eljárni.

Leellenőrzés:
N=2-nél (1,2)
N=3 ez alapján (1,2,4)

N=4 rendezett megoldása (1,2,5,7)
Ebből N=5 megoldása (1,2,5,7,14)

N=6 -nál (1,?,?,?,?, 21)

Persze bizonyítani legfeljebb annyit tudnék, hogy rendezett megoldás mindig létezik, feltéve hogy létezik megoldás.