Az asztalon 4 piros és 4 kék korong van elhelyezve, valamint két üres hely is van az alábbi elrendezésben: PKPKPKPK _ _ (?)

Kövezzetek meg, de nekem segítene, ha leírnád a példádat, hogy mi ez a 6 lépés.

Utána megpróbálok rá válaszolni.

Az biztos, hogy legalább 4 lépést meg kell tenni, mivel két K-t el kell pakolni és azok helyére két P-t berakni.

Szóval vagy 4, vagy 5, vagy 6 lépésre szükség van.

Sajnos a megoldásra nem jöttem még rá. Általánosságban elmondható ilyen esetben, hogy célszerű egy adott állapot olyan tulajdonságát megtalálni, ami számmal értékelhető, tehát minden állapothoz hozzá lehet rendelni egy számot. És erre igaznak kell lennie, hogy egy lépés során maximum 1-el csökkenhet, vagy más esetben 1-el nőhet. Továbbá meg kell határozni a végső állapot számát.

Így pl. ha az első állapot 6-os számot kap és bizonyítható, hogy az érték max egy-el csökkenthető, a végső állapot 0, akkor az előzőek alapján bizonyítható, hogy 6 lépésnél kevesebbel nem megoldható.

Ez az általános elv, ami sokszor be szokott jönni más feladatoknál.

Nem találtam még sajnos ilyen tulajdonságot.

(Ez lehet a jó helyen álló korongok száma, megfelelő párral rendelkező korongok száma vagy bármilyen tulajdonság, ami számszerűsíthető. Sajnos nem találtam még olyat, ami a bizonyításhoz jó lenne.)

Sajnos csak ennyit tudok segíteni egyelőre. Azért leírtam, hátha ötletet ad valakinek.

Másik ötletem bizonyításra (ez is elméleti, ilyen tulajdonságot sem találtam még):

Szintén minden állapothoz valamilyen módon rendeljünk egy számot. Minden lépésben ez a szám monoton nő vagy csökken. Minden lépés esetén bizonyíthatóan a lehető legnagyobb mértékben csökkentjük vagy növeljük a cél éréséig. Akár lépésenként az összes lehetőség (nem túl sok) végig vizsgálásával.

Ezzel biztosítjuk, hogy a lehető leggyorsabban érünk célt, tehát nincs kevesebb lépésből álló megoldás.