Helyes a válasz, de az a) részre is párosítással lehet válaszolni. Ha minden cédulához a komplementerét rendeljük párként, akkor az összes számot tartalmazónak nem lesz párja. Egy cédulának és a párjának mindig 5 végű az összege (azaz pl. a 2-es és a 3-a vagy a 6-os és 9-es kalapokban ugyanannyi cédula lesz). (Ez azért van, mert az összes számjegy összege 45.) Az 5 feliratú kalapban levő cédulák párjai a 0 feliratú kalapba kerülnek, de az az összes számot tartalmazó is itt van, ennek nincs párja, ezért van az 5-ben eggyel több cédula, mint a 0-ban.
az előbb elszállt, baszki :-( akkor most rövidítek
tippem: az 5-ösben eggyel több van, mint a nullásban (104 ill. 103), valamint mindegyikben páros számú, kivéve a nullásban (0 és 5 ld előbb, a többiben 102)
a gondolatmenet lényege, hogy a számok mérnöki intuícióm alapján "eléggé egyenletesen" vannak elosztva, az összes 1023 db. cédulából 10x102 egyenletesen, a 3 kakukktojás meg "valahogy"
hogy hány számjegyű cédulából hány darab van, azt a Pascal-háromszög tízes sora mondja meg, ez a Wikipédiából kopizva 1 10 45 120 210 252 210 120 45 10 (1 - ez nincs) , ránézésre látszik, hogy az 1-et és a 252-t kell alaposabban megnézni
az egy szem tízjegyű cédulán a számok összege 45, tehát az 5-ös kalapba megy
az ötjegyűekből 25x10 egyenletesen elosztva, plusz egy-egy az 5-ös és a 0-s kalapba (szimmetria, mérnöki megérzés :-) )
Van rengeteg cédulánk, egy tollunk, valamint tíz kalapunk, melyeken rendre a 0; 1; 2; 3; 4; 5, 6; 7; 8, 9 számok vannak felírva. Minden cédulára ráírunk valahányat (legalább egyet) a 0, 1; 2; 3; 4; 5; 6; 7; 8; 9 számok közül, hogy bármely két cédula esetén legyen olyan szám, mely az egyiken rajta van, a másikon nincs. E feltételnek eleget téve a lehető legtöbb cédulát készítjük el.
Adjuk össze mindegyik ilyen cédulán a ráírt számokat, figyeljük meg a kapott összeg utolsó számjegyét, és ennek megfelelő jelzésű kalapba dobjuk be a cédulát! Így mindegyik cédula bekerül valamelyik kalapba.
a) A 0 és az 5 feliratú kalapok közül melyikben van több cédula és mennyivel?
b) Melyik kalapokban lesz páros és melyekben páratlan a cédulák száma?
A feladványnak van értelme (egy jó megoldásnak pláne, de még gyakorlati haszna is
Kollégám mesélte, hogy az öccse gyereküléseket gyártó cégnél dolgozik, ütközési tesztek, sebesség-határ, csecsemő-bábuk, ilyesmi. Nyilván előadtam a lenti fejtörőt. Kolléga első reakciója: tök jó, ez hasznos lesz az öcsémnek, lévén hogy két gyereke van.
Ez esetben gratulálok neki az alsó csoportosok számára kreált feladványhoz, mindazonáltal - ha volna egyáltalán értelme -, ajánlanám figyelmébe az előle rejtőzködő, ámde tőle függetlenül is, kétségtelenül létező, magasabb szintű összefüggéseket. De ha így, akkor az más, a problémát megoldottnak tekintheti.:-)
Önmagában, a feladvány logikai ellentmondás, mert 2 lépésben nem lehet eldönteni a kérdést – hacsak nem a következőkkel állna elő a feladvány kiagyalója:
- egy tojást akárhányszor ledobhatunk, de az csak egyszer tud összetörni
- hát persze hogy egyetlen tojást se kell felhasználni, hiszen ha 3 métert számolunk egy emelet magasságának, az még akkor is összetörik, ha szivacsra vagy habra ejtjük…
- de én arra gondoltam, hogy…
- akkor most mondjuk azt, hogy…
Nem. A feladványnak van értelme (egy jó megoldásnak pláne, de még gyakorlati haszna is:-)), de nem abban a formában, ahogyan azt elénk tárták.
Továbbá:
- ha nincs olyan emelet, ahonnan leejtve egy (ugyanazt a) tojást, az ne törne össze
- illetve, ha bármelyik emeletről is ejtünk le egy tojást, azok mindig összetörnek
akkor egyváltozós (amihez 6 lépésre (tojásra) volna szükség, de pl. egy algoritmus esetében, ennek eldöntése a 0. egyben utolsó lépés is volna:-)), és akkor azért nincs értelme a feladványnak.
Én tehát arra az esetre vázoltam fel az egyik lehetséges megoldást leíró (magyarázó) folyamat első oszlopát, amikor:
1. van az az egy/több emelet, ahonnan leejtve egy tojást, az minden egyéb körülménytől függetlenül összetörik
2. van az az egy/több emelet, ahonnan leejtve egy tojást, a tojás nem törik össze
Ugyanakkor szeretnélek arról biztosítani: a fentebb leírtak szerint, 5 lépésből lehet megoldani a problémát; vagyis, megtalálni azt az (földszinttől számolt) 'első' emeletet, ahonnan leejtve egy tojást, az nem törik össze.
A korábban felírt oszlop, gyakorlatilag a megoldás kulcsa - már csak a zárat kell megtalálni.:-)
Nem, nem, dehogy, mondom, csak átfutottam, az értő olvasáshoz még nem volt elég időm. Vagy tényleg funkcionális analfabéta vagyok...
Amúgy kezdem kapisgálni. Különben az volt eddig a bajom, hogy nem értettem, hogy ha az első dobás a 8.-ról indul, akkor miért nem a 16,24,32 a további. Hiszen "szimmetrikusnak" kellene lennie. De most már kezdem sejteni, hogy az első dobásnál, ha nem törik el, akkor a következő szakaszra már csak eggyel kevesebb kell maradjon, "elpazaroltuk" az első dobást, és így tovább...
Most már annyi hozzászólás van, hogy ebből tényleg megértem, ha lesz egy kis időm.
Az első tojást úgy dobjuk, hogy ha eltörik, akkor az elsőtől elindulva az ezt megelőző szintig összesen X dobás legyen, ha nem törik el, akkor pedig a "maradék" épület legyen megoldható X-1 dobásból. Innen kiindulva visszafelé. Egy szintes ház 1 dobás. Minden lépésben az épület a korábbi épületszint dobásainak száma+1-gyel növelhető és az első dobás is erről az emeletről történik.
max emelet - legkevesebb dobás sorrendben:
1 - 1
3 - 2
6 - 3
10 - 4
15 - 5
21 - 6
28 - 7
36 - 8
Tehát első dobás 8. emeletről, ha eltört akkor elsőtől elindulva legrosszabb esetben a 7-en törik el a második tojás (8 dobás összesen), ha pedig az első dobás nem tört el, akkor a maradék 28 emeletnyi épületet tudjuk ugyanígy 2 tojással 7 dobásból megmondani (a részletesség kedvéért 15. emeletről ha eltört akkor 9-től a 14-ig max 7 dobás, ha nem akkor 21-ről dobok ami maradék emeletek 6 dobásból lesznek meg ... stb.)
Van egyrészt egy eljárás, miszerint először honnan dobod le a tojást, majd innen hogyan lépsz tovább, ha eltört; illetve hova, ha nem tört el. Ezt követően megint van egy terv arra, hogy az egyes kimenetek után hogyan lépsz tovább.
A terv elágazó, de előre rögzített, konstans.
Van másrészt a mérési eredmény, a dobások eredménye. Ha eltört a tojás, írjunk 1-t, ha nem tört el, írjunk 0-t.
Ha mindkettő eltört, onnantól írjunk a megmaradó helyekre 0-t.
Így ha n dobásunk van, akkor van egy n számjegyből álló sorozatunk, amiből legfeljebb kettő lehet 1-es, a többi 0-s.
A lehetséges sorozatok száma felső határt ad arra, hogy n dobásból hány kimentet tudunk megkülönböztetni.
Nyolc dobás esetén van 1 olyan sorozat, ami nem tartalmaz egyest, 8 olyan, ami pontosan egy darab egyest, 28 olyan, ami két darab egyest tartalmaz. Ez 37.
Hét dobásra 29 lenne a végeredmény, annyi tehát nem elegendő egy 36 emeletes házhoz.
A nyolc dobás tehát szükséges.
A megfelelő dobási rendszerd megalkotásával pedig igazolható, hogy elégséges is.
OK, jatsszunk itt, a forumon! Te bemondod, hogy i. dobas k. emelet, mi meg bemondjuk, hogy osszetort vagy sem, es mondhatod a kovetkezot. Meglatjuk, menni fog-e max. ket tojas max. 5 dobasbol.
Maximum 5 kísérlet kell hozzá, de akkor már tényleg elmondhatod magadról, hogy tök balszerencsés vagy.:-)
Hogy vegyük komolyan egymást, leírom ide az egyik lehetséges megoldás 'első oszlopát' - bár tegyük hozzá, azért ennél van egy nagyságrendileg elegánsabb (egyszerűbb, viszont kevésbé szemléletes) megoldása is a problémának.:-)
Hany emeletes maximum az a haz, amibol N dobassal el tudod donteni a leirt feltetelekkel, hogy pont hol torne el?
[N=1 es N=2 konnyen atgondolhatoak (1,3)].
Legyen (N-1)-re ez a szam K, es keressuk N-re a maximumot.
Dobd ki az elsot az N. emeletrol. Ha eltorik, a masodik tojassal az also N-1 emelet lentrol kezdve egyszeruen vegigprobalhato a maradek N-1 probalkozasodbol (es mas megoldas nincs is a pontos valaszhoz); ha nem torik el, akkor az N+1 ... N+K emeletek kozott a ket ep tojassal a rekurzio miatt meg tudod mondani, hogy pontosan meddig nem torik (sot, ennel tobbrol biztos nem).
Az biztos, hogy ha az elsot magasabbrol dobod, es torik, akkor az alsok kozul nem tudsz biztosat mondani. Az is, hogy lentebbrol meg nem erdemes kezdeni, ha egyszer N-rol is lehet, es maxot keresunk.
Adodik, hogy N-re 1+...+N a legmagasabb epulet, amire meg tudod mondani. Sot, az algoritmus is adodik: az N, N+(N-1), N+(N-1)+(N-2), ... ,N+...+2, N+...+1 emeletekrol kell kidobni addig a tojast, amig el nem torik, es a ket utolso dobas kozott pont annyi kulonbseg lesz, amennyi dobasod me'g visszamaradt, hiszen igy csinaltuk a sorozatot, alulrol haladva az utolsotol felfele egyesevel kiprobalod a masodik toresig.
Forditva mar csak az a kerdes, hogy mi a legkisebb N, aminek a szumma 1..N-je mar eppen eleri a kivant magassagot.
Igy jobb? Csak elsore nem akartam leloni a konkret megoldast, ravezetes akart lenni amit irtam.
Köszi a válaszokat, párszor elolvastam, még nem teljesen értem, legalábbis nem tudom elég jól vizualizálni, az "n-k" formulák néha még gondot okoznak... :o)
A megoldás azon alapul, hogy egy tojással csak az előző egy lépésenkénti eljárás ad megoldást n emelet esetén legfeljebb n lépésben. A második tojással úgy osztom ketté az n emeletes házat, hogy ledobom a k-adik emeletről. Ha eltörik, a másik tojással az alacsonyabb szinteken k-1 lépésben eldöntöm, hogy mi a megoldás, ha nem, a fölső n-k emeletre megint van két tojásom. Ha k-t úgy választom meg, hogy ennyi emeleten két tojással k-1 lépéssel eredményt kapjak, akkor k lépés kellett az n emelethez. 3 emelet esetén 2 kísérlet kell, ha a másodikról ledobott tojás eltörik, akkor a másikat az elsőről kell ledobni, ha nem akkor a harmadikról. Ha ez a legfelső 3 emelet, és ide úgy jutottál el, hogy az alatta levő emeletről még nem tört el a tojás, akkor még az alatt is lehet 2 emelet, amit a másik tojással próbálhatsz végig két kísérlettel,, ha az első mégis eltört volna. 3 kísérlettel tehát 6 emeletet lehet végigpróbálni. Ez alatt 1+3 emelet lehet a 4 kísérlethez, és így tovább, minden egyes plusz kísérlettel eggyel több plusz emelet adható hozzá.
A kulcs ott van, hogy az elso tojas csak akkor torhet el, ha a masodikkal az utolso "nem torott el" es az eltores helye kozotti minden emeletet kiprobalhatunk (alulrol felfele), hiszen masodikra mar nem kockaztathatsz, ha atlepsz valamit es utana egybol torik, akkor nem tudsz biztos valaszt mondani.
A probalkozasokat meg ugy kell erteni, hogy TE megmondod elore azt a szamot, hogy legfeljebb hanyat fogsz probalkozni, amibol meg tudod mondani az eredmenyt. Azt nem tudod, hogy most eppen eros vagy gyenge tojasokat kaptal, csak azt hogy az egyik szint es alatta nem tornek el, felette barhol eltornek (az elobbi miatt tudsz a 36 lepesbol faragni). A lenyeg, hogy amit vallalsz, azt a legrosszabb esetben is teljesitened kell, nem lehet bizonytalan kimenetel.
Megfogalmazhato ugy is a kerdes, hogy melyik legkisebb szam eseten letezik algoritmus, amelyikre igaz, hogy ennyi lepesszamon belul minden esetben helyes valaszt ad.
Nem tudom, mennyivel sikerult megvilagositani a minmax problemat...
Ez egyebkent azt hiszem mas emeletszammal de idei Zrinyi feladat is volt (talan tobb evfolyamon, 5. osztalyosoknak biztosan).
Egy kísérlet kimenetele jó, ha el tudom dönteni, mit bír ki egy tojás, rossz, ha nem tudom eldönteni, mert további kísérletekre van szükség. Például egy megoldás, ha elkezdem az első emeleten. Ha eltörik, már meg is van a válasz, ha nem, megyek a másodikra. Ezzel az eljárással a legrosszabb esetben 36 kísérletre van szükség, ha olyan kemény tojásaim vannak, hogy csak a legfelső emeletről leejtve törnek el (vagy még akkor sem). Mivel ezt egy tojással is el tudnám játszani, viszont két tojásom van, feltehetően van olyan algoritmus is, amivel ennél kevesebb kísérlet is elég.
kicsit pihent a topik, feldobnám egy kérdéssel. Adott egy régi feladat, szerintem itt is szerepelt, még a megoldását is tudom (valszeg a jót), de nem értem. Le tudná valaki írni a megoldást magyarázattal együtt?
Ez az a feladat :
Van 2 tojásunk és egy 36 emeletes épület. Ha valamelyik emeleten kidobunk egy tojást, akkor az vagy összetörik vagy nem. Állapítsuk meg melyik a legmagasabb emelet, ahol még nem törik össze egy tojás, méghozzá úgy, hogy a lehető legkevesebb próbálkozást kelljen elvégezni a legrosszabb esetben is.
Esetleg egy kis segítséget a feladat átírásához is : "legkevesebb próbálkozást kelljen elvégezni a legrosszabb esetben is" eléggé hülyén hangzik szerintem. Vagy matematikailag helyes, csak nyelvtanilag fura?
:: Megnéztem a Wiki-n a moho-t, de én semmi hasonlóságot nem látok a moho és az itt leírt logika között
a moho algoritmus lenyege, hogy reszfeladatokra osztja az eredeti problemat es ezek kozul azt oldja meg, amelyik a legnagyobb haszonnal jar. a feladat "maradekat" ugyanebben a stilusban oldja meg, amig a feladat "el nem fogy".
ebben a feladatban ez ugy nyilvanult meg, hogy a bemeneti karaktersorbol addig pakolt egy dobozba, ameddig az egyaltalan lehetseges.
egy nem moho algoritmus hamarabb valtana dobozt mint a moho, abban a remenyben, hogy a maradek karaktersor joval kevesebb dobozvaltasbol megoldhato. jelen feladatnal ez nem lehetseges, ezert optimalis itt a moho algoritmus.