A 6. feladat

Feladatok illetve megoldásaik, az elme frissen tartására.

A 6. feladat

HozzászólásSzerző: G.Á » 2018.04.18. 16:28

Egy matematika-feladványt osztok most meg, amelyik viszonylag híres, és érdekes történet kapcsolódik hozzá.

Legyenek a és b pozitív egész számok, és [math].
Mutassuk meg, hogy ha k egész, akkor k négyzetszám.
G.Á
 
Hozzászólások: 1087
Csatlakozott: 2016.12.25. 15:27
Has thanked: 57 times
Been thanked: 294 times

Re: A 6. feladat

HozzászólásSzerző: G.Á » 2018.05.03. 23:49

Van egy viszonylag elegáns geometriai megoldás. Tekintsük az "a" és "b" számokat egyelőre változóknak, és vizsgálódjunk az a-b síkon.

Viszonylag könnyen belátható, hogy ha a feladatban szereplő "k"-t rögzítjük, az az a-b síkon hiperbolákat jelöl ki.
A feladat összességében két részre válik, egyrészt érdemes megvizsgálni az a=b egyenest, utána a hiperbolákat.

Csak az egyenest tekintve, az egyenlet [Renderelés ... k(1+a^2)=2a^2], és a feladat szövege alapján, feltételezzük, hogy "k" egész.

Ekkor átrendezés után [Renderelés ... (2-k)a^2 = k], ahol, lévén hogy "k" pozitív kell hogy legyen (ami triviálisan belátható), "k" az adott egyenesen csak 1 lehet, ami valóban négyzetszám.

Ezzel beláttuk az állítást az a=b egyenesre vonatkozóan.
Kérdés, hogy hogyan tovább.
G.Á
 
Hozzászólások: 1087
Csatlakozott: 2016.12.25. 15:27
Has thanked: 57 times
Been thanked: 294 times

Re: A 6. feladat

HozzászólásSzerző: G.Á » 2018.07.23. 00:20

A megoldáshoz érdemes a következőből kiindulni:
Tételezzük fel, hogy létezik valamilyen rögzített egész k esetén olyan a=x és b=y (y>x vagy fordítva), hogy a feladatban szereplő egyenlőség teljesül.

Az egyenlet egy másodrendű algebrai kifejezés:
[Renderelés ... x^2 + y^2 -k xy -k =0].

A feltételezésünk azt jelenti, hogy a paraméter-síkon az [Renderelés ... (x,y_1)] pont az egyenlet gyöke.
Azonnal kereshetünk másik gyököt is, amely (és ez fontos) azonos egész k esetén szintén megoldás.

Rögzítsük x-et, ekkor a másik gyök [Renderelés ... (x,y_2)], megkereshető, mivel [Renderelés ... y_2]-re sima másodfokú egyenletet kapunk.

A Viéta-formulák alkalmazásával látható, hogy:
[math]
és
[math]

Most csak az első esetre hivatkozunk. Rögtön látható, hogy ha [Renderelés ... (x,y_1)] az egész számok rácsán helyezkedik el, akkor [Renderelés ... (x,kx-y_1)]-re is ez teljesül.
Az x-y felcserélhetőség szimmetriája miatt megoldás kell hogy legyen a:
[Renderelés ... (kx-y_1,x)] pont is.

Ez továbbra is az [Renderelés ... y=x] egyenes felett van, de kissé közelebb az origóhoz.

Ez a procedúra megismételhető, de mivel sohasem vezethet ki a pozitív-pozitív negyedből, ezért aszimptotikusan el kell hogy vezessen az [Renderelés ... x=0] (vagy [Renderelés ... y=0]) határhoz.

Ebből már egyenesen következik, hogy [math], vagyis négyzetszám kell hogy legyen.
Kép
A hozzászólást 1 alkalommal szerkesztették, utoljára G.Á 2018.07.23. 10:18-kor.
G.Á
 
Hozzászólások: 1087
Csatlakozott: 2016.12.25. 15:27
Has thanked: 57 times
Been thanked: 294 times

Re: A 6. feladat

HozzászólásSzerző: G.Á » 2018.07.23. 00:51

A feladat mellesleg az 1988.-as nemzetközi matematikai diákolimpia 6. feladata volt.
Eltérő megoldások találhatóak, ha így kerestek rá, de szerintem ez a legszebb.

Arthur Engel tollából, szabadfordítással:
"...Az ausztrál feladatkitűző bizottság hat tagja közül egyetlen sem akadt, aki meg tudta volna oldani.
A tagok között volt Szekeres Eszter és Szekeres György, maguk is híres problémamegoldók;-és kitűzők.
Végül, mivel számelméleti jellegű a kérdés, elküldték a feladatot Ausztrália négy legelismertebb számelmélészének. Mindannyiuknak hat órát adtak a feladatra.
Egyikük sem tudta ennyi idő alatt megoldani.
Ennek ellenére a bizottság továbbküldte a feladatot a XXIX. IMO zsűrijének, a feladatot dupla csillaggal jelölve meg, amivel a szupernehéz, potenciálisan ki nem írandó feladatokat jelölik.
Hosszú megbeszélés után a zsűri kitűzte a problémát, mint a verseny utolsó feladatát.
Tizenegy diák adott be tökéletes megoldást."

Terence Tao, akkor 13 éves diák számára abban az évben ez volt az egyetlen feladat, amelyet nem tudott helyesen megoldani, és egészen addig (és még jópár évig, bár ez ma már megkérdőjelezhető) a legnehezebb feladatnak számított, amelyet valaha is feladtak az IMO-n.
G.Á
 
