Kezdőlap


Cím:	A három dobókocka
Szerző(k):	Bártfai Pál
Füzet:	1973/november, 97 - 101. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Hozzászólás e Lapok egy feladatához

A 130. sz. sportversenyen kívüli probléma^{$^{*}$} ekvivalens átfogalmazásban a következőképpen hangzik:
Péter és Pál kockajátékot játszanak. Pál három dobókockának a lapjait beszámozza az

1, 2, 3, ..., 18

számokkal, mindegyik számot egyszer és csak egyszer felhasználva. Péter a kockákat megnézi, választ közülük egyet, majd Pál is választ a maradék kettőből egyet. Ezután mindegyikük feldobja saját kockáját, s aki nagyobbat dob, az 1 Ft-ot nyer a másiktól. Bizonyítandó, hogy Pál meg tudja úgy számozni a kockákat, hogy számára a játék előnyös legyen.
A közölt megoldás megad néhány megszámozási módot, s ezzel a feladatot teljes egészében megoldja; mégis, főképpen ha azt a megfogalmazást olvassuk, hiányérzetünk marad. Hogyan kapható ilyen megoldás ? Melyik a legügyesebb megoldás ? ‐ vetődnek fel bennünk a kérdések. Célunk most a legügyesebb megszámozást megtalálni.
Jelöljük meg a kockákat az 1, 2 és 3 számokkal úgy, hogy az a kocka legyen az egyes, amelyikre az egyes szám kerül. Jelöljük azt az eseményt, hogy az egyes kockával nagyobbat dobunk, mint a kettessel, hogy a kettessel nagyobbat dobunk, mint a hármassal, hogy a hármassal nagyobbat dobunk, mint az egyessel, rendre

A

-val,

B

-vel, ill.

C

-vel, és legyen a valószínűségük

P (A) = p_{1}, P (B) = p_{2}, P (C) = p_{3}

.
Ha

p_{1} \geq \frac{1}{2}, p_{2} \geq \frac{1}{2}, p_{3} \geq \frac{1}{2}

, akkor Pál nyerésének valószínűsége min (

p_{1}, p_{2}, p_{3}

), mivel Péter nyilván számára a legkedvezőbben választ a kockák közül. Legügyesebbnek, legjobbnak nevezhető tehát az a számozás, melyre min (

p_{1}, p_{2}, p_{3}

) a lehető legnagyobb. A közölt megoldásban láttunk olyan példát, amelyben min

(p_{1}, p_{2}, p_{3}) = \frac{20}{36}

.
1. Az első lépésben bebizonyítjuk, hogy

p_{1} + p_{2} + p_{3} \leq 2

. Ezzel min (

p_{1}, p_{2}, p_{3}

) értékét felülről tudjuk korlátozni, mégpedig min

(p_{1}, p_{2}, p_{3}) \leq \frac{2}{3} = \frac{24}{36}

.
A három kocka együttes feldobásának

6^{3} = 216

lehetséges eredménye van. Számoljuk most össze, hányszor következik be ezekből az

A

, a

B

, ill. a

C

esemény; pontosabban mondva, rögtön e három szám összegét becsüljük meg. Egy rögzített lehetséges eredménynél az

A

B

és

C

közül legfeljebb kettő következhet be, hiszen nem lehet; hogy mind a három dobott szám nagyobb legyen valamelyik másiknál. Ily módon az

A, B

és

C

események összesen legfeljebb 432-ször következnek be, ha végignézzük az összes lehetséges 216 kimenetelt, tehát

p_{1} + p_{2} + p_{3} \leq 2

.
Ezentúl a

p_{1}, p_{2}, p_{3}

valószínűségek helyett azok 36-szorosát, az

N_{1}, N_{2}, N_{3}

egész számokat fogjuk vizsgálni. Jelölje

N

e számok összegét:

N = N_{1} + N_{2} + N_{3}

. Az előbb bizonyítottak szerint

N \leq 72

, s egyúttal

M = min (N_{1}, N_{2}, N_{3})

-ra is, melyet maximalizálni akarunk, felső becslést kaptunk:

M \leq 24

.
Bemutatunk egy példát arra, hogy

M = 21

elérhető. A kockák számozása legyen:

\begin{matrix} I : & 1, 6, 7, 8, 17, 18; \\ II : & 3, 4, 5, 14, 15, 16; \\ III : & 2, 9, 10, 11, 12, 13. \end{matrix}

