Feladat: C.725 Korcsoport: 14-15 Nehézségi fok: könnyű
Megoldó(k):  Daróczi László 
Füzet: 2004/március, 138 - 139. oldal  PDF  |  MathML 
Témakör(ök): Logikai feladatok, C gyakorlat
Hivatkozás(ok):Feladatok: 2003/szeptember: C.725

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.

Megoldás. Tekintsük a táblázat három sorát. Ezeknek nincs közös része, és mindegyikükben lennie kell legalább egy fejnek. Ez azt jelenti, hogy legkevesebb 3 érmét mindenképpen meg kell fordítanunk, és ezeknek mind különböző sorokban és ugyanígy különböző oszlopokban kell elhelyezkedniük. Ha egyik sarokban sem lenne fej, akkor csak az 1. ábrán bejelölt helyek jöhetnek szóba; ezek közül viszont nem választható ki három úgy, hogy mind különböző sorban és különböző oszlopban legyenek. Így valamelyik sarokban fejnek kell állnia; legyen ez például a bal felső.

 

 
1. ábra
 

A különböző sorok és oszlopok követelménye szerint ekkor a másik két fej kétféleképpen helyezhető csak el (1-es és 2-es eset, 2. ábra). Látható, hogy az 1-es esetben három fej esik egy átlóra, a 2-esben pedig az egyik átlóban csupa írás marad; 3 érme megfordítása tehát nem elegendő, legalább 4-re van szükség. Ez viszont már elegendő is, egy lehetséges elrendezés látható a 3. ábrán.
 

 
2. ábra
 


 
3. ábra
 

Általánosíthatjuk a feladatot 3×3-as helyett n×n-es táblázatra, ahol n≥4. Ilyenkor (n≥4-re) már elég n érmét megfordítani; egy megfelelő választás látható a 4. ábrán.
 

 
4. ábra