Pagina 1 di 5
Inviato: 01 gen 1970, 01:33
da ma_go
Allora, propongo due problemi (di cui uno, se quello che mi hanno riferito non è falso, proposto a qualche IMO):
<BR>
<BR>1) Abbiamo due sfere e un palazzo di 100 piani. Da un certo piano in su la sfera si rompe sempre se lasciata cadere, mentre al di sotto no. Dobbiamo determinare da quale piano si rompe. Dobbiamo determinare il minimo del massimo di mosse in base alla strategia (non so quanto sia stato chiaro...)
<BR>
<BR>2) Abbiamo una scacchiera 11x11 e 22 pedine su di essa, disposte in modo tale che ce ne siano esattamente 2 per riga e 2 per colonna. Diciamo che due di queste disposizioni sono equivalenti se si può ottenere l\'una dall\'altra con un numero FINITO di permutazionidi righe o colonne (ad esempio scambiare la prima riga con la quinta, o la sesta colonna con la ottava). Sia S l\'insieme di tutte le disposizioni e R la relazione di equivalenza. Determinare la cardinalità di S/R (cioè il numero di relazioni non equivalenti tra loro).
<BR>
<BR>Il primo non è impossibile, il secondo... evitiamo i commenti! In bocca al lupo!
Inviato: 01 gen 1970, 01:33
da Azarus
ma con mossa nel primo cosa intendi?
Inviato: 01 gen 1970, 01:33
da acarus
Già!
<BR>
<BR>E poi: che te ne fai di due sfere?<BR><BR>[ Questo Messaggio è stato Modificato da: acarus il 24-02-2003 14:25 ]
Inviato: 01 gen 1970, 01:33
da acarus
Azzardo:
<BR>
<BR>Il numero massimo di mosse si riferisce al numero minimo di prove che occorre fare per determinare \"l\'altezza di rottura\"?
<BR>Se così fosse due sfere non bastano di certo.
<BR>
<BR>
<BR>O no?
<BR>Finchè si prova stando al di sotto del piano incriminato, la sfera non si rompe, quindi la si può riciclare! <IMG SRC="images/forum/icons/icon_smile.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: acarus il 24-02-2003 14:39 ]
Inviato: 01 gen 1970, 01:33
da acarus
Ci provo:
<BR>
<BR>Detto n il piano relativo alla rottura, il numro minimo di prove da fare è n+1: ecco a cosa serve la seconda sfera: ad avere la conferma al piano successivo a quello dove si è rotta la prima!
<BR>
<BR>Si o no???
Inviato: 01 gen 1970, 01:33
da publiosulpicio
Io ho trovato un modo che qualunque sia il piano in al massimo 20 mosse lo individui, ma fose si può fare meglio...
Inviato: 01 gen 1970, 01:33
da publiosulpicio
No, scusate, bastano, almeno secondo me 19 mosse
Inviato: 01 gen 1970, 01:33
da lordgauss
Il secondo viene dalle gare della Bocconi... apparirà strano, ma è così.
Inviato: 01 gen 1970, 01:33
da ma_go
No. si può scendere ancora. e si può sempre tentare di determinare la soluzione nel caso generale... non è così difficile!
<BR>
<BR>Ma il secondo davvero viene dai giochi della bocconi?? e tu hai la soluzione? io ho un numero in testa, vorrei la conferma!
Inviato: 01 gen 1970, 01:33
da Israfel_FMD
Allora, per prima cosa chiariamo la consegna del primo: se ho capito bene, una \"mossa\" equivale a gettare contemporaneamente due sfere da due piani diversi, e quel che bisogna trovare è il numero minimo di mosse per trovare il piano \"critico\" in un palazzo di n piani (in questo caso n=100). Se mi sono sbagliato, lascia stare la soluzione proposta e correggimi.
<BR>
<BR>Secondo me il procedimento da seguire è questo (lo generalizzo per m sfere e n piani perchè mi risulta più semplice e non devo fare i calcoli a mente):
<BR> - divido gli n piani in (m+1) parti
<BR> - getto una sfera da ognuno dei piani di \"confine\"
<BR> - individuo la parte del palazzo in cui si trova il piano critico
<BR> - ripeto il procedimento sopra limitandomi alla parte individuata, finchè non arrivo a selezionare non più di m piani
<BR>
<BR>In questo modo, il numero di mosse *dovrebbe* essere (log[m+1] (n/m))+1, ossia il numero di volte che devo moltiplicare (m) per (m+1) per ottenere n, più la mossa finale (ho fatto un paio di verifiche con la calcolatrice e forse è corretto); temo però che gli arrotondamenti per i numeri interi facciano casino.
<BR>Nel caso specifico, (m=2, n=100) abbiamo 5 mosse. Esempio di soluzione (poniamo che 61 sia il piano critico):
<BR>
<BR>mosse / piani rimasti
<BR>0 / 1-100
<BR>1 / 34-67
<BR>2 / 58-67
<BR>3 / 58-61
<BR>4 / 60-61
<BR>5 / 61
<BR>
<BR>Riguardo al secondo problema (a cui penserò con parecchia calma) la domanda vuol forse dire semplicemente \"trovare il numero di disposizioni non equivalenti fra di loro\"?
<BR>
<BR>[addsig]
Inviato: 01 gen 1970, 01:33
da ma_go
No. una mossa equivale a gettare UNA sfera. se una sfera si rompe te ne resta una sola.
<BR>
<BR>Per il secondo si.
<BR>
<BR>Ma... tu saresti stefano??
Inviato: 01 gen 1970, 01:33
da Azarus
ma se hai buttato la palla dal 100-esimo piano si è rotta....
Inviato: 01 gen 1970, 01:33
da ma_go
allora vorrà dire che non è la strategia migliore!
Inviato: 01 gen 1970, 01:33
da Azarus
lol intendevo nell\'esempio di Israel
Inviato: 01 gen 1970, 01:33
da Squirtledgl
Posso farcela in 18 tentativi!!!!!!!!!!!
<BR>Si può fare di meglio????? O posso svelare la mia soluzione???