Elképzelés a 158. feladatra: Tehát próbáljunk meg 14 üres mezőt úgy elhelyezni ezen a táblázaton, hogy a maradék 22-n mind legyen dominó. Mivel 6 sorunk és oszlopunk van, belátható, hogy 2 sorban és oszlopban legalább 3 üres mező lesz. Azt kell belátnunk, hogy nem tudunk úgy elhelyezni 14 üres mezőt, hogy a nem üreseket pedig dominó fedje. Vizsgáljuk csak a sorokat! Ha az első sorban 3 üres mezőt kívánunk elhelyezni, azt kétféleképpen tehetjük meg: (D a dominóval fedett, Ü az üres mező): (1) ÜDÜDÜD (vagy ennek szimmetrikus változata) ill. (2)ÜDÜDDÜ (és ennek is a szimmetrikus változata). A szimmetrikus változatok vizsgálatát elhagyhatjuk, hiszen azok lényegében ugyanazok mint az eredetik. Először nézzük meg, hogy ha egy sorban 3 üres mező van, akkor a következő sorban mennyi üres mező lehet maximum. Az (1) esetén 0, míg a (2) esetén 0 vagy 1. Nézzük az (1) elrendezést! Ekkor a második sorban DDDDDD lesz, hiszen az első sor 1.,3.,5. kockája alatt nem lehet üres mező, mert akkor lenne üres pár, így a második sor 1.,3.,5. mezője D-s lesz, a 2.,4.,6. mező pedig az első sor dominói miatt lesznek fedettek. Tehát a maradék 4 sorban 11 üres mezőt kellene elhelyeznünk. Mivel egy sorban 0,1,2,3 üres mező lehet és a 11-et 4 tag összegeként a 0,1,2,3 segítségével csak 2+3+3+3-ként lehet felírni, ezért a maradék 4 sorból háromban is 3 üres mezőnek kell szerepelnie. De ha a 3. sorban 3 üres mező van, akkor a következőben legfeljebb egy lehet, azaz a hátramaradó kettőben 7nek kell lennie, ami lehetetlen. Ha a harmadik sorban 2 üres mező van, akkor a negyedik már biztos 3 van, de az után legfeljebb csak egy lehet az ötödikben, azaz a hatodikban 5nek kell lennie, ami szintén lehetetlen. A (2) esetben a 2. sorban a legjobb esetben 1 üres mező szerepel. Az a maradék négy sorban 10. Ez kétféleképpen írható fel a 0,1,2,3 számok 4tagú összegeként: 1+3+3+3 vagy 2+2+3+3. Erről a két lehetőségről is könnyen beláthatjuk, hogy nem lehetségesek (hasonlóan mint az (1) esetben). Ha az első sorban 2 üres mező szerepel, azzal nem változott semmi, hiszen a 2 db 3 üres mezős sor elhelyezése abban az esetben sem lehetséges. Tehát beláttuk, hogy nem lehet elhelyezni 14 üres mezőt, úgy hogy a maradék 22-n mind dominó legyen, azaz legalább egy üres mező-pár lesz, azaz elhelyezhetünk még egy dominót úgy, hogy ne kelljen elmozdítani amár lerakott dominókat. (Picit hosszú megoldás, jobb lett volna egy rövidebb, "elegánsabb", de olyat nem találtam... talán valaki más...)
|