Probleme de logică, ghicitori și teste IQ — o arhivă cu sute de enigme rezolvate, comentate de cititori.
#42 Aruncari cu bile - problema de interviu
· dumitru
Esti intr-o cladire de 100 de etaje si ai la dispozitie doua bile identice. Se stie despre bile ca daca le arunci de la o inaltime mai mica de X etaje nu se sparg, iar de la inaltime mai mare se sparg. Se cere sa se gaseasca cel mai mare etaj de la care se poate arunca o bila fara sa se sparga. De cate aruncari este nevoie ?
Propusa de Bogdan S.
(intalnita si in cartea "Cracking the coding interview", usor modificata)
Fie x estajul pe care il cautam.. atunci numarul de aruncari ar fi:
(x div 3)+3 daca x<100 sau
33 daca e 100.
Sandu 18 februarie 2023
Fie x estajul pe care il cautam.. atunci numarul de aruncari ar fi:
(x div 3)+2 daca x<100 sau
33 daca e 100.
Paul 18 februarie 2023
Se arunca de la etajele 10,20,30...100 pana se sparge prima bila.
Presupunem ca s-a spart la 70.
Apoi se arunca bila 2 de la 61,62,63...69 pana se sparge sau nu.
In cel mai defavorabil caz se fac 100/10+9 =19 pasi
vadim 18 februarie 2023
19 maximum
Lelu_Vs 19 februarie 2023
Etajul X-1. Nr de incercari : X:2. Parerea mea...
ady 20 februarie 2023
maxim 14 pasi , incepem sa aruncam intii 14 etaje , daca se strica arumcam de la 1 pina la 13 si vedem exact unde s-a stricat , daca nu se strica , aruncam la 14+13, ca sa nu creasca numarul de pasi in caz ca se sparge, dupa care aruncam la 14+13+12 si asa mai departe
jony 20 februarie 2023
2. atat cate bile sunt.
Lelu_Vs 21 februarie 2023
In problema nu se specifica ce se intampla la etajul X. Se sparg sau nu bilele ? Asta ar completa enuntul.
Dan D 27 februarie 2023
cel mai mare etaj de la care se poate arunca o bila fara sa se sparga
este X-1
Este nevoie de X+1 incercari, pornind de la etajul 1 .... pana la X+1,pentru a se determina primul etaj la care se va sparge bila 100%.
Aruncarea de la etajul X nu certifica ca o bila s-ar sparge(probabil de aceea avem 2 bile).
Numarul maxim de aruncari presupun ca este X+2.
Marius 28 februarie 2023
Aruncam prima bila de la etajele pare ( 2,4,6,8....) . In momentul in care se sparge prima bila (etajul x), stim ca etajul cel mai mare de la care poate fi aruncata o bila este fie x-1 fie x-2. Aruncam a doua bila de la etajul x-1. Daca nu se sparge raspunsul este x-1, daca se sparge raspunsul este x-2.
Ex: prima bila se sparge la etajul 54. O aruncam pe a doua de la etajul 53. Daca nu se sparge 53 este cel mai mare etaj, daca se sparge 52 este cel mai mare etaj pentru ca am aruncat deja de la 52 prima bila.(48,50,52,54)
eu 3 martie 2023
14
Catalin Manea 7 martie 2023
Urci cite un etaj si arunci una din bile pina la etajul la care se sparge. Rezulta ca etajul limita este cel cu numarul mai mic cu 1 decit cel la care se sparge bila. Cita vreme bila nu se sparge, te poti folosi in continuare de ea pina se sparge si ai in permanenta a doua bila intacta.
Alex 7 martie 2023
Am stat si m-am tot gandit mai putin de maxim 18 aruncari nu am gasit o solutie:
Iei prima bila si o arunci de la etajul 10, apoi 20, 30, 40, 50, 60, 70, 80 , 90.
Daca cumva crapa iei a doua bila si incepi de la etajul ultimei aruncari (daca a crapat cand ai aruncat-o de la 80, cu a doua bila incepi de la et 71) si arunci din ce in ce mai sus pana cand crapa si a doua bila.
Daca cu a crapat pana la 90, incepi si o arunci din etaj in etaj pana cand gasesti etajul de la care crapa.
Orice s-ar intampla gasesti etajul in maxim 18 aruncari (in cel mai rau caz era etajul 99)
Nu am luat in calcul etajul 100 pentru ca mai sus de etajul respectiv nu poti ajunge ca sa arunci bila, deci l-am scos din start
Ionut 9 martie 2023
50 aruncari
Gabriel 13 martie 2023
Si de la ultimul etaj, atata timp cat NU le arunc pe langa cladire ci pe podeaua ultimului etaj. Nu pare sa fie specificat UNDE sa arunci bilele, asa ca se poate dintr-o singura aruncare.
Gabriela Vasile 16 martie 2023
Am voie să leg bila de o parașută?
Daniel 18 martie 2023
Etajul este x si este nevoie de x/2+1 incercari.
alam 19 martie 2023
50
kinder 20 martie 2023
etajul este clar 100(nu se specifica faptul ca bila trebuie sa atinga solul). numarul de incercari cred ca e divindeEtImpera(inaltimeaEtajului100);
Lelu_Vs 25 martie 2023
Eu astept si raspunsul "Oficial"
Nicolas 27 martie 2023
Incepand de la primele etaje vor fi (100/4)+1 = 26 de aruncari, maxim.
De ce 4? Pentru ca prima data se arunca de la et. 4.
Daca s-ar sparge bila este logic sa arunci de la et 2 iar prin eliminare (se spage sau nu) afli etajul limita.
alex 30 martie 2023
7 bile. Mereu arunci de la jumatatea intervalului. La 100 arunci de la 50, daca s-a spart arunci de la 25 si intervalul tau este (0, 50), daca nu s-a spart arunci de la 75 si intervalul este ( 50,100) . Continui asta pana ramai cu intervalul de lungime 1.
Nicolas 6 aprilie 2023
Cu totii uitati ca aveti doar 2 bile ? Odata sparte nu mai ai cu ce arunca !
Dragoș 7 aprilie 2023
Dacă bila se sparge la etajul 1 - încercarea a luat sfârșit !! ai nevoie doar de una!( !!!!!!!E OBLIGATORIU să începi de la ETAJUL 1 !!!!!!!)
Dacă nu, continui etaj cu etaj...până la 100 ...deci va fi un nr. de încercări să spunem y ={1, 100} ...dacă nu am uitat cumva semnul pentru intervale. :)
Petrica Radu 10 aprilie 2023
Raspuns corect : 18
Impartim cele 100 de etaje in n intervale ( n= 2,4,5,10,20,50)
Luam exact cazul final , celelalte sunt identice ca logica .
n=10
1. Numarum maxim de incercari pentru bila 1 este 9 ( n-1) , adica se va sparge la etajul 90.
2. Numarul maxim de incercari pentru bila 2 este 9 ( 100/n-1)
Deci , numarul maxim de incercari pentru cele 2 bile este n-1+ 100/n-1=9+9=18 .
Se face calculul pentru celelalte valori ale lui n si se vor obtine valori mai mari .
ex. n=5 4+19=23 .
Radu Alin 21 mai 2023
Daca ai doar doua bile banuiesc ca raspunsul la intrebarea de cate ori poti sa arunci e evident 2 ori. Prima aruncare nu poti sa o faci de la un etaj mai mare de 2 pentru ca mai ai doar o bila, iar in cazul in care de la etajul 2 aceasta se sparge ai varianta sa o arunci de la etajul 1 si sa nu se sparga. Daca arunci de la 3 si se sparge si ai vrea sa arunci a doua bila de la 2 risti sa o spargi si pe aceasta.
Raspunsul meu este de la etajul 1 sigur nu o sa se sparga si nu mai ai nevoie de a doua bila.
Radu Alin 21 mai 2023
In cazul in care ai avea la indemana cate bile vrei se pune problema astfel: prima bila tot timpul o arunci de la etajul 50 si ai doua optiuni:
I bila se sparge si atunci incerci la etajul 25 (a doua bila)
II prima bila nu se sparge si urci la etajul 75 si problema continua tot asa: in cazul in care bila se sparge mergi la jumatate de la 25 ori la 13 ori la 38 iar in cazul in care dupa 50 nu se sparge si la 75 incerci ori 63 ori 88 si tot asa.
Daca esti un pic de informatician (desi nu ma prea pricep) problema se scrie astfel:
fie I si j apartine interv [1; 100] si I si j apartine lui N (nr naturale nenule)
fie j un nr random (necunoscut)
atunci for I= 50
daca I=j atunci j=50 daca nu
daca I>j atunci I :=I+I/2Daca nu
atunci I:=I-I/2 si tot asa pana I=J
Alex 8 iunie 2023
..si iarasi logic: o singura aruncare! ...multi se intreaba: ''cum asa?'' ..poi, si in text scrie: ''se stie ca daca se arunca de la X...'' mai mare sau mai mica nu conteaza! Odata ce stii de la ce etaj se sparge mai ai nevoie doar sa o arunci! :)
Ionut 2 iulie 2023
Cel mai mare etaj de la care se poate arunca o bila fara sa se sparga este x-1 si nu este nevoie de nicio incercare deoarece stim ca bilele nu se vor sparge (din enunt)
Catalin 8 iulie 2023
Radu Alin are dreptate. Acelasi lucru ma apucasem sa scriu, apoi am vazut si raspunsul lui. Este nevoie de maxim 7 aruncari. Imparti pe 100 la 2, pana ajungi la 1. De cate ori il imparti, reprezinta nr de aruncari necesare, iar 1, este nr etajului cand aplici formula.
mircea 23 august 2023
6 incercari. arunci de la etajul 50 daca se sparge sau nu iti raman 49 de etaje dupa arunci de la etajul 25 daca se sparge sau nu raman 24 de etaje acuma arunci de la etajul 12 daca nu se sparge aici atunci iti raman 11 etaje acuma arunci de la etajul 6 orice ar fi raman 5 etaje arunci acuma de la etajul 3 si vezi care e 2 raman si mai arunci odata.in cazut in care la 12 se spargea atunci ramaneau 13 auncai de la 7 raman 6 etaje arunci de la 3 raman inca 1 aruncare
Lelu_Vs 30 ianuarie 2024
Presupunem ca la experimentul facut de tine se sparge prima bila la et. 50. Arunci de la etajul 25. Se sparge si bila ramasa. In situatia asta care este etajul de la care incep sa se sparga bilele ??? 4 ? .. 8? .... Sau 23? .... Conform carui calcul ? Teoria ta se aplica pt aflarea numarului de bile (care se sparg) necesare identificarii etajului X.
magicul 25 septembrie 2023
Dacă de la etajul x se sparge bila, înseamnă că e clar:
mai cobori un etaj și poți arunca bila fără ca să se spargă.
Răspuns: o singură încercare.
Sorin 8 decembrie 2023
Intrebarea nu cred ca e formulata cum trebuie. Presupun ca autorul incearca sa vada care e numarul minim de incercari absolut necesare (deci pentru cea mai defavorabila pozitie). Din 10 in 10 merge, dar are o hiba: cu cit te duci spre un etaj mai inalt, cu atit numarul de incercari creste (se tot aduna etaje, dar intre ele numarul cel mai defavorabil de incercari nu scade. Ca sa evitam asta, trebuie sa alegem un prim etaj si o procedura in asa fel incit numarul maxim de incercari sa ramina constant. Pentru fiecare noua incercare cu prima bila, se aduna o unitate, deci trebuie scazuta o unitate din incercarile cu cea de a doua bila cind se sparge prima. Daca incepem cu n etaje, a doua oara incercam cu n-1, samd. pina la 100, cind trebuie sa mai avem doar 1. Deci 1+2+3+... +n=100, deci [n(n+1)]/2=100.. rezolvind ecuatia se obtin 13. 65 etaje (dar nu se poate), deci se rotunjeste la 14. prima oara trebuie incercat cu etajul 14. Daca se sparge prima bila, vor fi cel mult 13 incercari cu a doua (in total 14). Daca nu se sparge, se continua cu etajul 14+13=27 Daca se sparge, deja sunt doua incercari, dar mai sunt necesare cel mult 12 ca sa se determine etajul, care inseamna iar cel mult 14. Daca nu se sparge, se continua cu etajul 14+13+12=39 samd.
Problema se poate generaliza pentru m etaje: numarul minim de incercari necesare pentru cea mai defavorabila pozitie este partea intreaga plus 1 a solutiei pozitive a ecuatiei: n^2 + n -2m = 0
Eistein 6 ianuarie 2024
Aruncam de la 50 si 51(2 aruncari),daca se sparge la 50 si 51 ,aruncam de la 25 si 26 (2 aruncari),daca se sparg la ambele aruncam de la 12 si 13 (2 aruncari),daca se sparg,6 si 7 (2 aruncari),daca se sparg 3 (o aruncare) avem etaju 2, deci 9 aruncari 10 maxim
Lelu_Vs 30 ianuarie 2024
Einstein ... daca se sparg la 50 si 51, dupa aia nu mai ai cu ce arunca. In enunt nu se specifica un numar infinit de bile.
Bush 11 februarie 2024
7 aruncari in caz ca nu nimeresti din primele 6 (prima de la 100/2=50; a doua de la 25 sau 75 a treia de la 13, 38, 63 sau 88 si asa mai departe)
Bush 11 februarie 2024
In caz ca exprimarea a fost ambigua: aruncam bila de la etajul 50 astfel eliminam din start 50 de etaje apoi de la jumatatea distantei pana la baza sau varful cladirii(25 sau 75in functie de caz) eliminand inca 25 de etaje, apoi din nou la jumatatea distantei si tot asa... In cel mai rau caz se efectueaza 6 aruncari
(Ex: et 50 bila se sparge,
et 25 bila nu se sparge,
et 38 bila nu se sparge,
et 44 bila se sparge,
et 41 bila nu se sparge,
et 43 bila se sparge asa ca este logic ca raspunsul este 42)
marius chivu 11 februarie 2024
RASPUNS 7 ARUNCARI
Oturan 4 martie 2024
o iei de la etajul 1 si arunci cu o b ila paana se sparge
ex etaju 1 nu se sparge
etaju 2 nu se sparge
etaju 3 se sparge
rezulta etaju max este etajul 2
Gigi Laurian 3 aprilie 2024
14 aruncari.
Prima aruncare a primei bile o fac de la etajul 14. Daca se sparge, arunc a doua bila din etaj in etaj. Daca etajul la care se sparge este 13, am nevoie de 1+13=14 aruncari.
Daca prima bila nu s-a spart la etajul 14, o arunc de la etajul 14+13=27. Daca se sparge, arunc a doua bila din etaj in etaj. Daca etajul la care se sparge este 26, am nevoie de 2+12=14 aruncari.
Daca prima bila nu s-a spart la etajul 27, o arunc de la etajul 27+12=39. Daca se sparge, arunc a doua bila din etaj in etaj. Daca etajul la care se sparge este 38, am nevoie de 3+11=14 aruncari.
Si asa mai departe, pana la etajul 14+13+12+11+10+9+8+7+6+5+4=99.
Ca generalizare, pentru o cladire cu N etaje, nr de aruncari de care ai nevoie este dat de cel mai mic numar natural care satisface inecuatia:
x(x+1)/2>=N.
eugenia 22 aprilie 2024
haha de 2 aruncari e nevoe daca avem doar 2 bile?)))))
Liviu 11 ianuarie 2026
Maximum 18 aruncari
Liviu 11 ianuarie 2026
Pasul optim dupa care se fac incercarile (din cat in cat) este radical indice 2 din numarul de etaje. radical indice 2 din 100 este 10.
Esti intr-o cladire de 100 de etaje si ai la dispozitie doua bile identice. Se stie despre bile ca daca le arunci de la o inaltime mai mica de X etaje nu se sparg, iar de la inaltime mai mare se sparg. Se cere sa se gaseasca cel mai mare etaj de la care se poate arunca o bila fara sa se sparga. De cate aruncari este nevoie ?
Propusa de Bogdan S.
(intalnita si in cartea "Cracking the coding interview", usor modificata)