Ez esetben

N_{1} = N_{2} = N_{3} = M = 21

. Később más példát is fogunk mutatni.
2. A továbbiakban a megoldás kulcsa az, hogy a kockák számozását lehetőleg tömören, áttekinthetően tudjuk megadni. Ehhez a megadásmódhoz két lépésben jutunk el.
A kockák egy tényleges számozását 6 db 1-es, 6 db 2-es, 6 db 3-as szám egy permutációjával adhatjuk meg: ha e sorozat

k

-adik eleme pl. 3-as, akkor ez azt jelenti, hogy a

k

szám a harmadik kockára kerül. Tekintsünk példaként egy ilyen sorozatot:

\begin{matrix} 1 1 2 2 3 2 1 1 3 2 2 1 3 3 1 2 3 3 \end{matrix}

(megállapodás szerint a sorozat első eleme mindig 1-es). Az

N_{1}, N_{2}, N_{3}

értékek kiszámítása itt még elég fáradságos. Türelmesen meg kell számolni, hogy hány olyan számpár van a sorozatban, ahol a 2 megelőzi 1-et és adódik

N_{1} = 16

, majd ugyanezt a 3‐2 viszonylatban, végül az 1‐3 viszonylatban leszámolva kapjuk, hogy

N_{2} = 9

és

N_{3} = 28

.
Cseréljük fel a sorozat 4. és 5. elemét; az

\begin{matrix} 1 1 2 3 2 2 1 1 3 2 2 1 3 3 1 2 3 3 \end{matrix}

sorozatban a 3‐2 párok száma eggyel megnőtt, tehát

N_{2} = 10

, míg

N_{1}

és

N_{3}

változatlan maradt. Tetszőleges kiindulásul vett sorozat ily módon feljavítható bizonyos fokig: bármely szomszédos 1‐2, 2‐3 vagy 3‐1 pár felcserélése az

N_{1}, N_{2}, N_{3}

számok egyikét eggyel növeli, míg a másik kettőt változatlanul hagyja. Ilyen cserékkel bármely sorozatból eljuthatunk egy másik, jobb sorozathoz, amelyben már 1‐2, 2‐3, 3‐1 szomszédos párok nincsenek. A továbbiakban elég ilyen sorozatokkal foglalkoznunk. Példánkban a 2‐3 párok cseréjével az

\begin{matrix} 1 1 3 2 2 2 1 1 3 2 2 1 3 3 1 3 3 2, \end{matrix}

majd a 3‐1 párok cseréjével az

\begin{matrix} 1 1 3 2 2 2 1 1 3 2 2 1 1 3 3 3 3 2 \end{matrix}

sorozathoz jutunk (

N_{1} = 16, N_{2} = 13, N_{3} = 30

).
Egy ilyen sorozat még tömörebben is megadható. Mivel az ilyen sorozatok szerkezete olyan, hogy néhány kezdő egyes szám (a továbbiakban röviden: egyes blokk) után néhány hármas (hármas blokk), majd néhány kettes (kettes blokk) következik s i. t., elég azt feltüntetni, hogy egymás után hányszor ismétlődik egy-egy szám:

\begin{matrix} 2, 1, 3, 2, 1, 2, 2, 4, 1, \end{matrix}

vagy betűkkel

\begin{matrix} a_{1}, c_{1}, b_{1}, a_{2}, c_{2}, b_{2}, a_{3}, ..., \end{matrix}

(*)

ahol

a_{k}

k

-adik egyes blokkban levő egyesek számát jelöli, s ugyanígy

b_{k}

a kettesek,

c_{k}

a hármasok számát. Nyilván

\begin{matrix} a_{1} + a_{2} + ... = b_{1} + b_{2} + ... = c_{1} + c_{2} + ... = 6. \end{matrix}

Természetesen e sorozat véges és elemei természetes számok.
Nézzük, hogyan számíthatjuk ki itt az

N_{1}

értékét. Gondoljunk arra, hogy a 2‐1 párok számát kell összeszámolni, és (*)-ban a

b_{1}

szám

b_{1}

darab kettest,

a_{2}

pedig

a_{2}

darab egyest jelent, tehát csupán ebből a két blokkból

b_{1} a_{2}

darab 2‐1 pár választható ki. Általános képlet:

\begin{matrix} N_{1} = b_{1} (a_{2} + a_{3} + ...) + b_{2} (a_{3} + a_{4} + ...) + ..., \end{matrix}

