Legkevesebb hány autómozgatással érhető el, hogy minden autó a helyére kerüljön, bárhogyan álltak be este az autók a parkolóba? (Egy autómozgatás azt jelenti, hogy egy autóval valamelyik parkolóhelyről egy másik parkolóhelyre áll a gondnok. )

Csak szerintem hiányos ez a feladat? Tudni kellene, hogy melyik autó hova állt (pl. 1-es autó a 3-as helyre; rendszám helyett most számokkal), mert így számtalan kombináció lehetséges.

Mi van akkor, ha az autók pont jó sorrendben érkeztek és mindenki a neki megfelelő helyre állt be? Akkor a gondnoknak nincs is feladata (0 mozgás), mert mindenki jó helyen áll.

2 parkolóhely, 1 autó, 1/2=0+1, 0*3+1=1 mozgás

3 parkolóhely, 2 autó, 2/2=1+0, 1*3+0=3 mozgás

4 parkolóhely, 3 autó, 3/2=1+1, 1*3+1=4 mozgás

5 parkolóhely, 4 autó, 4/2=2+0, 2*3+0=6 mozgás

6 parkolóhely, 5 autó, 5/2=2+1, 2*3+1=7 mozgás

7 parkolóhely, 6 autó, 6/2=3+0, 3*3+0=9 mozgás

...

21 parkolóhely, 20 autó, 20/2=10+0, 10*3+0=30 mozgás

A mozgatások minimumát nem lehet megmondani, az az autók sorrendjétől függ.

Az egyik szélső helyzet az, amikor mindegyik autó a helyére áll be.

Ez nem lehetetlen, csak kicsi a valószínűsége.

Az életszerűbb helyzet az, hogy csak egy részük áll jó helyen, a többi nem.

Legyen

N - az autók száma

J - a jó helyen állók száma

R - a rossz helyen levők száma

T - a tartalék (az üres) az üres parkolóhely

M - a menetek száma

Hogyan történhet a rendezés?

A jó helyen állókkal nem kell foglalkozni, csak a rosszakkal

Ezek száma

R = N - J

A gondnok a következő módon jár el:

1. Valamelyik rossz helyen álló autóval beáll a tartalék helyre, így keletkezett egy üres hely és maradt (R - 1) rendezendő autó

2. Megnézi az üres hely rendszámát, majd az oda való autóval beáll oda.

3. Így keletkezik egy új üres hely, ahová az oda való autóval beáll stb.

4. Ezt ismétli (R - 1)-szer

5. Ha már mindegyik autó a helyén van, a tartalék helyről beáll az utolsó üres helyre, ezzel a feladat végetért.

Hány mozgatás történt?

Az első pontban: 1

A 3-4 pontban: R - 1

az 5. pontban: 1

Összesen

M = 1 + R - 1 + 1

M = R + 1

vagyis a rossz helyen álló autók számánál eggyel több.

A legrosszabb esetben, ha kezdetkor minden autó rossz helyen áll, akkor

R = N

vagyis

M = N + 1

A példa adatával a maximum:

M = 21

Jó munkát a gondnoknak! :-)

DeeDee

********