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!
Salti e bombe su N
IMO 6 del 2009...
Dovrebbe essere facilotto, se non erro l'ha risolto una decina di persone al mondo...
Dovrebbe essere facilotto, se non erro l'ha risolto una decina di persone al mondo...
Ultima modifica di dario2994 il 15 feb 2010, 15:49, modificato 1 volta in totale.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
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ò
Induzione... tutt'altro che straight-forward però
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
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.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
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.
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.
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.
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...
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...
Non si smette mai di imparare.
[OT]
[/OT]
Ecco, dove posso trovare le soluzioni delle IMO più recenti?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
[/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
<<Se avessi pensato (se pensassi) che la matematica è solo tecnica
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $
e non anche cultura generale; solo calcolo e non anche filosofia,
cioè pensiero valido per tutti, non avrei fatto il matematico (non
continuerei a farlo)>> (Lucio Lombardo Radice, Istituzioni di
Algebra Astratta).
Mathforum
$ \displaystyle\zeta(s)=\sum_{n=1}^\infty \frac {1}{n^s} $