  ̌      ̌   
P 46 (2018/2019) 2 23
Problem dveh jajc
J S
Problem dveh jajc je zanimiv miselni problem,
ki po urbani legendi slovi kot eno izmed vprašanj
iz intervjuja za službo pri velikih računalniških
podjetjih, kot sta npr. Microsoft ali Google. To
vprašanje se na intervjujih najverjetneje ne poja-
vlja več, saj je zaradi svoje rešitve pritegnilo pre-
več pozornosti in s spraševanjem ne bi dosegli te-
ga, čemur je bilo prvotno namenjeno. Oglejmo si
ta problem pobliže tudi mi.
Imamo stavbo s 100 nadstropji in dve jajci. Jajci
sta enaki. Če ju spustimo iz nadstropja h ali kate-
regakoli nižjega nadstropja, se jajci ne razbijeta, če
pa ju spustimo iz nadstropja h+ 1 ali višjega, pa se
razbijeta. Z najmanj koliko spusti jajc lahko z goto-
vostjo najdemo nadstropje h?
...
↓
SLIKA 1.
Ilustracija problema dveh jajc.
Ilustracija problema je prikazana na sliki 1. Možne
vrednosti za h so cela števila od 0 do 100. Vrednost
0 pomeni, da se jajce razbije že pri spustu iz prvega
nadstropja, vrednost 100 pa, da tudi pri spustu iz
stotega nadstropja še vedno ne bomo imeli izgovora
za omleto.
Velikokrat pri reševanju problemov pomaga, če re-
šimo enostavnejšo različico problema. V našem pri-
meru poenostavimo problem dveh jajc v problem
enega jajca: zopet moramo najti tisto kritično nad-
stropje, pri katerem se jajce ravno še ne razbije.
Najenostavneje je, da testiramo nadstropja po vr-
sti: jajce spustimo iz prvega nadstropja; če se ne
razbije, ga spustimo iz drugega in tako nadaljujemo,
dokler se jajce ne razbije. Tako vemo, da je ravno
nadstropje pod slednjim tisto, ki ga iščemo.
Toda, ali je to najboljši postopek? V najslabšem
primeru bomo naleteli na zelo trdo jajce in bomo
potrebovali kar 100 korakov, da lahko z gotovostjo
trdimo, da se jajce nikoli ne razbije.
Poskusimo utemeljiti, da je predstavljeni posto-
pek res najboljši. Ker imamo na voljo samo eno jajce,
je našega poskušanja konec, čim se razbije. Če se
naš postopek iskanja nadstropja h začne tako, da
jajce spustimo iz drugega ali višjega nadstropja in
se jajce razbije, ne moremo več ugotoviti, na kate-
rem izmed nižjih nadstropij bi se jajce prvič raz-
bilo. Sledi torej, da moramo spuščanje začeti v pr-
vem nadstropju. Ko smo zagotovili, da je prvo nad-
stropje varno, pa imamo zopet enak problem, le da
nam preostane še 99 nadstropij. Z enakim argumen-
tom se prepričamo, da moramo nujno testirati drugo
nadstropje in tako do vrha.
Problem enega jajca smo v celoti rešili: odgovor
je 100, v najslabšem primeru moramo preveriti vsa
nadstropja. To je bila ena skrajnost, druga pa je, da
imamo na voljo neomejeno število jajc. V tem pri-
  ̌      ̌   
