187. Problema serbo

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

187. Problema serbo

Messaggio da AlexThirty » 07 ott 2015, 19:47

Avendo risposto circa due mesi fa a un problema della staffetta e avendo scritto una soluzione che può anche stare in piedi, mi rendo conto di essere in ritardo per la continuazione di questa tradizione. Quindi con tutta foga vi propongo questo problema che mi è sembrato molto intrigante anche se può darsi che qualcuno lo abbia già visto

Dato un numero [math] naturale, sia [math] l'insieme [math].
Determinare la più grande cardinalità possibile di un sottoinsieme [math] di [math] con la seguente proprietà: per ogni [math] è pari.
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.

LucaMac
Messaggi: 174
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: 187. Problema serbo

Messaggio da LucaMac » 07 ott 2015, 20:16

Allora definiamo $a_n$ la massima cardinalità in modo che quella cosa è sempre pari e $b_n$ in modo che quella cosa è sempre dispari.
Rinomino $A$ come $A_n$.
Voglio calcolare $a_{n+1}$ ! Prendo un qualsiasi elemento di $A_{n+1}$ e noto che questo "non interagisce" minimamente con quelli di parità diversa ( si avrebbe $v_2(x-y)=0$ che è pari! ). Allora considero disgiuntamente gli insiemi $B_{n+1} = \{ 1, 3, \ldots , 2^{n+1} -1 \} $ e $C_{n+1} = \{ 2 , 4 , \ldots , 2^{n+1} \} $ , hanno entrambi cardinalità $2^n$. Presi due elementi $x=2r-1$ e $y=2s-1$ si $B_{n+1} $ si ha che $v_2(x-y) = 1 + v_2(r-s) $ , allora visto che al variare di $x$ e $y$ si ha che $r$ e $s$ variano su tutto e solo $A_n$ , prendo esattamente $b_n$ elementi. Analogamente con $C_{n+1} $ e $x=2r , y=2s$ . Quindi si ottiene $a_{n+1} = 2 \cdot b_n $.
Calcoliamo ora $b_{n+1}$ ! Prendo un qualsiasi elemento di $A_{n+1}$ e noto che se lui è in $S$ allora un qualsiasi numero che ha parità diversa non vi è. Allora WLOG (è uguale, come nel caso di prima perchè a me interessano le differenze..) si considerano solo i numeri pari ( ovvero $C_{n+1}$ ). Analogamente la valutazione duadica cambia di parità, e quindi , potendo considerare solo uno tra $B_{n+1}$ e $C_{n+1}$ si ottiene $b_{n+1}=a_n$.
Ma allora $a_{n+2} = 2 \cdot a_n $. Ora $a_1 = 2 $ e $ a_2 = 2$ , quindi $a_{2k+1} = 2^{k+1} $ e $a_{2k} = 2^k$.
E boh, la mia dimostrazione dovrebbe anche mostrare che algoritmicamente si trova l'uguaglianza!
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"

AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

Re: 187. Problema serbo

Messaggio da AlexThirty » 07 ott 2015, 20:57

Mi pare che il tutto funzioni!
Il mio metodo era simile: partiva dalle stesse basi (elementi di parità diversa non mi interessano quindi giardo solo come interagiscono pari con pari e dispari con dispari) solo che non mi era venuto in mente l'approccio ricorsivo e provavl a contarli con metodi furbi e non
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.

Rispondi