Egy 3 × 3-as táblázat 9 mezőjének mindegyikét pirosra vagy kékre színezem úgy, hogy mindegyik sorban és mindegyik oszlopban szerepeljen mindkét szín. Hányféleképpen tehetem ezt meg?

Én másképp indulnék el; koncentráljunk csak az egyik színre, például a kékre. Hány kék mezőre van szükségünk?

0, 1 vagy 2 kevés lesz, 3-nál és 4-nél látjuk, hogy megoldható, 5-nél és 6-nál is, de színszimmetriai okok miatt azzal nem kell foglalkoznunk, ugyanis például a 3 kék - 6 piros és a 6 kék - 3 piros színkombinációkból ugyanannyi van, így elég csak az eredményeket beszorozni 2-vel. A 7, 8 és 9 pedig túl sok.

Nézzük a 3 kék esetét; haladjunk soronként, fentről lefelé. Az első sor bármelyik mezőjét beszínezhetjük kékre, ez 3 lehetőség. A második sorban már csak 2-féle színezési lehetőségünk van, az utolsó sorban pedig már csak egyféle, így 3*2*1=6-féleképpen tudjuk a 3 kéket lerakni. Tehát ha összesen van 3 kékünk, akkor 6-féle színezési lehetőségünk van. Természetesen a színezések sorrendje nem számít, ezért lehet egy konkrét színezési sémát kiválasztani, ami alapján festünk.

A 4 kék esetén (ahogy látom) már egy kicsit nehezedik a terep. Ha az előbb számolt 6 színezésből indulunk ki, vagyis ezekhez akarunk még egy kéket betenni, amit még 6-féleképpen tudunk megtenni, akkor 6*6=36 esetet számolunk meg, ezt még szorozzuk 2-vel a színszimmetria miatt, akkor 72-t kapunk, + 12 a 3 kékes esetből, tehát legjobb esetben is csak 84-féle jó színezés lehet, ehhez képest a 144 nagyon sok.

Mivel nincs sok eset, ezért "rajzolósan" meg lehet oldani, vagyis felrajzoljuk azt a 36 esetet, amikor összesen 4 kék van, és megnézzük, hogy azokból hány azonos. Kombinatorikai megoldást egyelőre nem látok.

Úgy tűnik, hogy indirekt számítással hamarabb célt érünk, vagyis azokat az eseteket számoljuk meg, amikor nem teljesülnek a feltételek.

Minden megkötés nélkül 2^9 = 512-féleképpen tudjuk kiszínezni a táblázatot.

Megint maradjunk a kékeknél;

-0 kék mező van: 1 lehetőség

-1 kék mező van: 9 lehetőség

-2 kék mező van: (9 alatt a 2) = 36

-3 kék mező van: itt már meg kell néznünk, hogy melyek azok az esetek, amikor nincs mindegyik színből mindegyik sorban:

a) Mind a három szín azonos sorban/oszlopban van: 6 lehetőség

b) Két szín azonos sorban/oszlopban (ezt most hívjuk összefoglalónéven sávnak), a harmadik pedig minden szempontból ezektől eltérőben: az első mezőt 9-féleképpen tudjuk befesteni, a másodikat szeretnénk, hogyha az elsővel azonos sávban lenne, erre 4 lehetőségünk van, így az első két mezőre 9*4/2=18 lehetőségünk van. Az utolsó mezőt már csak 2-féleképpen tudjuk lefesteni, így 18*2=36 lehetőséget számoltunk meg.

c) Két-két szín azonos sávban van. Itt is az első mezőt 9-, a másodikat 4-féleképpen tudjuk lefesteni. A harmadik mezőnek az előbbiek valamelyikével kell azonos sávba kerülnie, erre 4 lehetőség van. 9*4*4=144, de a színezés sorrendje nem számít, ezért osztunk 3!-sal, vagyis 6-tal, így 24-féle lehetőséget tudunk megszámolni.

Ezzel pedig lefedtük a rossz lehetőségek körét 3 kék esetén.

Nézzük a 4 kéket:

a) 3 szín azonos sávon van, a negyedik bárhol lehet: (9*4*1)/3! * 6 = 36.