P 46 (2018/2019) 224
meru je najboljša rešitev klasična in znana: posku-
simo najprej vreči jajce iz petdesetega nadstropja; če
se razbije, vemo, da je iskano nadstropje med prvimi
petdesetimi, če pa ne, pa med zgornjimi petdesetimi.
Preostanek nadstropij zopet razpolovimo, izberemo
ugodnejšo polovico in ponavljamo. Razpolavljanje
nadaljujemo, dokler z gotovostjo ne poznamo h. Ta
postopek imenujemo dvojiško iskanje ali bisekcija.
Koliko spustov bomo potrebovali v najslabšem
primeru? Oglejmo si primer za h = 49. Zaporedje
testiranj bi bilo naslednje:
50,25,37,43,46,48,49.
Ko se jajce tudi v 49. nadstropju ne bi razbilo, bi
vedeli, da je to iskano nadstropje. Izkaže se, da je
sedem testiranj tudi največ, kar jih lahko potrebu-
jemo pri takem postopku. Če se odločamo med n
možnostmi in število vsakič razpolovimo, nas torej
zanima, kolikokrat moramo n možnosti razpoloviti,
da bomo imeli manj kot eno preostalo možnost. Dru-
gače povedano, iščemo najmanjši k ∈ N, da velja
n
2k
≤ 1.
Če enačbo preuredimo in logaritmiramo, dobimo
n ≤ 2k,
log2n ≤ k.
Najmanjši naravni k, da zgornja neenačba velja, je
⌈log2n⌉. Oznaka ⌈x⌉ označuje zaokroževanje nav-
zgor.
V našem primeru imamo 101 možnost in potrebu-
jemo največ
⌈log2(7)⌉ = ⌈6,6582 . . .⌉ = 7
korakov.
Vprašajmo se še, koliko jajc potrebujemo v naj-
slabšem primeru. Odgovor je podoben kot zgoraj:
če se nam jajce vsakič razbije, se premaknemo nižje
in vsakič potrebujemo novo jajce. Ne potrebujemo
neomejenega števila jajc, temveč le sedem.
Pri reševanju problema dveh jajc smo rešili pro-
blem enega jajca in problem sedmih, osmih, devetih,
. . . jajc. Vemo le, da bo odgovor za problem dveh
jajc nekje med 100 in sedem poskusov.
Kaj pa če imamo več ali manj kot 100 nadstropij?
Slika 2 prikazuje, koliko poskusov potrebujemo za
problem enega ali neomejeno število jajc.
2 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
0
10
20
30
40
50
60
70
80
90
SLIKA 2.
Število potrebnih po-
skusov v najslabšem
primeru za problem
enega in neomejeno
mnogo jajc pri razlǐc-
nem številu nadstro-
pij. Rešitev za pro-
blem dveh jajc leži ne-
kje vmes.
  ̌      ̌   
P 46 (2018/2019) 2 25
Glede problema dveh jajc vemo, da bomo gotovo
potrebovali več ali enako poskusov kot z enim jaj-
cem (drugo jajce lahko namreč ignoriramo in upo-
rabimo enako rešitev kot pri enem jajcu) ter več ali
enako poskusov kot pri neomejenem številu jajc. To
ugibanje je predstavljeno na grafu s pikčasto krivu-
ljo. Rešitev seveda ne bo taka; za 110 nadstropij
seveda potrebujemo kvečjemu več poskusov kot za
100, torej mora biti rešitev naraščajoča funkcija šte-
vila nadstropij. Vijuge ponazarjajo, da nič ne vemo o
redu naraščanja rešitve: ali bo linearen, kot pri enem
jajcu (le morda z manjšim naklonom) ali pa bo loga-
ritemski, kot rešitev za neomejeno jajc, ali pa nekje
vmes?
Lotimo se sedaj problema dveh jajc. Najprej po-
skusimo različico dvojiškega iskanja. Prvo jajce vr-
žemo s 50. nadstropja, podobno kot pri bisekciji. Če
se ne razbije, nadaljujemo s 75. nadstropjem in tako
naprej. Toda če se jajce pri 50. nadstropju razbije,
imamo le še eno jajce, česar ni mogoče narediti bo-
lje kot s 49 poskusi. Ali je to res najbolje, kar lahko
naredimo?
Na tem mestu naj povemo, da je mogoče problem
rešiti precej bolje. Kaj če bi namesto tega, da s pr-
vim jajcem razpolovimo prostor iskanja in ga pri tem
morda žrtvujemo, prostor razdelili drugače? S prvim
jajcem lahko testiramo vsako drugo nadstropje, npr.
soda nadstropja. Ko se pri nekem nadstropju za-
lomi, z drugim jajcem ugotovimo, ali je iskano nad-
stropje trenutno ali spodnje. Kaj pa če namesto po
dve nadstropji, skačemo po tri nadstropja? Potem
bi s prvim jajcem na tri nadstropja natančno ugoto-
vili, kje se nahaja nadstropje h. S preostalim jajcem
nato ugotovimo, katero izmed teh treh nadstropij
je h, tako da zopet poskušamo od spodaj navzgor.
V tem primeru potrebujemo v najslabšem primeru
33 + 2 = 35 poskusov. To je najboljši rezultat do-
slej, a pot naprej že vidimo. Kaj če s prvim jajcem
skačemo po štiri, po pet, po šest nadstropij? Kaj je
najbolje?
Namesto da preizkušamo različne možnosti, izra-
čunajmo optimalno rešitev. Če imamo n nadstropij
in s prvim jajcem skačemo po k, bomo uporabili naj-
več
⌊
n
k
⌋
poskusov s prvim jajcem in največ k− 1 po-
skusov z drugim jajcem. Najslabše možno skupno
število poskusov označimo s P in torej enako
P =
⌊
n
k
⌋
+ k.
Izbrati želimo tak k, da bo P čim manjši. Izraču-
najmo kar za vse možne k, rezultati tega izračuna
so prikazani na sliki 3.
Razberemo lahko, da je optimalno število metov
19, dosežemo jih pri k = 8,9,10,11, 12 in 13. Rezul-
tat je pričakovan, želimo namreč čim manjšo vsoto
dveh števil
⌊
n
k
⌋
in k, pri čemer je njun produkt kon-
SLIKA 3.
Število potrebnih po-
skusov v najslabšem
primeru v odvisnosti
od velikosti skoka po
nadstropjih k.
  ̌      ̌   
