"Medland szigetén csak medvék élnek, jegesmedvék, pandák, mosómedvék, összesen 100-an. Minden lakó vagy igazmondó (mindig igazat mond) vagy hazudós (mindig hazudik).
A sziget összes lakójának feltették az alábbi három kérdést:
Jegesmedve vagy?
Panda vagy?
Mosómedve vagy?
Az első kérdésre 60, a másodikra 40, a harmadikra 30 igen válasz érkezett.
Hány hazudós él a szigeten?"
Az igazmondó medvék számát J, P, M, a hazugokét j, p, m betűkkel jelöltem.
Összlétszám:
J+P+M+j+p+m=100
A kérdésekre adok válaszok számából az derül ki, hogy
J+p+m=60
P+j+m=40
M+j+p=30
E három egyenlet összegéből az első egyenletet kivonva:
Az f(n) nem lehet sorozat, mivel nincs olyan n, amelyre f(n)=2015.
A feladat a pozitív egészeket a pozitív egészekbe képező függvényekről szól. Magyarán olyan függvényekről, amelyek minden pozitív egészhez rendelnek egy pozitív egészt. Minden ilyen függvény felfogható sorozatnak és viszont. Pl. az f(n)=n2 függvény azonos a négyzetszámok sorozatával: (1,4,9,16,25,...). Ez a függvény az n-hez az n2-et rendeli, tehát a sorozat n. eleme az n2.
A legtöbb ilyen f(n) függvény (avagy sorozat) nem veszi fel a 2015 értéket, azaz nincs olyan n, amire f(n)=2015. Teljesen irreleváns a feladat szempontjából, hogy van-e ilyen n vagy sem.
Így az f(f(n))=3n kitétel sorozatok unióit határozza meg.
Nem. Ez a kitétel egy megszorítást ad a függvényre, és végig kell gondolni, hogy a többi megszorítással együtt ez mit jelent. A fenti megszorítás csak annyit mond, hogy ha a sorozatban megnézzük, hogy az n. helyen mi áll (bármilyen n-re), majd megnézzük, hogy az annyiadik helyen mi áll, akkor éppen 3n-et kapunk. Magyarán kétszer alkalmazva a függvényt megkapjuk a 3n függvényt. Az
f(n) := floor(sqrt(3)*n)
függvény nem jó, mert erre f(2)=3 és f(f(2))=f(3)=5, tehát f(f(n))=3n nem teljesül n=2 esetén (minden n-re teljesülnie kell). Ettől persze még apriori előfordulhatna, hogy van olyan f(n) függvény, ami kielégíti az összes feltételt és az általad említett f(2015)=floor(sqrt(3)*2015) feltételt is, de valójában nem fordul elő. Yorg365 a 118-as üzenetben részletesen vázolta annak bizonyítását, hogy egyetlen függvény felel meg a feltételeknek, és meg is adta ezt a függvényt egy egyszerű rekurzióval.
Medland szigetén csak medvék élnek, jegesmedvék, pandák, mosómedvék, összesen 100-an. Minden lakó vagy igazmondó (mindig igazat mond) vagy hazudós (mindig hazudik).
A sziget összes lakójának feltették az alábbi három kérdést:
Jegesmedve vagy?
Panda vagy?
Mosómedve vagy?
Az első kérdésre 60, a másodikra 40, a harmadikra 30 igen válasz érkezett.
Nem igazán értem. Miért jó valamelyik megoldás, vagy miért nem.
A feladat követelményei egyértelműen meghatározzák az összes pozitív egészre f(n) értékét, így f(2015)-öt is. Ha valaki a jó számot adja meg, akkor a megoldás jó. :-)
Az, hogy a követelmények egyértelműen meghatározzák az értékeket (vagy hogy létezik-e egyáltalán megoldás) persze elsőre nem feltétlenül nyilvánvaló, ezért alkalmas versenyfeladatnak.
Az első párat könnyű kiszámolni (f(1)=2, f(2)=3,...). Leírtam n-t és f(n)-t két oszlopba egymás mellé, és néztem, hogy van-e valami minta. Megsejtettem, hogyha n 3-hatvány, akkor f(n)=2n, és f(2n)=3n. Ezt teljes indukcióval könnyű igazolni. Na most mivel ebben az esetben f(2n)-f(n)=3n-2n=2n-n=n, és f(n+1)>f(n), ebből következik, hogy az f függvény n és 2n között mindig csak 1-gyel növekedhet.
Legyen most n<=k<2n (n továbbra is 3-hatvány). Ekkor a fentiek miatt f(k)=2n+(k-n)=n+k.
Ezt behelyettesítve az f(f(k))=3k függvényegyenletbe kapjuk:f(f(k))=f(n+k)=3k. (Ez azt jelenti, hogy az f 2n és 3n között mindig 3-mal növekszik).
2015=2*729+557. Ha most n=729=36, és k=729+557=1286, akkor n<=k<2n, és 2015=n+k, tehát a fentiek szerint f(2015)=3*1286=3858. Készen vagyunk.