b) A kék mezők négyzetet/téglalapot alkotnak ekkor egy sor és egy oszlop nem fog a kékből kapni: tekintve, hogy tudjuk, hogy egy sor és egy oszlop nem kap a kékből, érdemesebb azt megnézni, hogy hányféleképpen tudjuk ezeket kiválasztani; 3*3=9, tehát 9 esetben lesz egy-egy olyan sor és oszlop, hogy azokban nincs kék.

c) Csak az egyik sávon nincs kék úgy, hogy egyik sáv sincs teljesen lefestve: megtehetjük azt, hogy azt a sávot lezárjuk, tehát oda nem megy kék, így a maradék 6 mezőt kell kiszíneznünk kékkel, ezt (6 alatt a 4)=15-féleképpen tudjuk megtenni. Mivel 6 sáv van, ezért 15*6=90 színezést tudunk megszámolni. Azonban ebben a számolásban megszámolásra kerülnek újra az a)-ban lévő esetek, tehát őket le kell vonnunk: 90-36=54, valamint a b)-ben számolt esetek kétszer, tehát azok kétszeresét le kell vonnunk: 54-2*9=36, tehát 36 olyan eset van, amikor pontosan egy sáv nem kap a kékből.

Más lehetőség nincs.

Összesen tehát 1+9+36+6+36+24+36+9+36=193 esetben tudjuk a kékeket lerakni úgy, hogy a feltételek nem teljesülnek. Ezt szorozzuk 2-vel, így 386 "rossz" színezés van, így 512-386 = 126 jó színezés van.

Lehet, hogy van hiba a levezetésemben, még gondolkodom rajta.

Ha jól gondolom, megtaláltam a direkt számításnak a módját;

-Ha 3 kékkel színezünk, azt már leírtam: 6

-Ha 4 kékünk van, akkor a színezéseket csoportosítsuk aszerint, hogy hány sarkot színezünk be:

a) Ha egyik sarkot sem színezzük, akkor a maradék 5 mezőből kell 4-et színezünk, erre egyébként 5 lehetőségünk van, viszont ezek közül csak 1 lesz helyes, amikor az oldalnégyzeteket festjük be.

b) Ha csak az egyik sarkot festjük, akkor azt tapasztaljuk, hogy az ehhez "lóugrásban" lévő mezőket mindenképp be kell festenünk, ezzel viszont már teljesül a feltétel, így az utolsó színt a megmaradt 3 mező bármelyikére tehetjük, tehát ha csak 1 konkrét sarok van színezve, akkor 3 lehetőségünk van. Mivel 4 sarok van, ezért 3*4=12.

c) Ha csak két sarkot festünk, akkor azt kétféleképpen tehetjük;

1. Ha a nagy átlón lévőket választjuk, akkor a megmaradt kékeket (5 alatt a 2) = 10-féleképpen tudjuk elhelyezni, de két esetben nem kapunk megfelelő színezést (amikor a két kéket azonos sávba tesszük oldalnégyzetekre), emiatt 8 jó színezésünk van. Mivel a főátlót 2-féleképpen lehet megválasztani, ezért itt 2*8=16 a jó színezések száma.

2. Egy sávon lévő sarkokat színezünk, ekkor a hozzájuk képest lóugrásban lévő (közös) mezőt kötelező befestenünk. Ha ez megvan, akkor 1 sáv marad, amelyiknek nem jutott kék, így annak bármelyik mezőjére tehetjük a kéket, ez 3 lehetőség. Mivel a sarkokat 4-féleképpen választhatjuk meg, ezért 3*4=12.

d) Ha 3 sarkot festünk, akkor a két középső sávnak nem jut kék, így ezek metszetébe, tehát középre kell tegyük a 4.-et. Mivel a 3 sarkot 4-féleképpen tudjuk megválasztani, ezért itt 4 lehetőség van.

e) Mind a 4 sarkot színezzük, ezt 1-féleképpen tudjuk, viszont ez nem megoldás.

Összesen tehát 6+1+12+16+12+4=51 esetben tudjuk a kékeket lerakni, ezt szorozzuk 2-vel, így 51*2=102-féle jó színezés van.

Ezt a megoldást kicsit erősebbnek érzem, mint az előzőt.

Szerintem is 102=6*17 a megoldás.

Az első sor 6 féle lehet. Mindegyik első sorhoz 17 megoldás tartozik.