P 46 (2018/2019) 226
stanten. To je enako znanemu geometrijskemu pro-
blemu, kjer želimo čim manjši obseg pravokotnika z
dano ploščino a – odgovor je seveda kvadrat s stra-
nico
√
a.
Uporabljeno strategijo imenujemo tudi »strategija
velik korak, majhen korak«. Pogosto jo uporabljamo
pri reševanju problemov (problem diskretnega loga-
ritma).
Toda 19 metov ni najboljša rešitev. Za n nadstro-
pij potrebujemo približno 2
√
n metov, kar sicer iz-
boljša tudi red rešitve, ampak rešitev ni optimalna.
Če s prvim jajcem delamo različno velike korake,
lahko pridemo do boljšega rezultata. To lahko vi-
dimo, če razmislimo, koliko metov potrebujemo za
vse možne vrednosti h. Če bi se jajce razbilo npr. v
devetem nadstropju, bi to odkrili po desetih metih:
najprej bi prvo jajce spustili iz desetega nadstropja,
nato pa bi z preostalim jajcem preizkusili ostalih de-
vet spodnjih nadstropij. Če pa bi bili jajci taki, da bi
se razbili v 99. nadstropju, bi porabili deset metov
s prvim jajcem in devet z drugim jajcem. Pri prvem
primeru smo po enem metu morali rešiti še manjši
problem velikosti devet, pri drugem primeru pa smo
po desetih korakih prav tako morali rešiti problem
velikosti devet. Število poskusov za vsako nadstro-
pje je prikazano na sliki 4.
Glede na število poskusov so nadstropja jasno
razdeljena v skupine po deset. Znotraj vsake sku-
pine je najslabše, če moramo preverjati do devetega
nadstropja znotraj skupine, glede na to, ali se v de-
vetem nadstropju razbije ali ne. Vemo, ali je iskano
nadstropje to ali pa eno višje (ki smo ga že preverili).
Vendar, če gledamo skupine kot celote, opazimo: za
spodnje skupine porabimo manj poskusov, kot za
zgornje. Gotovo bi bilo bolje, če bi v vsaki skupini za
najslabši primer porabili približno enako poskusov.
Učeno rečemo, da uporabimo princip minimiziranja
maksimalnega obžalovanja, kar je znan princip v te-
oriji odločitev in teoriji iger. Pogosto mu rečemo kar
minimaks. Pravi, da se moramo odločiti tako, da bo
naj najslabši primer čim manj slab. Uporabljamo ga
tudi pri pisanju umetnih inteligenc za igranje iger,
tudi v znanem alfa-beta algoritmu, s katerim lahko
napišemo umetno inteligenco za igre tri v vrsto, šah
ali go.
Najdimo rešitev problema dveh jajc, s tem da te-
žimo k temu, da bo najslabši primer čim manjši.
Zmanjšati želimo najslabši primer v zgornji skupini,
SLIKA 4.
Število potrebnih poskusov pri problemu dveh jajc pri strategiji,
ko s prvim jajcem skačemo po deset nadstropij naenkrat.
na ta račun pa se bo povečal tisti v spodnji. Recimo,
da s prvim jajcem začnemo testiranje v nadstropju
ℓ. Če se jajce razbije, moramo preveriti še ℓ−1 nad-
stropij, skupaj smo porabili torej ℓ poskusov. Če se
jajce ne razbije, se s prvim jajcem premaknemo v
višje nadstropje. Toda katero? Premakniti se je smi-
selno v tisto nadstropje, če se jajce razbije, bomo
v najslabšem primeru zopet imeli ℓ poskusov. Ker
smo sedaj en met že porabili, se pomaknemo za ℓ−1
nadstropij navzgor. V najslabšem primeru za testi-
ranje vsakega nadstropja do sedaj zopet porabimo
ℓ korakov. Res, če se pri prvem metu jajce ne raz-
bije, ga vržemo iz nadstropja ℓ+ (ℓ−1). Če se sedaj
razbije, vemo, da je kritično nadstropje h nekje med
ℓ + 1 in 2ℓ − 1. Preizkusiti moramo v najslabšem
  ̌      ̌   
