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}\} $?
Problema 5, oliforum contest 2009, round 2.
Problema 5, oliforum contest 2009, round 2.
The only goal of science is the honor of the human spirit.
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.
$ 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."
- - - - -
"Well, master, we're in a fix and no mistake."