Jedi lovagos matematikai versenypélda. Tudom a megoldást, de lehet jobban?
Ez a feladat az OITM8 LLM kategóriájából származik (1. forduló, már le van zárva, a hivatalos megoldás viszont nem tetszik).
A feladat szövege:
A Jedi lovagok egy csoportja versenyt rendez. Az egyik lovag véletlenszerűen egy körön belül áll. A többi lovag véletlenszerű sorrendben kihívja őt. Ha egy kihívó legyőzi a kör lovagját, annak a lovagnak el kell hagynia a versenyt. A kihívó ekkor a Kerek Kör új lovagja lesz, és mint ilyen, minden további kihívóval szembenéz, amíg le nem győzik. Ha a Kerek Kör jelenlegi Lovagja nyeri a kihívást, akkor a Kerek Körön belül marad, és a kihívónak el kell hagynia a versenyt. A verseny végén a körön belül lévő lovagot tekintik győztesnek. Feltételezhetjük, hogy nincs két lovag, aki pontosan ugyanolyan ügyes, és hogy az erősebb lovag mindig legyőzi a gyengébbet.
Tegyük fel, hogy három lovag vesz részt a versenyben. Ha a legerősebb áll először a körbe, akkor őt nem lehet legyőzni, tehát senki sem hagyja el a kört. Ha történetesen a leggyengébb áll először a körben, akkor az első mérkőzés után kirúgják. Ha az őt legyőző lovag volt a legerősebb, akkor a végső kihívást is ő nyeri meg (így mindig csak egy lovag hagyja el a kört),ellenkező esetben a legerősebb lovag a kihívása alatt kirúgja a középső lovagot a körből (így két lovag hagyja el a kört). Ha a középső lovag áll először a körbe, akkor csak őt rúgják ki a körből, függetlenül attól, hogy a másik két lovag milyen sorrendben támad rá. Összességében átlagosan 5/6 vagy 0,83 lovag hagyja el a kört a verseny során.
Ki kell számolnod, hogy a verseny során átlagosan hány lovag hagyja el a kört a versenyben résztvevő lovagok száma alapján.
Emellett megad 2 példát is, 3 esetén (2 tizedesre kerekítve) 0,83, míg 1000-re 6,49 az eredmény. A kérdés ebben az esetben N=28 volt, arra 2,93 volt a helyes megoldás.
LLM kategória lévén LLM-mel (ChatGPT és konkurenciái) kellett megoldani, lehetőleg valamilyen kódot íratva. A hivatalos megoldás egy nem túl szép dinamikus programozást használó kód volt. A 4o nálam rájött, hogy itt harmonikus összegről van szó, a megoldás szerinte - nem túl érthető magyarázattal - a következő:
(1+1/2+1/3+...+1/N)-1
Ahol a -1 a végén a körben maradó Jedi lovag. A megoldás jó, a kérdésem az lenne, hogy ezt matematikailag, analitikus módon hogy lehet bizonyítani?
Ez a probléma valóban érdekes, és a harmonikus sor megjelenése intuitív módon is érthetővé válik, ha figyelembe vesszük a verseny mechanizmusát és a „trónfosztások” (körből való kiesések) logikáját. Az analitikus bizonyításhoz a következő lépések vezethetnek el:
1. Általános megfigyelések
Az N lovagból végül 1 marad a körben, tehát (N - 1) lovag eshet ki legfeljebb.
A verseny során minden párbaj eredménye egy lovag kiesését eredményezi.
Mivel mindig a jelenlegi körben lévő lovagot hívják ki, és az erősebb lovag győz, az erős lovagok hajlamosak „stabilizálni” a kört, kevesebb kiesést eredményezve.
2. A kulcsötlet: Minden lovag „esélye” arra, hogy kiesést okozzon
Vegyük észre, hogy egy lovag csak akkor eshet ki, ha egy nála erősebb lovag kihívja és legyőzi.
Most gondoljuk végig:
Mikor esik ki az i-edik legerősebb lovag?
Akkor, ha egy nála erősebb lovag (1-től
𝑖
−
1
i−1-ig) előbb sorra kerül, mint ő maga.
Ez azt jelenti, hogy az i-edik legerősebb lovag kiesésének valószínűsége megegyezik azzal az eséllyel, hogy nem ő a legerősebb az eddig kihívottak közül. Mivel a sorrend véletlenszerű, ez pontosan:
𝑃
(
i-edik lovag kiesik
)
=
𝑖
−
1
𝑖
P(i-edik lovag kiesik)=
i
i−1
Ennek az értéke azt mutatja meg, hogy az
𝑖
i-edik legerősebb lovag
1
/
𝑖
1/i valószínűséggel marad versenyben addig, amíg ő van a körben.
3. Az elvárt kiesések száma
Mivel minden kiesés független ilyen értelemben, az elvárt kiesések száma a következő lesz:
𝐸
(
𝑁
)
=
∑
𝑖
=
2
𝑁
𝑃
(
i-edik leger
o
˝
sebb lovag kiesik
)
E(N)=
i=2
∑
N
P(i-edik leger
o
˝
sebb lovag kiesik)
Ez a következőképpen írható át:
𝐸
(
𝑁
)
=
∑
𝑖
=
2
𝑁
(
1
−
1
𝑖
)
=
(
𝑁
−
1
)
−
∑
𝑖
=
2
𝑁
1
𝑖
E(N)=
i=2
∑
N
(1−
i
1
)=(N−1)−
i=2
∑
N
i
1
Ez egyszerűsödik:
𝐸
(
𝑁
)
=
(
𝑁
−
1
)
−
(
𝐻
𝑁
−
1
)
E(N)=(N−1)−(H
N
−1)
ahol
𝐻
𝑁
H
N
a harmonikus szám:
𝐻
𝑁
=
1
+
1
2
+
1
3
+
⋯
+
1
𝑁
H
N
=1+
2
1
+
3
1
+⋯+
N
1
Tovább egyszerűsítve:
𝐸
(
𝑁
)
=
(
𝑁
−
1
)
−
(
𝐻
𝑁
−
1
)
=
𝑁
−
𝐻
𝑁
E(N)=(N−1)−(H
N
−1)=N−H
N
De mivel a feladat szerint az elvárt kiesések száma
𝐻
𝑁
−
1
H
N
−1, nézzük meg újra:
A fenti megközelítésben valójában az elkerült kiesések számát számoltuk ki. A teljes lehetséges kiesések száma
𝑁
−
1
N−1, így:
𝐸
(
𝑁
)
=
(
𝑁
−
1
)
−
(
𝑁
−
𝐻
𝑁
)
=
𝐻
𝑁
−
1
E(N)=(N−1)−(N−H
N
)=H
N
−1
4. Intuitív összegzés
Minden új lovag belépésekor az „aktuális király” csak akkor eshet ki, ha nála erősebb érkezik.
Az elvárt kiesések száma ezért a harmonikus számokkal függ össze, mert a sorrend véletlenszerűsége éppen ilyen „csökkenő eséllyel” adódik össze.
Végül a -1 azért jelenik meg, mert a verseny végén mindig marad egy lovag a körben, aki nem esett ki.
Összefoglalva:
𝐸
(
𝑁
)
=
(
1
+
1
2
+
1
3
+
⋯
+
1
𝑁
)
−
1
=
𝐻
𝑁
−
1
E(N)=(1+
2
1
+
3
1
+⋯+
N
1
)−1=H
N
−1
Ez teljes mértékben megegyezik a feladathoz tartozó „hivatalos” megoldással.
További kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!