Fórum: Lejárt határidejű KÖMAL feladatokról

Mennyi a sok?

Saját magamon kívül egyvalakit tudok akinek meglett a gráfos ( na vajon kicsoda? :).

Nem tartom fairnek, hogy 3-an jöttök megtámadni egyszerre. Nem tudom, hogy tisztában vagy vele, de már egy ideje leérettségiztem, így nem vagyok aktív Kömal megoldó. De az akkori N jelűek között többször voltam díjazott, régebben ráadásul 4 N feladat volt, nem 3. A múlt havi többi "A" jelűekhez valószínűleg több idő kell, mint 5 perc, amennyi időm volt.

nincs senki a Fazékban, akinek meglenne? Akkor ez is egy max 2 megoldós példa... (egyről tudok)

A gráfosat tőletek sokan megoldották?

Az tény, hogy nekem és szerintem még sokan másoknak nem kellett hozzá 5 perc se, de nem teljesen fair, hogy csak a könnyű feladatokról írsz. Kíváncsi lennék mi a véleményed a rákövetkező feladatról.

( Amire egyébként szívesen látnék megoldást, mert olyan versenyzővel még nem találkoztam akinek sikerült volna. )

Hacsak az A504 nem,[519]hsz. :DDD

(lejárt) A506-os megoldása: legyen az a pontos p hatványosztója p^k, ekkor a=m*p^k, és a színe legyen m mod p (ez 1,2,^...,p-1 lehet, mert m nem osztható p-vel), az a felírása egyértelmű, így a színezés is. Továbbá i*a színe i*a=(i*m)*p^k miatt (i*m) mod p, hiszen a pontos osztó p^k, ha 0<i<p, de i*m redukált maradékrendszert alkot mod p, ha i befutja az 1,2,^...,p-1 számokat, így a színek páronként különbözőek, ami kellett.

Ilyen könnyű A jelűt még nem láttam. 5 perc alatt megoldottam.

Igen, közben rájöttem én is:)

2a-b-vel és 2a+b-vel.

Pontosan erre gondoltam az előző hozzászólásban csak nem volt konkrét ellenpéldám

Az előjeleket szét kellene talán választani, mert pl. a=b=4 esetén 16+4+4 osztható 3-mal, de 16+4-4 már nem.

Üdv. Az oszthatóságok rendben vannak, szerintem ott a hiba amikor n-et kifejezed c,d-vel, mert ott már nem mindegy, hogy a +- közül melyik valósul meg ténylegesen.

Az biztos, hogy rossz, erre utal az ellenpélda, de a hiba biztos nem itt van, mert (i)-ben a 2(a²ab)=3b² a bal oldal osztható 2-vel, így a jobb is. Mivel 3 páratlan, ezért b² a páros.

Bocsánat, nálam a bnégyzet a 3n+1.

Hm... ez érdekes...

bnégyzet páratlan, tehát c nem egész.

A megoldásomban leírtam, hogy legyen (1) 2n+1="anégyzet" és (2) 3n+1="bnégyzet" ahol a és b pozitív egész számok. Namost mi az "anégyzet"+"bnégyzet"+1 értékét akarjuk meghatározni. Ha az (1) egyenlet háromszorosából kivonjuk a (2) egyenlet 2szeresét, akkor az pont előnyünkre válik, hiszen n mint változó kiesik. Innen pedig már szerintem könnyű a feladat, ezt a kis trükköt kellett volna észrevenni, hiszen ekkor 5n+3 felbomlik 2 egész szám szorzatára. (Bár nem írom már le ide, de még azt az esetet kellett vizsgálni, hogy mi van abban az esetben, ha az egyik tényező 1. Ekkor ugye lehet 5n+3 prím is, de itt is ellentmondásra jutunk, tehát nincsen ilyen lehetőség. Bár még nem javították ki a feladatot, de remélem nem hibáztam el semmit sem.

Mivel osztható egyébként 5n+3, vagy hogy jön ki az, hogy összetett szám? :) Nekem mindenféle drámai fordulat kijött n-re (a 40-gyel oszthatóság biztosan, de mintha fokozódott volna a hangulat...)

Nem olvastam végig, de az (iii)-től kezdve lesz a gondolatmenetben a hiba. Talán túlságosan is "túlbonyolítod" ezt a feladatot (Persze ez csak az én véleményem), létezik ennél sokkal egyszerűbb megoldása is, csak egy kicsit trükközni kell.

Nem tudom, hogy hol rossz, de az biztos, hogy n=40 esetén 2n+1 és 3n+1 is négyzetszám, 5n+3=203 mégsem osztható 3-mal. :(

B.4255.

2n+1 és 3n+1 négyzetszámok, ezért felírhatók a következő alakban:

2n+1=(2a1)²=2(2a²2a)+1 és 3n+1=(3b1)²=3(3b²2b)+1.

(i) n=2a²2a=3b²2b, átrendezés után 2(a²ab)=3b², minden változó pozitív egész, ezért 3|(a²ab).

(ii) 2n=2a²2a+3b²2b=2(a²ab)+3b², minden változó pozitív egész, ezért 2|b².

(iii) Legyen b²/2=c és a²ab=3d, ekkor n=3c+3d=3(c+d).

Legyen 5n+3=p, behelyettesítéssel kapjuk, hogy 5^.3(c+d)+3=p, vagyis 3(5(c+d)+1)=p. A bal oldal osztható 3-mal és minden változó pozitív egész, ezért 3|p, vagyis p összetett.

A frissebb változat: http://www.combinatorics.org/Surveys/ds1/sur.pdf

ezzel már 1140 is kijön. (mert r(5,13)1139).

Pontosan nem ismerjük, az egyetlen ismert nemtrivi klasszikus Ramsey szám hipergráfokra az r₃(4,4)=13. Felső becslésként a feladatra, bár lehet, hogy ismernek jobbat is, ezt kaptam: (r₂ helyett r-et írok a gráfos Ramsey számoknál).

r(5,11)r(4,11)+r(5,10)191+442=633

r(5,12)r(4,12)+r(5,11)238+633=871

r(5,13)r(4,13)+r(5,12)291+871=1162

r₃(4,5)r(r₃(3,5),r₃(4,4))+1=r(5,13)+11162+1=1163

Azaz már 1163-ra is igaz, 11000 helyett. Bár ez a számolás használja a fenti ismert Ramsey számot, és 4 nemtrivi felső becslést a sima Ramsey számokra, lásd például itt

http://www.emis.de/journals/EJC/Surveys/ds1.pdf

Ezért írtam az utolsó mondatom. És nem is az A-ra írtam a hsz-em, inkább a B-re.

Én konkrétan nem láttam olyan ,,versenyzőt'' aki ebben NEM ismerte fel a Ramsey-tételt még jóval azelőtt hogy nekiállt volna ,,józan ésszel''.

Persze ez csak 4-5 fős minta, de ennél nem sokkal többen küldik az A pontversenyt.

És pontosan mennyi r₃(4,5) értéke? Nekem becslésként 10626() jött ki, de az nem biztos, hogy ez a legjobb becslés.