Newsgroup: it.hobby.enigmi
Titolo: Non rompete le palle

Che nessuno si offenda: e' veramente il titolo di un problema.
Un laboratorio di ricerche ha creato un nuovo tipo di cristallo
rinforzato e voi siete il collaudatore.
Il vostro lavoro consiste nel prendere palle del nuovo materiale e
buttarle dai vari piani di un grattacielo, determinando sino a che
piano resistono.
Il budget basso ha permesso di fornirvi solo due palle, e dovete
cavarvela con quelle.
Per motivi di efficienza, dovete minimizzare il piu' possibile il
numero di tentativi (se no al laboratorio salta la qualificazione ISO
9000), quindi non va bene partire dal primo, poi passare al secondo,
poi al terzo, eccetera, sino alla rottura. Troppo tempo! Dovete
adottare un criterio che:
1) vi porti sicuramente alla soluzione
2) minimizzi il numero di tentativi massimi necessari
Se i piani del grattacielo sono 100, qual e' questo criterio e in
quanti tentativi massimi vi porta alla soluzione?
Ovviamente siamo in un caso ideale: se il limite di resistenza e' al
piano x, le palle si romperanno sempre da li' in su e resteranno sempre
intatte ai piani inferiori.

 quanti tentativi massimi vi porta alla soluzione?
Beh, io procederei sempre andando a testare "la metà"...
Parto quindi dal 50esimo piano...
Se si spacca, dal 25...
Se resiste, dalla metà fra 25 e 50 (37 o 38 quindi)
ecc ecc ecc
Dico pallate??? :-D
-- 
GTFedelissimo
Membro accolto con lode nella
Federazione Italiana Giovani Artisti 

 ecc ecc ecc
Dimentichi però che ci sono solo 2 palle a disposizione, per cui una 
volta che si è rotta la prima non puoi più procedere con una ricerca 
binaria.
--
[fadeout]


Esattamente.
Infatti, con una tecnica del genere, si avrebbe un valore di 50
tentativi massimi.
Se si spacca al 50, l'unico modo per arrivare sicuramente in fond,
visto che abbiamo una palla sola, e' provare dal primo, poi dal
secondo, poi il terzo, eccetera. Se siamo sfigati si rompe al 49. Piu'
il tentativo iniziale, 50.
Si puo' fare di meglio.

Il 11-09-2006, Il bragozzi scrive:




spoiler
Ovviamente col metodo dicotomico con recupero.
Siccome 2^6=64, allora parto dal 36-mo piano.
a36  a68  a84  a92  a96  a98.. -> esatta.
a36  a68  a84  a92  a96* b94.. -> esatta.
a36  a68  a84  a92* b88  b90.. -> almeno 88 o esatta.
a36  a68  a84  a92* b88*       -> almeno 84.
a36  a68  a84* b76  b80  b82.. -> almeno 80 o esatta.
a36  a68  a84* b76  b80*       -> almeno 76.
a36  a68  a84* b76*            -> almeno 68.
a36  a68* b52  b60  b64  b66.. -> almeno 64 o esatta.
a36  a68* b52  b60  b64*       -> almeno 60.
a36  a68* b52  b60*            -> almeno 52.
a36  a68* b52*                 -> almeno 36.
a36* b20  b28  b32  b34..      -> almeno 32 o esatta.
a36* b20  b28  b32*            -> almeno 28.
a36* b20  b28*                 -> almeno 20.
a36* b20*                      -> che palle di merda!
-- 
Ciao, rez	||  -- GNU/Linux 2.4.25 su Slackware 9.1  ||

 Che nessuno si offenda: e' veramente il titolo di un problema.
spoiler
.
.
.
.
Io proverei i piani di 3 in 3, partendo dal 3°. Detto N il numero di piani e 
P il piano di prova:
getto una palla dal piano P:
- non si rompe: proseguo dal P+3
- si rompe:
getto l'altra dal P-2:
- si rompe => il limite di sicurezza è P-3
- non si rompe => il limite di sicurezza è P-1
Il numero massimo di tentativi è N/3+1.
Stefano 


"Almeno X" non basta.
Devi ottenere sempre uin valore preciso.


 quanti tentativi massimi vi porta alla soluzione?
spoiler
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Supponendo di sapere con certezza che il punto di rottura è compreso 
tra 1 e 100, ho trovato un criterio con cui il numero massimo di lanci 
è 13, ma non so se è l'ottimo.
I piani da cui lancio la prima palla (fino a che non si rompe) sono 
questi in sequenza:
14 - 27 - 39 - 50 - 60 - 69 - 77 - 84 - 90 - 95 - 99
Se la prima palla si rompe al piano n°
14: lancio la seconda dal 1 al 12, per un massimo di 1+12=13
 (se al 12 non si rompe il punto di rottura sarà sicuramente il 13)
27: lancio la seconda dal 15 al 25 per un massimo di 2+11=13
...
...
95: lancio la seconda dal 91 al 93 per un massimo di 10+3=13
99: lancio la seconda dal 96 al 97 per un massimo di 11+2=13
Se la prima palla non si rompe mai, il piano di rottura è ovviamente 
100.
--
[fadeout]

Stefano Gemma wrote:

