Matematika/logika feladat. Valaki segítene?

Több dolgot sem értek:

"Adott 11 páronként különböző egész szám"

Milyen az a páronként különböző egész szám?

"egyikének sincs 30-nál nagyobb prímosztója"

A 30-nál nagyobb első prímszám a 31. Tehát ez azt jelentené, hogy mindegyik kisebb 31-nél?

A páronként különböző azt jelenti, hogy bármelyik két számot választva egyikük sem egyenlő, magyarul van 11 különböző számunk.

Az, hogy nincs 30-nál nagyobb prímosztója, az azt jelenti, hogy a 2;3;5;7;11;13;17;19;23;29 számok szorzataként felírható.

Skatulya-elvvel megoldható:

Az egyszerűség kedvéért vegyük csak azokat a prímhatványokat, amik egy szám hatványaként felírhatók: kettő-hatványok, három-hatványok, stb.

Az állítás akkor és csak akkor teljesül, ha van legalább két számunk, amiknek legalább 1 prímosztója megegyezik. Tegyük fel indirekt, hogy ez az állítás sosem valósul meg. Ez azt jelenti, hogy minden skatulyából pontosan 1 számot veszünk ki. Ezzel a módszerrel 10 számot tudunk kiválasztani, viszont a feladat állítása szerint 11 számra teljesül a feltevés, de ha még egy számot kell választanunk, akkor valamelyik olyan skatulyából kellene húznunk számot, amelyikből már egyszer vettünk, amire tudjuk, hogy akkor már lesz 2 olyan szám, amire teljesül a feltevés. Így ellentmondásra jutottunk, vagyis a tagadás hamis, így az eredeti állítás biztosan igaz.

> Milyen az a páronként különböző egész szám?

Pontosan azt jelenti, ami le van írva. Nincs két olyan szám, ami egyforma lenne. Persze az „adott 11 egymástól különböző szám” is megtette volna, de ez is helyes megfogalmazás.

> egyikének sincs 30-nál nagyobb prímosztója

Magyarán egyik primtényezője sem nagyobb 30-nál.

~ ~ ~ ~ ~

Egy kicsit elakadtam a megoldásban, de nyomon vagyok. Ugye tíz darab olyan prímszám van, ami 30-nál kisebb. Minimum egy szám tehát összetett. Ha mindegyik szám primszám lenne a 11 közül, akkor természetesen bármelyik részhalmaz szorzata olyan szám lenne, ami kizárólag prímszámok első hatványainak szorzata lenne, tehát nem lehetne négyzetszám.

Ha valamelyik számnak minden prímtényezője páros hatványon van, akkor az adott szám önmagában négyzetszám, ezért ebben az esetben egyetlen számot kiválasztva igaz lenne az állítás. Pl.: 2^8 * 3^10 = (2^4 * 3^5)^2

Ha egy számban valamelyik prímtényező páros hatványon van, és ezt olyan számmal szorozzuk, hogy a szorzat négyzetszám lesz, akkor tulajdonképpen a páros hatványon álló prímtényező nem játszik szerepet. Pl.: (5^4 * 7^3) * (11^2 * 7) = 5^4 * 7^4 * 11^2 = (5^2 * 7^2 * 11)^2

Ha a páros hatványon lévő prímtényezőkkel elosztom az eredeti számokat, úgy akkor és csak akkor lesz négyzetszám az egyszerűsített szorzat, ha az eredeti szorzat is négyzetszám. Jelen esetben:

5^4 * 7^3 = (5^4 * 7^2) * 7 = (5^2 * 7)^2 * 7 → 7

11^2 * 7 → 7

Tehát ha konstruálunk egy olyan sorozatot, amiben minden szám prímszám, vagy prímszámok első hatványainak szorzata és erre bizonyítjuk az állítást, akkor az eredeti állítást is bizonyítottuk, hiszen ha ezekből egy részhalmaz szorzata négyzetszám, akkor bármelyik tagját megszorozva egy négyzetszámmal szintén négyzetszámot kapunk.

