Egy 4x4-es táblába írandó betűk: A, B, C, D. Minden sorban, minden oszlopban és mindkét átlóban mind a négy betűnek szerepelnie kell. Ha a bal felső mezőben A van, akkor hányféleképpen tölthető ki a tábla az előírásnak megfelelően?

Én úgy kezdtem, hogy felírtam, hogy mivel 4x4-es a táblázat így 16 eleme van. A feltételekből világos, hogy pontosan 4 db szükséges a táblázatban mindegyik betűből. Mivel az egyik A helye már meg lett adva, így abból nekünk csak 3-mat kell beírnunk. Kis átgondolással(a többi A helyeit alapból csak a jobb alsó 3x3-mas táblázatba keressük a feltételek miatt, és az átlós feltétel miatt abból is kiesik 3 hely) könnyen bizonyítható, hogy ezt kétféleképpen tehetjük meg:

1) 1. sor 1. oszlop ; 2. sor 3. oszlop; 3. sor 4. oszlop ; 4. sor 2. oszlop

2) 1. sor 1. oszlop ; 2. sor 4. oszlop; 3. sor 2. oszlop; 4. sor 3. oszlop;

Én eddig jutottam.

Innentől lehet próbálkozni tovább, hogy mi van ha pl 1. sor 2. oszlopba B-t írok, vagy C-t stb és onnantól az esetszámokat összeszorozni. Nem hiszem, hogy lesz 64-nél több eset, ha tudsz programozni brute force módszerrel simán megcsinálja egy program pillanatok alatt, főleg a plussz feltételekkel amiket írtam. Ha nem, igazából te is meg tudod papíron.

Esetleg matematikai oldalról is meg lehetne közelíteni, biztos vagyok benne hogy vissza lehet vezetni a problémát egy általánosabbra, de azt most nem tudom megmondani mire.

A feladat kulcsa az, hogy a főátlókon lévő mezőknek kell a legtöbbet tudniuk. Nem mondok azzal újat, hogy (ha egyáltalán létezik ilyen kitöltés), akkor mindegyik betűből kell, hogy legyen a sarkokban. Ilyen kitöltésből (6)-féle van.

Vegyünk egy konkrét kitöltést;

A__B

____

____

C__D

Most a középső mezőkre koncentráljunk; ha megfigyeljük, akkor az A-D és B-C betűk ugyanarra a kér helyre mehetnek. Hogy az A-D betűket hogyan írjuk fel, még nincs hatással semmire, ebből vegyük az egyik esetet;

A__B

__A_

_D__

C__D

Most nézzük a B-C betűket. Adott esetben kétféle lehetőség van;

A__B

_CA_

_DB_

C__D és

A__B

_BA_

_DC_

C__D

Az első felállás nem túl szerencsés, mivel például az első sor második helyére nem tudunk mit írni. Ellenben a második felállás nagyon szerencsés; olyannyira, hogy csak egyféleképpen tudjuk kitölteni;

ACDB

DBAC

BDCA

CABD

Tehát

-az első lépésnél (sarkok kitöltése) 6-féle lehetőség volt,

-a második lépésnél (A-D beírása) 2-féle lehetőségünk volt,

-a harmadik lépésnél (B-C beírása) látszólag kétféle lehetőségünk volt, de valójában csak 1-féle lehetőségük volt

-a negyedik, egyben utolsó lépésnél (a többi mező kitöltése) 1-lehetőségünk volt, mivel a betűk helye egyértelművé vált.

A lépéseknél kapott lehetőségek számát összeszorozzuk (most nem megyek bele mélyen, hogy miért), így 6*2*1*1=12-féle lehetőség van a kitöltésre.