104 [L04] BST 2013

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

104 [L04] BST 2013

Messaggioda bern1-16-4-13 » 04/01/2016, 23:34

Degli interi positivi, non necessariamente distinti, sono stati scritti in una fila. Ad ogni
passaggio il nostro carissimo amico Carmelo sceglie (se esistono) due interi [tex]x[/tex] e [tex]y[/tex] scritti in posizioni adiacenti,
con [tex]x[/tex] a sinistra di [tex]y[/tex] e [tex]x > y[/tex]. Poi rimpiazza la coppia [tex](x, y)[/tex] con [tex](y + 1, x)[/tex] o [tex](x − 1, x)[/tex] a sua scelta.
Dimostrare che Carmelo può effettuare solo un numero finito di queste operazioni.
mentre il mondo persiste nei suoi sanguinosi conflitti, la vera guerra è combattuta dai matematici
bern1-16-4-13
 
Messaggi: 179
Iscritto il: 27/11/2014, 22:10
Località: Firenze

Re: 104 [L04] BST 2013

Messaggioda Ale99 » 05/01/2016, 10:50

Ok vediamo un po' ...

Testo nascosto:
[Consideriamo , ad un certo punto della successione di mosse , la somma
$ S = \sum_{i=1}^{n} 2^{i-1} a_ i $
Notiamo ora che la mossa $ ( a_1,a_{i+1} ) \rightarrow ( b , a_1 ) $ dove $ b = a_{i+1} + 1 , a_i - 1 $ aumenta strettamente la somma .
Osserviamo che il massimo $M$ della successione non cambia .
Dunque la somma $ S $ se le mosse fossero infinite arriverebbe a superare $ (2^n-1)M $ , ma cioè é assurdo in quanto avevamo detto che il massimo della successione non cambia .
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Avatar utente
Ale99
 
Messaggi: 482
Iscritto il: 24/08/2014, 11:51

Re: 104 [L04] BST 2013

Messaggioda Linda_ » 05/01/2016, 11:00

Arrivo un po' in ritardo ma posto anche la mia!

Testo nascosto:
Notiamo che dopo ogni mossa il numero di sinistra diventa sempre $\leq$ di quello di destra perché $x>y\rightarrow x\geq y+1$ e poi comunque $x>x-1$.
E adesso induzione! Chiamiamo $n$ il numero di interi scritti in fila.

Passo base $n=2$. Ok, funziona, al massimo possiamo fare una mossa perché poi il numero di destra diventerà maggiore di quello di sinistra.

Supponiamo che funzioni per $n=2, 3, \ldots, k-1$ con $k\in\mathbb{Z^+}$

Passo induttivo $n=k$. Ci ricondurremo ora al caso $n=k-1$.
Supponiamo che $A$ sia il numero maggiore scritto in fila (e notiamo che il massimo non cambia mai) e prendiamo l'intero $A$ posto più a destra. Sicuramente potremo applicare una mossa alla coppia formata da $A$ e dal valore alla sua destra dato che $A$ è il massimo e l'abbiamo preso in modo tale che i numeri alla sua destra siano strettamente minori di lui. A questo punto $A$ slitta, indipendentemente dalla scelta del nostro Carmelo, al posto del valore alla sua destra per le ipotesi. Quindi potremo applicare ancora una volta una mossa considerando la coppia $A$ - il valore immediatamente alla sua destra, e allora $A$ continua a slittare verso destra, fino a quando non si troverà all'estremità destra della fila, dato che i valori di cui disponiamo sono in numero finito.
A questo punto $A$ non potrà più essere considerato per formare una coppia perché non ha valori alla sua destra e alla sua sinistra ci sono tutti numeri $\leq$ di lui e quindi abbiamo una "sottofila" di $k-1$ numeri. Ma con $k-1$ per ipotesi induttiva potevamo fare solo un numero finito di mosse, e allora il passo induttivo, da cui deriva la tesi, è dimostrato.
Linda_
 
Messaggi: 50
Iscritto il: 16/05/2014, 14:28

Re: 104 [L04] BST 2013

Messaggioda bern1-16-4-13 » 05/01/2016, 11:41

@Ale99: ok! (Quella somma degli [tex]a_i[/tex] non aveva bisogno delle potenze di [tex]2[/tex] per essere strettamente crescente, bastava moltiplicare ogni [tex]a_i[/tex] per il suo indice)
@Linda: l'idea è buona, ma devi spiegare meglio come mai siamo costretti a fare infinite mosse su A e il suo successivo, perché se così non fosse Carmelo non sarebbe costretto a far finire A in fondo alla fila (usa l'induzione estesa).
mentre il mondo persiste nei suoi sanguinosi conflitti, la vera guerra è combattuta dai matematici
bern1-16-4-13
 
Messaggi: 179
Iscritto il: 27/11/2014, 22:10
Località: Firenze

Re: 104 [L04] BST 2013

Messaggioda Ale99 » 05/01/2016, 12:01

In effetti non ce ne era bisogno , però lo usata perché mi aveva ricordato un problema del Senior molto simile e dove era necessaria ...
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Avatar utente
Ale99
 
Messaggi: 482
Iscritto il: 24/08/2014, 11:51


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti