Keresés


Toplista

Toplista
  • betöltés...

Magántanár kereső

Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!

Chicken McNuggets -- mi a legnagyobb el nem érhető szám?

3686
Nem házi, csak szórakozásként, amíg nincs itt nagy forgalom:

A McDonaldsban 6, 9 vagy 20 darabos csibefalat dobozokat lehet venni. Mi az a legnagyobb szám, amit NEM lehet elérni úgy, hogy tetszőleges kombinációban vásárlunk valamennyit ezekből a dobozokból?

(Tehát pl. 61 elérhető úgy, hogy veszünk 2×20 + 2×6 + 1×9 dobozt, de mondjuk 25-öt nem tudunk sehogy se elérni.)

Mindenféle megoldás érdekes lehet attól kezdve, hogy papíron próbálgatod, azon át, hogy brute force programot írsz rá, odáig, hogy precíz matematikai bizonyítást adsz, hogy melyik a legnagyobb el nem érhető szám és miért.

Jelenleg 1 felhasználó nézi ezt a kérdést.
31
Középiskola / Fejtörő

Válaszok

5
Huh ez jó kérdés...én így gondolkodtam...

Ha felbontjuk a számokat prímekre , akkor ezeket kapjuk:
20 = 5*22
9=32
6=3*2

Ha felbontjuk prímszámokkal, nem tartalmazhatja az alábbi számokat: 2, 5, 3
Tehát ezzel kellene kezdeni valamit:
Ha felbontjuk, akkor egyik oldal sem tartalmazhatja a kettes, hármas, négyes, ötös, és ezek valamennyi szorzatát.
Szerintem a legjobb módszer, hogy megkeressük a legnagyobb prím számot ami a mostani állás szerint, 22 millió számjegyből áll, és lehet, hogy van nála nagyobb is.
Szerintem ez lehet a megoldás... :)
3

Nem rossz hozzáállás, de most nem ez adja a megoldást. Pl. volt róla szó, hogy a 61-et fel tudjuk írni valahogy. Nézzünk onnan kezdve néhányat:
61 = 2·20 + 9 + 6
62 = 20 + 4·9 + 6
63 = 3·9 + 6·6
64 = 2·20 + 4·6
65 = 20 + 9 + 6·6
66 = 11·6
... nem is kell tovább menni, hisz 67=61+6, 68=62+6, 69=63+6, szóval innen kezdve minden szám előállítható úgy, hogy a 6-tal kisebbhez (ami előállítható) hozzáadunk 6-ot.

Vagyis baromi nagy prímeket nem érdemes nézni...

Szóval tuti 61 alatt van valahol, amit keresünk.
Módosítva: 8 éve
4

Hogyha csak 6-os és 9-es csomag lenne, akkor nyilván minden 3k alakú számot elő tudunk alakítani, kivéve a 3-at.
Hogyha hozzáadunk egy 20-as csomagot(20=3*6+2), akkor ezek szerint minden 20+6a+9b alakú számot elő tudunk állítani, ez leegyszerűsítve: 3(6+2a+3b)+2.
A 6+2a+3b: minden 7-nél nagyobb természetes szám előállítható(a 7 még nem), ezt visszahelyettesítve: 3*7+2=23, eddig ez a legnagyobb szám, amit nem tudunk előállítani; és az összes 3k+2 alakú számot elő lehet állítani, ami nagyobb, mint 23.
Hogyha 2 db 20as csomagot veszünk, akkor 40+6a+9b lesz, ez leegyszerűsítve: 3(13+2a+3b)+1
A 13+2a+3b: minden 14-nél nagyobb természetes szám előállítható, ezt visszahelyettesítve: 3*14+1=43 ez a legnagyobb szám, amit nem tudunk így előállítani, mert a többi összes 3k, 3k+1, és 3k+2 alakú számot elő tudjuk állítani.

13

a legnagyobb elnemérhető szám a végtelen
-48

Szia!

Először is nagyon jó a fejtörő, nagyon tetszik.
Másodszor pedig szeretném megkérdezni, hogy ennek létezhet más levezetése is? Én úgy gondolom, hogy kombinatorika, illetve talán algebra irányába érdemes lenne elmennem. Köszi előre is a válaszod!
4