Hozzászólások: 1087
Csatlakozott: 2016.12.25. 15:27
Has thanked: 57 times
Been thanked: 294 times

Re: A 6. feladat

HozzászólásSzerző: dgy » 2018.07.23. 16:20

Nem érzem teljesnek a bizonyítást.

Először pár apró megjegyzés:
Viszonylag könnyen belátható, hogy ha a feladatban szereplő "k"-t rögzítjük, az az a-b síkon hiperbolákat jelöl ki.

A görbék csak [Renderelés ... k>2] esetben hiperbolák, [Renderelés ... k=2] esetben két párhuzamos egyenest, [Renderelés ... k<2] esetben ellipsziseket kapunk. Az [Renderelés ... y=x] egyenest valóban csak az ellipszisek metszik, [Renderelés ... k] egész volta miatt csak a [Renderelés ... k=1] eset jöhet szóba.
ezért aszimptotikusan el kell hogy vezessen az x=0 (vagy y=0) határhoz.

Megtévesztően használod az "aszimptotikus" kifejezést. Ez azt jelenti, hogy végtelen sok lépésben közeledik valahova az eljárás. Itt viszont arról van szó, hogy a tartomány korlátos és a lépések véges volta miatt az eljárásnak véges sok lépésben el kell érnie az általad megadott határt. Ez nem ugyanaz, mint az "aszimptotikusan"!
Ez továbbra is az y=x egyenes felett van, de kissé közelebb az origóhoz.

Ez nem magától értetődő, be kell bizonyítani.

A lényeges kifogás most következik, a bizonyítás döntő lépésével kapcsolatban:
Ez a procedúra megismételhető, de mivel sohasem vezethet ki a pozitív-pozitív negyedből...

Miért is nem?

A feladat kitűzésekor feltettük, hogy [Renderelés ... a] és [Renderelés ... b] pozitív egészek. Ebből azonban nem következik, hogy a rájuk vonatkozó egyenletnek nem lehet nulla vagy negatív gyöke! (Mint ahogy az eljárásodban meg is jelenik mindkét változó nulla értéke.) Lehet, hogy a gyökök iterációs eljárása kivezet az előfeltételben megadott tartományból - ekkor az így felbukkanó gyököket egyszerűen nem fogadjuk el, nem tekintjük a probléma megoldásának (miközben az egyenletnek továbbra is megoldásai).

A gyökök pozitivitására akkor lehet hivatkozni, ha az előfeltevéstől független módon, magából az egyenletből és az iterációs konstrukcióból bebizonyítjuk, hogy az eljárás nem vezet ki a pozitív síknegyedből. Ekkor - a kvantumelméleti léptető operátoros számoláshoz hasonlóan - azzal lehet feloldani az ellentmondást, hogy az iterációs eljárás valahol véget ér.

De még így sem stimmel a dolog - az iteráció ugyanis nem ér véget a nullánál: a (0; 3) ponttól tovább vezet a
(-3; 0) ponthoz (ami valóban megoldás!), és tovább a negatív egészek felé. Így nem áll az az érv, hogy az eljárásnak meg kell állnia, tehát a nullához kell jutnia.

Az állítás bizonyára igaz, de finomabb érvelés kell a bebizonyításához.

dgy
Avatar
dgy
 
Hozzászólások: 1737
Csatlakozott: 2014.03.12. 21:40
Tartózkodási hely: Budapest
Has thanked: 111 times
Been thanked: 832 times

Re: A 6. feladat

HozzászólásSzerző: G.Á » 2018.07.24. 00:48

Köszönöm a megjegyzéseket, igazad van.
Megpróbálom majd pontosan leírni, de egyelőre csak az egyik (mellékes) dologgal kapcsolatban válaszolok.
Ez továbbra is az y=x egyenes felett van, de kissé közelebb az origóhoz.

Ez nem magától értetődő, be kell bizonyítani.


A Viéte-formula alapján:
[Renderelés ... y_2 = (x^2-k)/y_1 < (y^2_1 -k)/y_1= y_1 - \dfrac{k}{y_1} < y_1]
ahol felhasználtuk, hogy az y=x átló feletti ágról indulunk, illetve hogy [Renderelés ... k,y_1] nemnegatívok.
Szintén teljesül, hogy [Renderelés ... y_2 < x], vagyis továbbra is az átló felett maradunk.
[Renderelés ... y_2 < (x^2 -k)/x= x - \dfrac{k}{x} < x]
Ezenkívül természetesen fennáll az itt felhasznált [Renderelés ... x<y_1]
G.Á
 
Hozzászólások: 1087
Csatlakozott: 2016.12.25. 15:27
Has thanked: 57 times
Been thanked: 294 times

Re: A 6. feladat

HozzászólásSzerző: =^.^= » 2018.07.24. 00:55

[Renderelés ... y_2 \geq 0] esetén már működjön az iteráció, az pedig például abból jön, hogy a (-1,1) pont a hiperbola tartományán kívül van minden k-ra.

Megpróbálom majd pontosan leírni

Esetleg a forrásodat is megadhatnád?
Avatar
=^.^=
 
Hozzászólások: 144
Csatlakozott: 2017.04.17. 22:51
Has thanked: 13 times
Been thanked: 10 times
Név: Maci

Re: A 6. feladat

HozzászólásSzerző: G.Á » 2018.07.24. 01:15

G.Á
 
Hozzászólások: 1087
Csatlakozott: 2016.12.25. 15:27
Has thanked: 57 times
Been thanked: 294 times


Vissza: Rejtvények, feladványok

Ki van itt

Jelenlévő fórumozók: nincs regisztrált felhasználó valamint 0 vendég