Ki lehet-e választani az első 100 pozitív egész szám közül 51-et úgy, hogy nincs köztük olyan számpár, ahol az egyik többszöröse a másiknak?

#10

Akkor a fenti bizonyítással egyetértesz? Elfogadod?

Nem, nem fogadom el, mert ez nem bizonyítás, és azért nem, amiért leírtam.

Ez maximum akkor tudna működni, hogyha az ÖSSZES szóbajöhető számötvenest felvonultatnád, és mindegyikre egyesével belátnád, hogy nem tudsz még egyet hozzájuk venni. Az, hogy mindig csak egyet tudsz cserélni, az sem feltétlenül igaz.

Elmondom más szavakkal:

Több lépesben történik a számok kiválasztása

- elöször kiválasztjuk a számokat 51-től 100-ig. De ez a kiválasztás nem végleges.

- kellenének számok az 1-50 tartományból is. Nem egy, sok. A kiinduló 50 és a hozzáadott számok együtt bármelyik 1-100 kiválasztást kiadja.

De olyan 1-50 számokat kell keresnünk, amikkel növelhetjük a "megfelelő" számok számosságát. Ami lehetetlen mert, amikor a halmazhoz hozzáadunk egy 1-50-es számot, a meglevő halmazunkban a kétszerese "nem megfelelővé" válik. Tehát be tudjuk venni a halmazba bármelyik számot, de a számosság nem fog a kiinduló 50 fölé növekedni.

Ez egy teljes indukció.

Van egy kiinduló helyzet, amiben kevesebb mint 51 számunk van.

Van egy sok "lépés"-ből álló módszer, amivel bármelyik további számot hozzá tudjuk adni a halmazunkhoz. A módszerrel bármely olyan végállapot előállítható ahol egyetlen szám sem többszöröse a másiknak.

A "lépés" előtt 51-nél kevesebb számunk van. És a lépés után is 51-nél kevesebb számunk lesz, mert, ha hozzáadunk a halmazhoz egy 1-50 számot, akkor ki kell vennünk egy 51-100 számot. (A kétszerest)

Más bizonyítás:

Tegyük fel, hogy sikerült a feladatnak megfelelő számhalmazt előállítani. Az 1-es nem lehet a halmaz eleme, mert az kizárna 99 számot. A 2-es nem lehet a halmaz eleme, mert akkor csak 1 páros számunk és 49 páratlan számunk lenne.

Induljunk el a halmaz elemein alulról felfelé 3-tól 50-ig. Amíg van ilyen k szám, addig igaz az, hogy a 2k nincs benne a halmazban. Vegyük ki k-t és tegyük be 2k-t. Megtehetjük, mert k-nál kisebb szám már nincs a halmazban, ezért 2k-nak nincs osztója. A cserével nem zártunk ki más számokat, mert ami 2k-val osztható lenne, az k-val is osztható, ezért nem lehetett a halmazban. Így számról számra haladva lecseréljük az 1-50 számokat, miközben a halmaz számossága nem változik.

Marad legfeljebb 51-100-ig a számsor, a mi legfeljebb 50 szám.

A 19-es bizonyítás jónak tűnik.

Másik megoldás, a skatulyaelvvel; tegyük fel, hogy legfeljebb 50 szám vehető ki. Azt látjuk, hogy ha az utolsó 50 számot választjuk, akkor 50 szám kiválasztható.

Ha meg tudunk konstruálni 50 darab skatulyát, akkor azzal belátjuk, hogy az (indirekt) állítás igaz lesz. A skatulyákba csak úgy tehetőek számok, hogy egyidőben csak egyféle szám vehető ki, ezzel biztosítva azt, hogy 50-nél több szám nem választható ki, tehát a számok úgy helyezkednek el, hogy bármely két szám közül egyik osztója a másiknak (például 1-2-4-8), vagy csak egy szám áll a skatulyában (például a 89). Egy lehetséges skatulyarendezés;

100 50 25 5 | 99 33 11 | 98 49 7 | 97 | 96 48 24 12 6 3 | 95 19 | 94 47 | 93 31 | 92 46 23 | 91 13 | 90 45 15 | 89 | 88 44 22 | 87 29 | 86 43 | 85 17 | 84 42 21 | 83 | 82 41 | 81 27 9 | 80 40 20 10 2 | 79 | 78 39 | 77 | 76 38 | 75 | 74 37 | 73 | 72 36 18 | 71 | 70 35 | 69 | 68 34 | 67 | 66 | 65 | 64 32 16 8 4 | 63 | 62 | 61 | 60 30 | 59 | 58 | 57 | 56 28 14 | 55 | 54 | 53 | 52 26 | 51

Az 1 számot nem írtam be sehova, mert akármelyik skatulyába nyugodtan beírható.

Tehát sikerült 50 skatulyát kialakítani, amelyekbe az összes számot el tudtuk helyezni, és mindegyik skatulyából pontosan 1 szám vehető ki. Tehát 51 számot nem tudunk kivenni úgy, hogy valamely kettő ne legyen osztója egymásnak.

Persze ha nagyobb számhalmaz lenne, akkor nehezebb lenne a dolgunk, így annál már más megoldási módra lenne szükség, mint mondjuk a 19-es válasz.