187. Problema serbo

[AlexThirty]

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]n naturale, sia [math]A l'insieme [math]\{1,2,3,\ldots,2^{n}\}.
Determinare la più grande cardinalità possibile di un sottoinsieme [math]S di [math]A con la seguente proprietà: per ogni [math]x,y \in S, x\neq y, v_{2}(x-y) è pari.

[LucaMac]

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!

[AlexThirty]

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