Bizonyítsd be, hogy tetszőleges 100 természetes szám közül biztosan találni néhányat (esetleg egyet), melyek összege osztható 100-zal. Tudnátok segíteni?

Osszuk fel a 100 számot csoportokba aszerint, hogy százzal osztva mennyi a maradék. A maradékok alapján 0-99, legfeljebb 100 csoport képezhető, de ha 0 a maradék, akkor már teljesül a feltétel, tehát legfeljebb 99 olyan csoport lehet, ami nekünk első körben nem megfelelő.

Most nézem, hogy összeget írtál, ez biztos?

Különbségre lehet bizonyítani, de összegre nem.

Ellenpélda: 99 db szám, aminek 51 a maradéka, a századiknak meg 50, nem tudsz kiválasztani...

Storno, az ellenpélda mégse jó, mert 50*51+50 már osztható 100-zal.

A maradékosztályokat ha nézzük, akkor azok párba állíthatók, 1-99, 2-98, stb... - ezekből választva egyet-egyet megint osztható 100-zal az összegük.

Ha ellenpéldát akarunk találni, akkor vegyünk egy tetszőleges x számot valamelyik osztályból, zárjuk ki a 100-x osztályt, mert abból nem vehetünk számot.

Vegyük a következő y számot.

Két eset lehetséges. Ha ugyanabból az osztályból származik, akkor a 100-x = 100-y osztályt már kizártuk, de a 100-(x+y) mod 100 osztályt is ki kell zárjuk, különben megint 100-zal osztható számhoz jutunk.

Ha másik osztályból veszünk számot, akkor a 100-y osztályt kell kizárnunk, illetve a 100-(x+y) mod 100 osztályt.

Ezt az eljárást követve legfeljebb 99 osztályt zárhatunk ki, mert több nincs, mivel minden egyes szám választásánál legalább egy újabb osztályt ki kell zárnunk.

Hmmm, fogas kérdés, s nem túl egzakt a levezetés, de most jobb nem jut eszembe...

Képezzük a következő összegeket:

a1

a1+a2

a1+a2+a3

.

.

.

a1+a2+...+a99

a1+a2+...+a99+a100

100 db egész számot kaptunk, mik lehetnek a 100-as maradékok?

Ha van közöttük 0 maradék akkor az adja a megoldást.

Ellenkező esetben kell lennie legalább két azonos maradékúnak, ekkor ezek különbsége a megoldás.