P 46 (2018/2019) 2 27
primeru ℓ − 2 nadstropij, torej imamo skupaj ℓ po-
skusov, enako kot v prvi skupini. Če pa se prvo jajce
tudi v drugem poskusu ne razbije, se premaknemo
še višje. Ker smo sedaj porabili že dva poskusa, se
premaknemo za toliko nadstropij, da bomo v naj-
slabšem primeru zopet potrebovali ℓ poskusov, to-
rej za ℓ − 2 nadstropij. S strategijo nadaljujemo in
se premikamo za ℓ − 3, ℓ − 4, . . . nadstropij, dokler
se ne premaknemo le za eno. Edino preostalo vpra-
šanje je, pri katerem ℓ začeti. Če bi začeli na ℓ = 10
kot prej, ne bi niti prišli do 100. nadstropja. Pa zo-
pet izračunajmo rešitev: zanima nas najmanjši ℓ, da
bomo prišli do vrha stolpnice, torej, da bo veljalo
ℓ+(ℓ−1)+(ℓ−2)+(ℓ−3)+· · ·+3+2+1 ≥ 100.
Vsota na levi strani neenačbe predstavlja vsoto pr-
vih ℓ naravnih števil, za katero poznamo direktno
formulo, sešteje se v ℓ(ℓ+1)2 . Če preklopimo še na
splošno število nadstropij n, dobimo neenačbo
ℓ(ℓ + 1)
2
≥ n.
To je kvadratna neenačba, ki jo enostavno rešimo in
dobimo
ℓ ≥ 1
2
(√
8n+ 1− 1
)
.
Ker je ℓ naravno število, moramo rezultat zaokrožiti
navzgor, v primeru n = 100 dobimo
ℓ =
⌈
1
2
(
√
801− 1)
⌉
=
⌈
28,302− 1
2
⌉
= ⌈13,651⌉ = 14.
V tem primeru so nadstropja, s katerih mečemo prvo
jajce, enaka:
14,27,39,50,60,69,77,84,90,95,99,100.
Ko se pri nekem nadstropju prvo jajce razbije, drugo
jajce mečemo od prejšnjega testiranega nadstropja
navzgor, dokler se ne razbije. Zadnje testirano nad-
stropje v zgornjem zaporedju je 100, kar je zato, ker
ima stolpnica le 100 nadstropij; če bi jih imela več, bi
bilo naslednje nadstropje 102. Bolj enakomerno raz-
porejenost najslabših primerov lahko vidimo tudi na
grafu na sliki 5, ki je podoben tistemu na sliki 4, le
da so skupine bolj enakomerne.
SLIKA 5.
Število potrebnih poskusov pri problemu dveh jajc pri strategiji,
ko s prvim jajcem skačemo po deset nadstropij naenkrat.
Je mogoče le s 13-imi meti? Odgovor je ne. Če bi
ciljali na 13 metov, bi morali prvo jajce spustiti s 13.
nadstropja, sicer bi lahko za spodnja nadstropja po-
rabili več kot 13 metov v najslabšem primeru. Zato
moramo naslednjega spustiti iz 13 + 12 = 25. nad-
stropja in tako naprej, s čimer ne pridemo do vrha
stolpnice. Odgovor na problem dveh jajc je torej, da
potrebujemo 14 metov. Poglejmo si še, koliko metov
potrebujemo za stolpnico z n nadstropji. Slika 6 za-
menja našo krivuljo s pravilno formulo, da je število
metov P enako
P =
⌈
1
2
(√
8n+ 1− 1
)⌉
.
  ̌      ̌   
