OliForum Matematico

Ciao ragazzi!

Consideriamo una serie di caselle successive numerate secondo i numeri naturali 0, 1, 2, 3, ....
Ci viene assegnato un insieme di n+1 numeri naturali DISTINTI (che chiamiamo "salti").
EDIT: avevo dimenticato di precisare che ovviamente i salti sono diversi da 0.
Tra le caselle (esclusa la 0 e quella che ha il numero corrispondente alla somma dei salti assegnatici) ce ne sono n che contengono una bomba, quindi non le possiamo toccare.
Ci troviamo sulla casella "0" dei numeri naturali. Noi dobbiamo effettuare tutti e soli i salti (sempre in avanti) che ci sono stati assegnati, nell'ordine che preferiamo, evitando di finire su una casella con la bomba.
Dimostrare che data una qualsiasi configurazione di bombe e di salti assegnati, esiste sempre un modo di ordinare i salti tale per cui NON si finisce su una bomba.
Esempio:
Ci vengono assegnati un salto da 1, un salto da 2, un salto da 3.
Le bombe stanno in 1 e 3 (in 0 e in 6 non potevano esserci comunque bombe).
In questo caso dobbiamo per forza fare prima il salto da 2, poi quello da 3 e poi quello da 1.

Io NON conosco la soluzione di questo problema (e chi me lo ha fatto non se la ricorda), non so se è facile o difficile... per favore potete aiutarmi? ci ho pensato un sacco ma non riesco a risolverlo!

Grazie!

IMO 6 del 2009...
Dovrebbe essere facilotto, se non erro l'ha risolto una decina di persone al mondo...

Ah grazie non lo sapevo!! Allora non sarà mica tanto facile! Provo a cercare una soluzione su internet allora! Se non la trovo, chiedo di nuovo a voi! Grazie

No fermati... se ti senti particolarmente coraggioso (e pieno di tempo libero) ti posso dare un hint così magari ci provi... non sono certissimo che funga, perchè io non ho mai letto completamente la soluzione, ma mi pare che fosse così:

Induzione... tutt'altro che straight-forward però

Guarda... ti ringrazio, ma ci ho già provato un sacco a fare come dici nell'hint... però proprio non riesco... per cui o mi dai un hint più "sostanzioso", oppure cedo e cerco su internet!

Non per altro è un IMO 6. Comunque non ho altri hint da dare... più che altro perchè non conosco e non voglio conoscere la dimostrazione.

Alla fine ho ceduto e ho cercato su internet...
però devo dire che la soluzione è bellissima, elegante e semplice! (ok, magari trovarla NON è semplice, ma quando uno ce l'ha davanti ci si chiede "come ho fatto a non arrivarci?")
...quindi in definitiva se siete interessati provateci!
Ciao

Penso di avere trovato la dimostrazione, ma non sono sicuro...

Supponiamo che i salti assegnatici siano nella successione aritmetica 1,2,3,4... e si indichi con n il salto più grande e quindi il numero di salti; allora le caselle saranno │0│1│2│...│n(n+1)/2│.Ora ragioniamo per assurdo e cerchiamo di sistemare le bombe (che saranno n-1) in modo da evitare un certo salto prestabilito.
Supponiamo di voler evitare il salto 2. Per ostacolarlo, dovremo sistemare le bombe in questo modo (le caselle sono in ordine e i quadrati sono le bombe):
│0│ │■│■│ │ │■│■│ │... Adesso cerchiamo di evitare i salti da 3:
│0│ │ │■│■│■│ │ │ │■│■│■│ │... Andando avanti si nota che in un certo intervallo bisogna coprire sempre la metà delle caselle (con un eventuale resto). Le bombe sono n-1 e la metà delle caselle n(n+1)/4, e si può verificare in modo algebrico che n-1<n>0), per n appartenente agli interi positivi (abbiamo considerato che bisogna coprire esattamente metà delle caselle, ma un eventuale resto non cambierebbe la disequazione).
Ora estendiamo il nostro ragionamento senza considerare successioni.Dapprima supponiamo di togliere alla successione di prima un salto (indicato con k); Le bombe saranno n-2 (si toglie un salto). Risulta che n-2<n>0 (dopo alcuni passaggi algebrici), ed è verificata per ogni n e k appartenenti agli interi positivi e n>k.
Continuando con 2 salti in meno abbiamo che n-3<n>0, che anche questa è sempre verificata (sempre per n>k+h). Andando avanti con il numero di salti in meno , la disequazione continua a risultare valida finchè non esauriamo tutti i salti da togliere.
Concludendo, non esisterà mai una disposizione di bombe tale da evitare un cerrto tipo di salto, quindi sarà sempre possibile disporre i salti in modo da evitare le bombe c.v.d.

