Ezen a héten egy kicsit matematikaibb rejtvényt kaptok ajándékba:
Tekintsük a következő P(n) állítást: egy n törpből álló olyan csoport, amiben van egy süket törp az kizárólag süket törpöket tartalmaz. P(1) triviálisan igaz. Most tegyük fel, hogy P(m) igaz valamilyen m-re. Legyen G egy m+1 törpből álló csoport, amiben van egy süket törp. Jelölje x ezt a süket törpöt. Ha x-hez hozzáveszünk G-ből m-1 másik törpöt, akkor az így kapott H csoport egy m törpből álló csoport lesz, amiben van egy süket törp. Mivel P(m) igaz, így H-ban csak süket törpök vannak. Legyen y az a törp, akit kihagytunk H-ból. y és m-1 törp H-ból egy olyan m tagú K törpcsoportot alkot, amiben van legalább egy süket törp, hiszen H-ban csak süket törpök vannak, így az indukciós feltevést ismét használva biztosak lehetünk benne, hogy y is süket törp, tehát G kizárólag süket törpökből áll. Bebizonyítottuk tehát, hogy ha van egy süket törp, akkor minden törp süket.
Vagy mégse?
Köszönet Hannák Gábornak a javaslatért. Ha másnak is van rejtvény javaslata, akkor küldhetitek.
2 responses to “süket törpök”
Twitteren belekezdtem a valaszba, de ra kellett jonnom: keves a hely. Szoval, mindenfele kombinatorikai ismeret nelkul:
az az alapfelteves lesz rossz, hogy P(m) igaz valamilyen m-re, mert P(m) akkor es csakis akkor igaz, ha m=1 viszont m != 1 -re sosem lesz az (ne haragudj a programozoi egyenlotlenseg jelert, nem tudom hogy kell berini a megfelelo unicode jelet). Ha G egy m+1 tagbol allo csoport, akkor G tagjainak szama legalabb 2, hiszen P(0) -ra nem tud igaz lenni az allitas (semmilyen torp nincs a 0 tagu csoportban, se suket, se masmilyen), marpedig G csak akkor lehet 1 tagu, ha m=0. A H csoport gyakorlatilag megegyezik a G csoporttal, hiszen a G-bol az osszes nem suket torpot is atvesszuk, vagyis az allitas szinten csak akkor lehet igaz, ha G eredeti letszama nem volt tobb, mint 1, vagyis nem volt benne mas, mint Mr. X, a suket torp.
Vegyük a bizonyításból m=1 esetét.
Ekkor veszünk egy 2 törpből álló halmazt.
Ebből az egyik törp x.
A G ből m-1=0 további törppel tudunk egy H csoportot csinálni x-el.
Így nincs legalább egy törp aki biztosan süket de nem x,
hogy teljesítse az indukcós bizonyításban a K csoportra való feltételt,
így a bizonyítás ellentmondásra vezetett.