A feladat innen ekvivalens a következő megfogalmazással: Adott 11 kettes számrendszerű szám, maximum 10 számjeggyel. Bizonyítsuk be, hogy létezik olyan részhalmaza ennek a 11 számnak, ahol a részhalmaz elemein XOR műveletet végzünk, akkor az eredmény 0 lesz. (Itt minden számnál az adott számjegynél megjelenő 1-es azt reprezentálja, ha az eredeti feladatban az adott prímszám páratlan hatványon van. A helyiértékek jelentik az első 10 prímszámot.)

Ennél az átírt feladatnál igaz lesz, hogy minden szám legalább egy egyest tartalmaz. (Ha nem, akkor eleve az adott szám négyzetszám, tehát a feladat megoldott.) Létezik legalább egy helyiérték, ahol az adott helyiértéken legalább 2 szám esetén 1-es található.

Látható az is, hogy amelyik helyiértéken csak egy szám esetén van 1-es, az nem szerepelhet a részhalmazban .(Különben az eredmény nem lenne nulla. Az eredeti feladatra átfordítva, ha egy prímtényező csak az egyik számban jelenik meg, az nem lehet a szorzat része, hiszen az adott prímtényező nem lehetne páros hatványon a szorzatban.) Ha egy helyiértéken három vagy több, de páratlan számú esetben szerepel egyes, ott az egyik nem szerepel a részhalmazban.

Egyelőre eddig jutottam.

"Az állítás akkor és csak akkor teljesül, ha van legalább két számunk, amiknek legalább 1 prímosztója megegyezik"

az csak annyit mondana, hogy a szorzat osztható egy (egynél nagyobb) prímszámmal.

A feladat viszont azt kéri, hogy a szorzat maga legyen négyzetszám.

--------------------

Ez a feladat volt a Szőkefalvi-Nagy Gyula Matematikai Emlékversenyen, de ha jól látom, akkor annak a beküldési határideje már lejárt.

Valami házifeladat akkor talán?

Amúgy ha tanultál vektortereket, akkor azokkal elég könnyen kijön (a feladat lényegében nem más, mint hogy a 2 elemű test felett vett 10 dimenziós vektortérből veszünk 11 tetszőleges vektort, és bizonyítsuk be, hogy ezek nem lineárisan függetlenek - ami a vektorterek egyik legalapabb tulajdonsága).

Ha nem, akkor pl. ez egy nagyon jó lehetőség átolvasni őket (wikin tök jól le van írva), megérteni, és gyakorló feladatként elsütni erre a feladatra - esetleg azt is végiggondolva, hogy ennek a gondolatmenetnek mentén hogyan lehet a bizonyítást elmondani vektorterek nélkül.

És akkor nekem sincs rossz érzésem, hogy esetleg érdemtelenül jutattam valakit valamilyen iskolai háziversenyben jogtalan előnyzö azáltal, hogy megmondtam neki a megoldást, mert így ahhoz, hogy értsd a megoldást, önszorgalomból tanulnod és dolgoznod kell vele.

közben átolvastam a korábbi hosszabbat is, és ott lényegében tök jól le van írva a vektorteres megfeleltetés, csak nincs használva ez a szó.

Azt is be lehet fejezni egy kis ötlet segítségével, és akkor nem kell a vektortereknek utánanézni (bár ha azt megérted, akkor ott meg nem kell ötlet), annyit segítek, hogy skatulya-elv.

Nagyon tetszik a vektorteres megoldás. És nagyon jó a bináris számmá való leképzés ötlete is. Annak a bizonyításnak a befejezése mehet kombinatorikával is: 2 elem 10-ed illetve 11-ed osztályú ismétléses variációival. Nem fejtem ki végig, gondolkozz rajta, kérdező, úgy érdekesebb ... :)

(Az is lehet, hogy a #6 hozzászólásban pont ugyanerre gondoltál, amikor a skatulya elvet mondtad?...)