50, kék és piros sapkájú törpe egyenként bemegy egy szobába, és úgy kell sorba rendeződniük, hogy a sor egyik oldalán a kéksapkájúak, a másik oldalán meg a pirossapkájúak állnak. Hogyan oldják meg a feladatot, mikor semmi kommunikáció (szóbeli, mutogatás, stb.) nem lehet közöttük, és egyik szobába belépő törpe sem tudja, hogy milyen színű sapka van a saját fején?
Az elso torpe jobbra all, a masodik balra. A harmadik torpe bemegy, ha azt latja hogy az elso ket torpe sapkaja egyforma tehat egy oldalon kellene hogy alljanak akkor nem all be sehova, hezital, ezzel jelezven az elso kettonek, hogy alljanak egy, mondjuk a jobb oldalra. Ezutan beall elsokent a bal oldalra. Amikor a 4. bejon es latja hogy a bal oldali 3.-nak is olyan a sapkaja mint az elso kettonek, akkor nem all be sehova, jelezven a 3.-nak, hogy rossz oldalon all, majd helycsere utan beall balra. Igy a bejovo torpek reakcioja alapjan az elozoleg belepett bal oldali mindig tudja, ha rossz oldalon all es at tud menni jobbra. Igy a vegen egyik oldalon kekek, a masikon pirosak lesznek.
sajnos nem jo a megoldas, mert mindenfele hezitalas, jelzes, reakcio ki van zarva…
Oltári jó feladat, szerintem még nem hallottam korábban. Jó trükkös a megoldása is, szerintem tipikusan a vagy-beugrik-vagy-nem. De inkább nem írom még le, ezzel motiválva a többieket ;]
Ha trükkös akkor tükrös (mármint a szoba)
akkor marad a tukor… :))
nincs se tükör, se trükk
Na jó, igazad van, csak teljes indukció van benne, az meg nem is trükk, minden gimnazistának ismernie kell ;]
se teljes se reszleges indukcio nincs benne
A megoldás:
Bemegy az első törpe, megáll.
Bemegy a második, melléáll.
Bemegy a harmadik, ha két egyforma sapkájút lát, melléjük, ha különbözőt, akkor közéjük áll.
Bemegy a negyedik, ha csak egyszínűeket lát, melléjük, ha különbözőket, közéjük áll, és így tovább…
Pontosan, viszont ez a módszer a teljes indukció módszerén alapul: az első törpe egy helyes színsorrendű sort kezd meg, és minden további, a szobába lépő törpére igaz, hogy az N hosszú helyes színsorrendű sorból N+1 hosszú helyes színsorrendű sort csinál.