Valaki meg tudja oldani ezt a feladatot?

Hát akkor mondjuk nézzük az evidens esetet:

Ha n=1, akkor van egy 2x2-es sakktáblánk, amire 3 bábút helyezünk el. Magyarul 1 darab üres kocka marad a táblán. Igaz az, hogy elhagyhatunk 1 sort és 1 oszlopot úgy, hogy a megmaradt kockán nem lesz bábú? Szerintem igen.

Akkor legyen mondjuk n=2. Ekkor a sakktábla 4x4-es (16 kocka) és 6 bábút helyezünk el rajta. Igaz az, hogy elhagyhatunk 2 sort és 2 oszlopot úgy, hogy a megmaradt (marad 4 kocka) kockákon ne legyen üres bábú?

Kezdjük el végignézni a sorokat. Amíg nem vettük el mind az n sort, és olyan sorhoz értünk, amiben több bábu is volt azt vegyük el. Ezután két lehetőség van.

1) Elfogyott mind az n elvehető sor, és nem feltétlenül haladtunk végig mind a 2*n soron. Viszont ekkor legalább 2*n bábut elvettünk, tehát legfeljebb n maradt a táblán. Ez a legfeljebb n bábu legfeljebb n oszlopot jelöl ki, ezeket pedig el tudjuk hagyni minden gond nélkül, és készen vagyunk; a megmaradt részen nincs bábu.

2) Végig értünk mind a 2*n soron, de csak k ⩽ n sorban találtunk több bábut. Ez azt jelenti, hogy maradt még 2*n – k darab sor, amiből még n – k darabot vehetünk el, és mindegyiken legfeljebb 1 darab bábú van. Ez összesen legfeljebb 2*n – k darab bábu, amit nyilván el tudunk venni, mert maradt még összesen n – k + n darab elvehető sor és oszlop.

(((> „van legalább 1 olyan eset,”

Mikor mondunk két esetet különbözőnek? Ugye 6 bábut 16 mezőre 8008-féleképpel lehet letenni, ami még a négyzetszimmetriák figyelembe vételével is 1000 eset. Ezek mindegyikére meg kell mutatni, hogy el tudunk venni 2 sort és 2 oszlopot úgy, hogy ne maradjon bábu, és csak akkor van belátva n = 2-re. (n = 3-ra meg már milliónyi eset van.)

> „akkor azzal a feltevés bizonyítva van,”

Hol olvastál te olyat, hogy tegyünk fel valamit? A feladat állítása amúgy biztos nincs bizonyítva ennyivel.

> „hiszen ha n-re igaz és n+1-re is igaz, akkor abból már skatulyaszerűen következik, hogy n+2, n+3... esetre is igaz lesz az állítás.”

Nem 'dominószerűen'-t akartál írni? Csak mert az egyrészt nem elég, hogy n két értékére igaz legyen az állítás (ugyanis az n = 1 és a n + 1 = 2 centiméteres magasságot szinte bárki át tudja ugrani, de például n = 1000-re nem találsz embert); másrészt a skatulya-elvet úgy tudod alkalmazni, hogy ha megmutatod, hogy több dolgot kell skatulyázni, mint ahány skatulya van. Vagy most 'skatulyaszerűen' alatt valamik egymásba ágyazását érted?

Természetesen örömmel olvasnék egy _helyes_ teljes indukciós bizonyítást, mert valószínűleg tanulságos lenne, de a népbutítást nem szeretem; nem azt mondom, hogy szájbarágósan meg kell oldani a kérdező háziját, de attól még hülyeségeket nem kell neki írni „segítség” címszó alatt, mert az rossz az egész társadalomnak, és sajnos nem csak a kérdezőnek. Persze tévedni emberi dolog, ha a 01:55-ös válaszadóval is így történt, akkor bocsánatot kérek a kioktatásért; és el van felejtve. Néha mindenkinél kiborul a bili… :) )))

Nem a skatulya-elvről beszéltem. Amit én leírtam az lényegében a teljes indukció, de teljesen mindegy, mert nem ezen van a hangsúly, én is csak utólag vettem észre a hasonlóságot. A lényeg azon van, hogy én "n" helyére elkezdtem behelyettesíteni a számokat és megvizsgáltam igaz-e az állítás.

"Hol olvastál te olyat, hogy tegyünk fel valamit? A feladat állítása amúgy biztos nincs bizonyítva ennyivel."

A feltevés az volt, hogy el tudunk hagyni n sort és n oszlopot úgy, hogy nem marad bábú a táblán és ezt igazoltuk úgy, hogy tényleg volt olyan eset, amikor a tábla üres lett. Az én értelmezésben nem az a feladat, hogy az összes lehetséges bábulerakás esetén meg kell tudnunk ezt csinálni (akkor úgy lett volna megfogalmazva a feladat, hogy "biztosan elhagyhatunk n sort és..."), hanem hogy létezik olyan eset, amikor ez igaz.