Salti e bombe su N

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
iny92
Messaggi: 8
Iscritto il: 01 apr 2008, 17:00

Salti e bombe su N

Messaggio da iny92 » 15 feb 2010, 15:37

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!

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 15 feb 2010, 15:47

IMO 6 del 2009...
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

iny92
Messaggi: 8
Iscritto il: 01 apr 2008, 17:00

Messaggio da iny92 » 15 feb 2010, 15:48

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 :D

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 15 feb 2010, 15:51

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ò
...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

iny92
Messaggi: 8
Iscritto il: 01 apr 2008, 17:00

Messaggio da iny92 » 15 feb 2010, 15:58

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! :D

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 15 feb 2010, 16:06

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

iny92
Messaggi: 8
Iscritto il: 01 apr 2008, 17:00

Messaggio da iny92 » 15 feb 2010, 19:32

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

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Messaggio da Euler » 20 mar 2010, 23:23

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

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. :)

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Messaggio da Euler » 20 mar 2010, 23:44

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

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Messaggio da Euler » 21 mar 2010, 15:11

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.

Avatar utente
ghilu
Messaggi: 177
Iscritto il: 06 gen 2008, 18:14
Località: bergamo

Messaggio da ghilu » 10 giu 2010, 11:20

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...
Non si smette mai di imparare.

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Messaggio da Euler » 10 giu 2010, 11:44

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 :)
cogito ergo demonstro

Avatar utente
<enigma>
Messaggi: 876
Iscritto il: 24 set 2009, 16:44

Messaggio da <enigma> » 20 giu 2010, 15:06

[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]

matty96
Messaggi: 343
Iscritto il: 21 apr 2010, 14:30
Località: Matelandia di Calabria (CS)

Messaggio da matty96 » 23 giu 2010, 21:24

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} $

flexwifi
Messaggi: 90
Iscritto il: 11 giu 2007, 22:04

Messaggio da flexwifi » 24 giu 2010, 10:03

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

Rispondi