vagy szavakkal:

N_{1}

egyenlő azon

b a

szorzatoknak az összegével, ahol a

b

indexe kisebb, mint az

a

indexe.
Egy kicsit más a képlet

N_{2}

-nél és

N_{3}

-nál, ugyanis itt az azonos indexű

c b

, ill.

a c

szorzatok is számításba jönnek:

\begin{matrix} N_{2} = c_{1} (b_{1} + b_{2} + ...) + c_{2} (b_{2} + b_{3} + ...) + ... \\ N_{3} = a_{1} (c_{1} + c_{2} + ...) + a_{2} (c_{2} + c_{3} + ...) + ... \end{matrix}

(Gyakorlásképpen ellenőrizzük a megadott példában az

N_{1}

N_{2}

N_{3}

megadott értékeit !)
3. Rögzítsük most a (*) sorozat hosszát,

h

-t, és keressük

N

maximális értékét. Megmutatjuk, hogy

N

növelésével vagy változatlanul hagyásával a sorozat mindig átalakítható úgy, hogy az

a_{1}, a_{2}, ...

sorozat elemei egy kivételével mind egyesek legyenek, majd ugyanez elvégezhető a

b_{1}, b_{2}, ...

és a

c_{1}, c_{2}, ...

sorozatra is.
Tegyük fel, hogy az

a_{1}, a_{2}, ...

sorozatnak van két, 1-nél nagyobb eleme:

a_{k}

és

a_{l} (k < l)

. Legyen a közbeeső

b

-elemek összege

B

, a közbeeső

c

-elemek összege

C

. Ha

B > C

, akkor

a_{k}

-t 1-gyel,

a_{l}

-et (

a_{k} + a_{l} - 1

)-gyel pótolva

N

értéke

(B - C) (a_{k} - 1)

-gyel növekszik, ugyanis a 2‐1 párok száma

B (a_{k} - 1)

-gyel növekszik, az 1‐3 párok száma

C (a_{k} - 1)

-gyel csökken, míg a 3‐2 párok száma változatlan marad. Ha

B \leq C

, akkor

a_{k}

-t

(a_{k} + a_{l} - 1)

-gyel,

a_{l}

-et pedig 1-gyel pótolva

N

értéke

(C - B) (a_{k} - 1)

-gyel növekszik.
Így elérhető, hogy a sorozatnak csak három eleme különbözik 1-től. Lehetőség szerint húzzuk előre a sorozatban e három elemet az előbbi második típusú átalakítással. Mert már könnyen megállapíthatók a különböző

h

hosszúsághoz tartozó maximális

N

-et adó (*) sorozatok, és így

N

maximális értéke is. Ezt táblázatban foglaljuk össze:

\begin{matrix} \begin{matrix} h & a maximális sorozat & N \\ 3 és 4 & tetszőleges & 72 \\ 5 & 1, 5, 6, 5, 1 & 71 \\ 6 & 5, 5, 5, 1, 1, 1 & 67 \\ 7 & 4, 5, 5, 1, 1, 1, 1 & 67 \\ 8 & 1, 4, 5, 4, 1, 1, 1, 1 & 66 \\ 9 & 4, 4, 4, 1, 1, 1, 1, 1, 1 & 63 \end{matrix} \end{matrix}

N

maximális értéke

h

növekedésével, mint azt néhány értékre a táblázatból láthatjuk, csökken (pontosabban: nem növekszik). Ezt indukcióval bizonyítani is tudjuk. Tekintsünk egy

(h + 1)

hosszúságú

(h \geq 7)

, fenti alakú maximális sorozatot, ennek végződése:

\begin{matrix} ..., 1, 1, 1, 1, 1. \end{matrix}

Ha ehelyett az

\begin{matrix} ..., 1, 2, 1, 1 \end{matrix}

végződésű, különben változatlan

h

hosszúságú sorozatot tekintjük,

N

értéke változatlan, hiszen

N_{1}, N_{2}, N_{3}

közül egyik eggyel növekedett, valamelyik eggyel csökkent, s a harmadik változatlan maradt. Tehát van olyan

h

hosszúságú sorozat, amelyre

N

értéke ugyanannyi, mint a maximális

N

érték a

h + 1

hosszúságú sorozatokra, ami az állítást bizonyítja.
4. Most bebizonyítjuk, hogy

M \geq 22

nem érhető el. Ehhez elég a

h \leq 8

eseteket végignézni.
A