Ammetto che la dimostrazione sia un po' empirica, ma spero che verrà perfezionata.

Scusate ma ho un problema di caratteri ...
domani cercherò di risolverlo per inviare la dimostrazione completa.

Ecco la dimostrazione giusta (ho avuto dei problemi con i simboli di maggiore e minore, quindi li ho sostituiti a parole tra parentesi quadre):

Supponiamo che i salti assegnatici siano nella successione aritmetica 1,2,3,4... e si indichi con n il salto più grande e quindi il numero di salti; allora le caselle saranno │0│1│2│...│n(n+1)/2│.Ora ragioniamo per assurdo e cerchiamo di sistemare le bombe (che saranno n-1) in modo da evitare un certo salto prestabilito.
Supponiamo di voler evitare il salto 2. Per ostacolarlo, dovremo sistemare le bombe in questo modo (le caselle sono in ordine e i quadrati sono le bombe):
│0│ │■│■│ │ │■│■│ │... Adesso cerchiamo di evitare il salto da 3:
│0│ │ │■│■│■│ │ │ │■│■│■│ │... Andando avanti si nota che in un certo intervallo bisogna coprire sempre la metà delle caselle (con un eventuale resto). Le bombe sono n-1 e la metà delle caselle n(n+1)/4, e si può verificare in modo algebrico che n-1[minore di]n(n+1)/4 (alla fine risulta n^2-3n+4[maggiore di]0), per n appartenente agli interi positivi (abbiamo considerato che bisogna coprire esattamente metà delle caselle, ma un eventuale resto non cambierebbe la disequazione).
Ora estendiamo il nostro ragionamento senza considerare successioni.Dapprima supponiamo di togliere alla successione di prima un salto (indicato con k); Le bombe saranno n-2 (si toglie un salto). Risulta che n-2[minore di]n(n+1)/4-k, cioè che n^2-3n-4k+8[maggiore di]0 (dopo alcuni passaggi algebrici), ed è verificata per ogni n e k appartenenti agli interi positivi e n>k.
Continuando con 2 salti in meno abbiamo che n-3[minore di]n(n+1)/4-k-h (h è il nuovo salto in meno), quindi n^2-3n-4k-4h+12[maggiore di]0, che anche questa è sempre verificata (sempre per n>k+h). Andando avanti con il numero di salti in meno , la disequazione continua a risultare valida finchè non esauriamo tutti i salti da togliere.
Concludendo, non esisterà mai una disposizione di bombe tale da evitare un cerrto tipo di salto, quindi sarà sempre possibile disporre i salti in modo da evitare le bombe c.v.d.

Scusami se ti confuto, ma la faccenda è più complicata di quanto pensi.
Per interdire dei salti in progressione aritmetica non servono $ $\frac{n\cdot (n+1)}{2} $ come dici. Se così fosse, la stima di (n-1) bombe sarebbe molto larga in qualche caso (e quindi non difficile da smontare).
Tuttavia la stima è in realtà "ottimale", nel senso che, ad esempio, per la progressione 1,...,n bastano solo "n" bombe consecutive...

Cavolo dopo tre mesi qualcuno mi risponde! Comunque me ne ero già accorto che ho sparato una grossa cazzata ma ora ho poco tempo per pensarci perchè devo fare le dimostrazioni per lo Stage Senior...comunque grazie

[OT]

iny92 ha scritto:Alla fine ho ceduto e ho cercato su internet...
però devo dire che la soluzione è bellissima, elegante e semplice! (ok, magari trovarla NON è semplice, ma quando uno ce l'ha davanti ci si chiede "come ho fatto a non arrivarci?")
...quindi in definitiva se siete interessati provateci!
Ciao

Ecco, dove posso trovare le soluzioni delle IMO più recenti?
[/OT]

vedi su questo sito.Però ci sono soltanto quelle del 2006(sono PreImo,non so se ti vanno bene),degli altri anni ci sono solo i testi.Altrimenti puoi controllare i giornalini della matematica e trovare qualche problema delle IMO,cosi' ti scarichi anche la soluzione

Per il problema 6 delle IMO 2009 qui puoi trovare una soluzione in inglese