Problema 5, oliforum contest 2009, round 2.

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Problema 5, oliforum contest 2009, round 2.

Messaggio da jordan » 18 ott 2009, 20:34

Problema 5.
Own. Sia definita la funzione $ g(\cdot):\mathbb{Z} \to \{0,1\} $ di modo tale che $ g(n)=0 $ se $ n<0 $, altrimenti $ g(n)=1 $. Sia definita la funzione $ f(\cdot):\mathbb{Z} \to \mathbb{Z} $ di modo tale che $ f(n)=n-1024g(n-1024) $ per ogni $ n \in \mathbb{Z} $. Definiamo la sequenza degli interi $ \{a_i\}_{i \in \mathbb{N}} $ di modo tale che $ a_0=1 $ e $ a_{n+1}=2f(a_n)+\ell $, dove $ \ell=0 $ se $ \displaystyle \prod_{i=0}^n{\left(2f(a_n)+1-a_i\right)}= 0 $, e $ \ell=1 $ altrimenti. Quanti elementi distinti ha l'insieme $ S:=\{a_0,a_1,\ldots,a_{2009}\} $?
The only goal of science is the honor of the human spirit.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 16 dic 2009, 17:25

2010.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 16 dic 2009, 17:26

Fico :lol:
The only goal of science is the honor of the human spirit.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 31 dic 2009, 09:39

Giusto per chiarire le cose, il testo è un modo complicato per dire che la successione è

$ a_0 = 1 $
$ a_{n+1} = ( 2 a_n + \ell ) \bmod 2048 $,

dove $ \ell $ vale 1, a meno che ciò non comporti una ripetizione di un termine precedente, nel qual caso vale 0.

Dim.: Esercizio. Si tratta solo di dipanare la notazione. Niente di profondo o interessante... []

Dico che la successione prende tutti i valori interi da 1 a 2047 una e una sola volta, dopodiché vale definitivamente 0.

Sketch di dimostrazione:

Viene utile pensare i numeri da 0 a 2047 in binario, ossia come le stringhe di undici caratteri 0, 1. La regola della ricorsione è quindi uno "shift a destra senza riporto". La cifra meno significativa è $ \ell $, scelta con la regola "1, a meno di ripetizioni". Nel seguito, $ S $ indicherà una sottostringa di dieci caratteri 0, 1, $ x $ un carattere 0, 1.

Fatto 0. Ogni stringa ha esattamente due possibili successori e due possibili predecessori. Più precisamente, $ xS $ ha come possibili successori $ S0 $ e $ S1 $, mentre $ Sx $ ha come possibili predecessori $ 0S $ e $ 1S $. Se compare un termine pari $ S0 $, il termine dispari $ S1 $ deve essere comparso in precedenza.

Ovvio, per come è definita la successione. []

Fatto 1. Il primo termine che si ripete è 0.

Dim.: Consideriamo il primo termine che si ripete. E' ovviamente pari, dato che per costruzione i termini dispari compaiono solo una volta, ossia è della forma $ S0 $. Dico che $ S=0 $

Per il Fatto 0, nella successione devono esistere tre posizioni in cui compaiono i termini $ S1 $, $ S0 $, $ S0 $, nell' ordine (ma non necessariamente consecutive).

Se $ S1 $ ha un predecessore, sempre per il Fatto 0, i tre predecessori di $ S1 $, $ S0 $, $ S0 $, sono $ 0S $ oppure $ 1S $, quindi abbiamo una ripetizione, laddove avevamo supposto che $ S0 $ fosse il primo termine a ripetersi. Allora $ S1 $ non ha predecessore, ossia è il primo termine della successione, cioè 1. []

Corollario. Dopo, la successione è definitivamente 0. []

Fatto 2. Se $ a $ è una stringa che non compare nella successione, allora anche il suo successore pari $ 2a \bmod 2048 $ non compare.

Dim.: Si usa il Fatto 0. Esercizio.[]

Fatto 3. Tutte le stringhe compaiono nella successione.

Dim.: Supponiamo di no. Sia $ a $ una stringa che non compare. Applico ripetutamente il Fatto 2. In un numero finito di passi arrivo a dimostrare che 0 non appartiene alla successione, contro il Fatto 1. []

Corollario: I termini $ a_0, a_1, \dots, a_{2009} $ sono tutti distinti.. []

E questo chiude l'esercizio: la risposta è 2010.

Nota: cambiando le stringhe di 11 caratteri con stringhe di lunghezza fissata $ q $ qualunque, e il parametro 2048 con $ 2^q $, si dimostra il risultato analogo, che la successione

$ a_0 = 1 $
$ a_{n+1} = ( 2 a_n + \ell ) \bmod 2^q $,

assume tutti i valori da $ 1 $ a $ 2^q - 1 $ una ed una sola volta, dopodiché vale definitivamente 0.

Buon anno a tutti!

M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Rispondi