Fórum: Érdekes matekfeladatok

Nem azt kéne feltenni, hogy P és Q relatív prímek? Amúgy az s₁=1 simán feltehető, hiszen s homogén.

Hmm. Furcsa. Akkor debuggolnom kell a bizonyítást.

Bocs, de valamit nem értek ( hacsak nem számoltam el valamit). Legyen s₁=1, P=4, Q=6. Ekkor

s₂=6  s₄=264  s₆=11520.

Ekkor s_(4,6)=s₂=6 de (s₄,s₆)=24

Még novemberben feladtam egy feladatot, amit senki nem oldott meg. Akkor ígértem két másik feladatot is, de ezeket nem tűztem ki érdeklődés hiányában, meg azért is, mert esetleg valaki bemondja, hogy szabad a gazda, és akkor szenvedhetek a megoldás leírásával. Mindhárom feladat arról a szemináriumról való, amelyre részben én gyűjtöttem a feladatokat.

Mivel most más okból leírtam ezek közül a második feladat megoldását, ezért ezt a feladatot most már nyugodtan feladhatom.

238. Az n-edik Catalan-szám . Ismert, hogy ez egyenlő azon lépcsős utak számával, amelyek a kockás papírra rajzolt n jobbra mutató és n felfele mutató kis nyílból áll (valamilyen sorrendben), és nem megy a végpontokat összekötő átló fölé, vagyis minden prefixében legalább annyi jobbra nyíl van, mint fölfele mutató nyíl.

Ezt tudva lássuk be, hogy bármely n-re

Ez a determináns a Catalan-sorozatból képzett Hankel-determináns, amelynek minden mellékátlójában egyenlő elemek állnak.

Lássuk be azt is, hogy

Ha valaki nem boldogul, akkor a megoldás itt olvasható (angolul).

Az első feladat tehát az (1141) hozzászólásban olvasható, a harmadikat viszont csak ennek a megoldása után szeretném föladni, mert összefügg.

Köszönöm, hogy foglalkoztál vele. Megpróbálom átrágni magam rajta.... :o)) Hozzám most jutott el a feladat.

Ez a kérdés a "Nehezebb matematikai problémák" témában is szerepel, a [296]-os hozzászólásban, de akkor addig gondolkoztam rajta, hogy végül teljesen elfelejtettem. :)

Bármely n hosszú dobássorozatot leírhatunk egy pozitív egészekből álló h₁,h₂,...,h_m sorozatként, ahol h_i az i-edik "egyszínű"-részsorozat hossza (tehát h₁+h₂+...+h_m = n és mn). (Minden ilyen összeg valójában két sorozatot ír le, mivel a "színek" megcserélésével a leírás nem változik.) Nevezzük ezeket a sorozatokat n felbontásainak!

Ebből a nézőpontból a kérdés úgy hangzik, hogy n-nek hány felbontása létezik, és ezek közül hányban szerepel k-nál nemkisebb tag (az eredeti kérdésre a válasz ezek aránya lesz). Ez utóbbit úgy is megkaphatjuk, hogy azokat számoljuk össze, amelyekben csak k-nál kisebb tagok szerepelnek, majd ezt az összesből kivonjuk.

Vezessük be az

függvényt, amely azt adja meg, hogy a-nak hány olyan felbontása van, amely b-nél nemnagyobb pozitív egészekből áll.

(A fenti definíció azt "mondja", hogy f(a,b) értéke 1, hogyha a = 0. Egyébként pedig úgy kapjuk meg, hogy a-ból "lecsípünk" 1-et, 2-t, ... b-t (egészen addig, amíg a el nem fogy), minden esetben megnézzük, hogy a maradéknak hányféle felbontása van, és ezeket összegezzük.

Úgy emlékszem, hogy valamelyik IOI/CEOI válogatóversenyen volt egy feladat, amely valahogy úgy hangzott, hogy "Hányféleképpen lehet felugrálni egy a fokú lépcsőn, ha legfeljebb b fokot tudunk egyszerre átugrani?", és ez volt a megoldás.)

Ezzel kifejezve az eredeti kérdésre a válasz:

Az "érmés" vonatkozásban szemlélve az f(n,n) kifejezést láthatjuk, hogy egyenlő 2^n-1-nel.

Időközben megnéztem a F1-et, de érintőlegesen a feladaton is gondolkodtam.... :o) Nekem nagyon bonyolult, lehet, hogy nincs is erre konkrét képlet?

Mondjuk ez a képlet tuti nem jó. Ha k=1, az azt jelenti, hogy legalább egy hosszú egyformákból álló blokk van, ennek esélye 1, nem pedig n/2^n-1. Ugyanúgy ha k=2, akkor az esély 1-1/2^n-1, nem pedig a képletből adódó (n-2)/2^n-1. Jó kérdés, hogy mi lehet a helyes képlet...

Jaj köszi! :o)) Sajna a matek nem igazán az erősségem, de a feladat érdekel.

Na, csak hogy rendesen meglegyen (még nem gondoltam bele, hogy jó-e a képlet, és eltartott vagy 2 percig, míg rájöttem, mi akar az ott lenni...). Tehát annak esélye, hogy lesz legalább k db. egyforma oldal n dobásból:

ami n=k-ra 1/2^n-1-et ad (legalább ez a része tuti jó :-) ).