P 46 (2018/2019) 228
SLIKA 6.
Število potrebnih poskusov v najslab-
šem primeru za problem enega, dveh
in neomejeno mnogo jajc pri razlǐc-
nem številu nadstropij.
Po pričakovanjih leži krivulja za dve jajci med pro-
blemom z enim in neomejenim številom jajc. Vidimo
tudi, da si z dvema jajcema lahko pomagamo precej
bolj kot z enim samim. Problem ima namreč koren-
sko rast z n, kar je precej bolje od linearne.
Smo s tem zaključili nalogo in rešili problem? Ma-
tematično gledano ja, odgovor je 14. Pa vendar, je
mogoče še bolje? Izkaže se, da je mogoče še bolje.
Če uporabimo metanje prvega jajca z nadstropij
13,25,36,46,55,64,72,79,85,90,94,97,99,100
bomo še vedno imeli v najslabšem primeru 14 metov,
v povprečnem pa 10,31, z razliko od povprečja 10,35
pri naši strategiji. Bralcu je prepuščena pot do te
strategije.
Kaj če imamo tri jajca ali pa štiri in 1000 nadstro-
pij? Denimo, da imamo e jajc in n nadstropij, tre-
nutno pa jajce spuščamo iz nadstropja ℓ. Zgodi se
lahko eno izmed dvojega: jajce se razbije in ostane
nam e− 1 jajc in ℓ− 1 spodnjih nadstropij. Če pa se
ne razbije, nam ostane n−ℓ nadstropij in e jajc. Oba
problema sta manjša in ju lahko rešimo rekurzivno.
Sedaj to preizkusimo za vse ℓ in vzamemo tistega, ki
ima najmanjši maksimum obeh opcij, saj iščemo čim
manj slab primer. Implementacija tega problema je
zopet prepuščena v zabavo in izziv bralcu, spodaj
pa je podana tabela pravilnih vrednosti za različne
n in e.
1000 1000 45 19 13 11 11 11 10 10 10
500 500 32 15 11 10 10 9 9 9 9
400 400 28 14 11 10 9 9 9 9 9
300 300 24 13 10 9 9 9 9 9 9
200 200 20 11 9 8 8 8 8 8 8
100 100 14 9 8 7 7 7 7 7 7
50 50 10 7 6 6 6 6 6 6 6
45 45 9 7 6 6 6 6 6 6 6
40 40 9 6 6 6 6 6 6 6 6
35 35 8 6 6 6 6 6 6 6 6
30 30 8 6 5 5 5 5 5 5 5
25 25 7 5 5 5 5 5 5 5 5
20 20 6 5 5 5 5 5 5 5 5
15 15 5 5 4 4 4 4 4 4 4
10 10 4 4 4 4 4 4 4 4 4
9 9 4 4 4 4 4 4 4 4 4
8 8 4 4 4 4 4 4 4 4 4
7 7 4 3 3 3 3 3 3 3 3
6 6 3 3 3 3 3 3 3 3 3
5 5 3 3 3 3 3 3 3 3 3
4 4 3 3 3 3 3 3 3 3 3
3 3 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1
n 1 2 3 4 5 6 7 8 9 10
e
SLIKA 7.
Rezultat problema e jajc za n nadstropij
×××