h = 8

esetben

M \geq 22

csak úgy lehetséges, ha

N_{1} = N_{2} = N_{3} = 22

. Tekintsünk egy nyolc elemből álló sorozatot:

\begin{matrix} a_{1}, c_{1}, b_{1}, a_{2}, c_{2}, b_{2}, a_{3}, c_{3} \end{matrix}

és keressük a maximális

N = 66

-ot adó sorozatokat. Nézzük először azt az esetet, amikor

b_{1} > 1

és

b_{2} > 1

. Ekkor

a_{2} = c_{2}

, különben

b_{1}

, vagy

b_{2}

növelésével

N

növelhető lenne.

c_{1}

, és

c_{2}

közül mindkettő nem lehet egynél nagyobb, mert az egyik ugyancsak növelhető lenne a másik rovására

N

növelésével, kivéve azt az esetet, amikor

b_{1} = a_{2}

, de akkor előbb

b_{1}

-et kell

N

változatlanul tartásával megváltoztatni. Folytatva ezt a gondolatmenetet, kapjuk, hogy az

a_{k}

-k, valamint a

b_{k}

-k között csupán egy-egy négyes és két-két egyes van, továbbá

a_{1} = 1

és

c_{3} = 1

is kötelező. Ezek után két sorozattípus marad:

\begin{matrix} 1, 1, ., 4, 4, ., 1, 1 \\ 1, 4, ., 1, 1, ., 4, 1. \end{matrix}

N_{3}

mindkettőre kiszámítható: 27 és 12 adódik, tehát

N_{3} \neq 22

. Ha

b_{1} = 1

, akkor

b_{2} = 5

. Az előbbi gondolatmenettel most

a_{1} = 1, a_{2} = 1, a_{3} = 4

, majd

c_{3} = 1

adódik:

\begin{matrix} 1, ., 1, 1, ., 5, 4, 1, \end{matrix}

másrészt

b_{1} = 5

esetén a fordított sorozatot kapjuk:

\begin{matrix} 1, 4, 5, ., 1, 1, ., 1. \end{matrix}

A két maximumot adó sorozat közül az elsőre

N_{1} = 25

, a másodikra

N_{2} = 25

. Más maximális sorozat nincs, tehát

M = 22 h = 8

esetén nem érhető el. Ha

h = 6

vagy 7, akkor számítsuk ki

N_{2}

-t:

\begin{matrix} N_{2} = b_{1} c_{1} + 6 b_{2} = b_{1} c_{1} + 6 (6 - b_{1}) = 36 - b_{1} (6 - c,) . \end{matrix}

Két esetet kell megnézni:

N_{2} = 22

vagy

N_{2} = 23

lehetséges-e ? Ha

N_{2} = 22

, akkor

\begin{matrix} b_{1} (6 - c_{1}) = 14, \end{matrix}

N_{2} = 23

, akkor

\begin{matrix} b_{1} (6 - c_{1}) = 13. \end{matrix}

Mindkettő lehetetlen, mert mindkét tényező 1 és 5 közé kell essen.
Ha

h = 5

, akkor

\begin{matrix} N_{1} = 6 a_{2}; N_{2} = 6 c_{1}; N_{3} = 36 - c_{1} a_{2}, \end{matrix}

azaz az első két egyenlet alapján

a_{2}

és

c_{1}

, legalább 4 kell legyen, de akkor

N_{3} \leq 20

.
A

h = 4

esetben

N_{2} = 36

, ami minden további lehetőséget kizár.
Bebizonyítottuk tehát, hogy

M \geq 22

nem érhető el.

M = 21

-re több megoldás van, ha ezek közül legjobbnak azt nevezzük, amelyre

N

a lehető legnagyobb, akkor a legjobb megoldás sorozata:

\begin{matrix} 1, 3, 5, 5, 3, 1 \end{matrix}

vagy kockákra szétbontva:

\begin{matrix} I : & 1,10,11,12,13,14; \\ II : & 5,6,7,8,9,18; \\ III : & 2,3,4,15,16,17, \end{matrix}

mely esetben

N_{1} = 25, N_{2} = 21, N_{3} = 21

(és ez egyben

h = 6

-ra egy maximális sorozat). Hogy ennél jobbat nem lehet csinálni, azt a

h = 5

esetnél elmondott diszkusszió mutatja.

^{$^{*}$}Megoldását lásd K. M. L. 46 (1973) 169. oldal.