no, così al massimo fai 35 tentativi, max 33 con la prima e max 2 con la
seconda (nel caso del 98' piano)
col tuio metodo puoi farne solo 19 andando di 8 in 8 fino a di 13 in 13.
dalla tabella, si ha:
di X in X       Ipalla          IIpalla         max
2               50              1               51
3               33              2               35
4               25              3               28
5               20              4               24
6               16              5               21
7               14              6               20
8               12              7               19
9               11              8               19
10              10              9               19
11              9               10              19
12              8               11              19
13              7               12              19
14              7               13              20
ma si può diminuire ulteriormente.
ad esempio vado al 14', 27', 39', 50', 60', 69', 78', 86', 93', 99', e
quindi se si rompe riparto dal piano successivo a quello della prova
precedente, limitando il mumero massimo di tentativi a 14.
non so se si possa diminuire ulteriormente.

rez wrote:

e se si rompe al trentaseiesimo piano, devi fare 65 tentativi

carmine wrote:

ps: se si dovesse rompere al novantottesimo o al centesimo, i tentativi da
fare sarebbero 15

Congratulazioni a Carmine, nonostante il piccolo errore.
Il valore e' 14, ma nel calcolo della sequenza hai sommato due volte il
valore 9:
   .. 60', 69', 78'...
La sequenza corretta e' stata indicata da Fadeout, che pero'  ha
commesso un errore sistematico,
...Se la prima palla si rompe al piano n°
14: lancio la seconda dal 1 al 12, per un massimo di 1+12=13
 (se al 12 non si rompe il punto di rottura sarà sicuramente il 13)
...
In realta', se si e' rotta al 14 e non al 12, al 13 potrebbe rompersi
come non rompersi.

Il bragozzi ha pensato forte :

Non si tratta di un errore, ma bensì di un'ipotesi, tant'è che il post 
iniziava con "Supponendo di sapere con certezza che il punto di rottura 
è compreso tra 1 e 100". Ovviamente se così non fosse occorrerebbe 
aggiungere 1.
--
[fadeout]

 e' veramente il titolo di un problema.
Interessante. Cosa succede se si hanno più di 2 palle e più di 100 piani?
Ad esempio, con 1000 piani con 3 palle?
ciao
marco

 
no no, credo abbia ragione
14 - rotta
poi
1, 2, ..., 12
non rotta. Non puoi fermarti, il piano potrebbe essere 13 o 14, quindi 
devi provare il 13. Totale 14 lanci.
Il numero minimo di lanci per arrivare a k piani dovrebbe essere l'n 
minimo tale che
n(n+1)>=2k
ciao
marco

 provare il 13. Totale 14 lanci.
Avete ragione! Mi cospargo il capo di cenere ;-)
--
[fadeout]

e se si rompe al trentaseiesimo piano, devi fare 65 tentativi
Be' ma non avevo mica capito bene cosa chiedeva.. e`
tutto sbagliato:-(


 99: lancio la seconda dal 96 al 97 per un massimo di 11+2=13
Se il piano di rottura fosse il 98, non potresti distinguerlo dal 99. Ti 
servirebbe comunque un lancio dal 98° piano.
Stefano 


Il modo generale di risolvere il problema e' rivoltarlo: "Quanti piani
'copro' con n palle e x tentativi?"
Risolto questo, si fa una bella equazione e si risolve il problema
originale.
La versione "rivoltata" si risolve cosi':
indichiamo con p(n,x) il numero di piani coperti da n palle e da x
tentativi.
Se lancio una palla dal un qualunque piano:
-la palla si rompe: il piano da individuare e' inferiore, e a questo
punto posso coprire p(n-1, x-1) piani
- la palla non si rompe: il piano e' superiore, e posso coprire p(n,
x-1) piani.
Quindi, se sommiamo i piani che posso avere sotto di me, quelli sopra e
quello a cui sono ottengo che p(n,x)=p(n-1, x-1) + p(n, x-1) + 1
Per n=1, si ha che p(1,x)=x    (con una palla sola l'unico modo e'
partire dalla base e farsi tutti i piani uno alla volta)
Per n=2 si arriva al p(2,x) = n*(n+1) (come giustamente diceva Marco
Dalai)
Per n=3 ...  c'e' da lavorarci un po' su, ma ci si arriva.

Uei, c'era un errore.
p(2,x) = n*(n+1)/2, non n*(n+1)
E infatti il Dalai scriveva che n*(n+1)>=2k


No, gli errori erano due!
p(2,x)= x*(x+1)/2
Avevo sbagliato simbolo.
x sono i tentativi, vero? Non e' che sto facendo dell'altro casino? :)

Stefano Gemma ha detto questo lunedì :

E' vero. Mi sono sbagliato... Ed anche in tutti gli altri sottocasi è 
necessario un lancio ulteriore.
--
[fadeout]

"Marco Dalai"  ha scritto nel messaggio

Già trattato su IHE
Vedi:
http://groups.google.it/group/it.hobby.enigmi/browse_frm/thread/d9a9c839c510f5fa/b2ecd915f94ed6e8?lnk=st&q=raffa+e+i+fagioli&rnum=1&hl=it#b2ecd915f94ed6e8
Ciao, Nino 

 
grazie del link, me lo guardo
ciao
marco