L[04/05] Che belle le potenze di due!

[Gerald Lambeau]

Sia $n \ge 2$ un intero fissato e sia $A_n=\left\{ 2^n-2^k | k \in \mathbb{Z}, 0 \le k<n \right\}$.
Determinare il più grande intero positivo che non può essere espresso come somma di uno o più elementi (non necessariamente distinti) di $A_n$.

[0004POWER]

Credo sia 1, ma probabilmente é sbagliato

[Gerald Lambeau]

$n$ è fissato, quindi nell'insieme non ci vanno tutti i numeri così ottenuti per tutti gli $n$, ma per un solo $n$. Per esempio, il risultato per l'insieme $A_2$ è diverso da quello per l'insieme $A_3$.

[Salvador]

Non saprei, forse $2^{n+1}-1$?

[Gerald Lambeau]

No.

[Salvador]

Posto una possibile risposta, ma dovrei ancora aggiustare la mia ipotetica soluzione. @Gerald Lambeu è giusta?

Testo nascosto:

Chiamiamo $M(n)=(n-2)2^n+1$ e L(n) la quantità richiesta. Allora $M(n)=L(n)$ per ogni n.

[Gerald Lambeau]

È giusta, posta pure la tua soluzione .

[Salvador]

È giusta, posta pure la tua soluzione .

Testo nascosto:

Lemma 1: Chiamiamo $x_{ij}=2^j-2^i$. Abbiamo dunque $A_n=[2^n-1, 2^n-2, ..., 2^n-2^{n-1}]=[x_{0n},x_{1n},...,x_{(n-1)n}]$.
Osserviamo che $A_{n+1}=[2^{n+1}-1,2^{n+1}-2,...,2^{n+1}-2^n]=[2^{n+1}-1,2(2^n-1),...,2(2^n-2^{n-1})]=[2^{n+1}-1,2x_{0n},...,2x_{(n-1)n}]$, ovvero che gli elementi di $A_{n+1}$ sono tutti gli elementi di $A_n$ raddoppiati più $2^{n+1}-1$.

Lemma 2: Osserviamo che, dato un intero positivo pari $y$, se esiste una rappresentazione $y=m_1 x_1 + ... + m_h x_h$ (con $x_1, ..., x_h \in A_n-[2^n-1]$, allora dividendo per 2 si ha $y/2 = m_1 (x_1/2) + m_2 (x_2/2) + ... + m_h (x_h/2)$, ma per il Lemma 1 $x_1/2, ... , x_h/2 \in A_{n-1}$. Inoltre poiché $2^n-1$ è l'unico elemento dispari di $A_n$, se $x_h=2^n-1$, poiché $y$ per ipotesi è pari allora $m_h$ dev'essere pari: possiamo scrivere $m_h=2m$ e $m_h x_h = 2m(2^n-1)=2m(2^{n-1}+2^{n-1}-1)=2m(2^{n-1})+m(2^n-2)=2mx_{(n-1)n}+mx_{1n}$ grazie al Lemma 1: ciò vuol dire che se $y$ è rappresentabile con termini di $A_n$, allora $y/2$ è rappresentabile con termini di $A_{n-1}$, e viceversa.

Osserviamo che per $n=2$ si ha $A_2=[3,2]$, $M(2)=1$, e dunque $M(2)=L(2)$ in quanto se $x$ è un intero pari si può esprimere come somma di $x/2$ 2 e se $x\ge 3$ è un intero dispari si può esprimere come somma di $3 + 2 \dfrac{x-3}{2}$. Dunque la nostra tesi è vera per $n=2$.

Dimostriamo ora che $M(n)$ non è mai rappresentabile con termini di $A_n$. Supponiamo per assurdo che $v>2$ sia un intero per cui $M(v)$ sia rappresentabile con termini di $A_v$. Allora poiché $M(v)$ è dispari, la sua rappresentazione con termini di $A_v$ deve contenere almeno un addendo dispari, e poiché l'unico elemento dispari di $A_v$ è $2^v-1$, deve contenere quest'ultimo. Si ha dunque $w=M(v)-(2^v-1)=2^v(v-2)+1-2^v+1=2^v(v-3)+2$, e $w$ è rappresentabile con termini di $A_v$. Ma allora per il Lemma 2 $w/2=2^(v-1)(v-3)+1=M(v-1)$ dev'essere rappresentabile con termini di $A_{v-1}$. Iterando questo procedimento possiamo giungere alla conclusione che $M(2)$ sia rappresentabile con termini di $A_2$, ma ciò, come si è visto sopra, è assurdo. Ne deriva dunque che $M(n)$ non è mai rappresentabile con termini di $A(n)$.


Ora dimostriamo per induzione che ogni intero maggiore di $M(n)$ è rappresentabile con termini di $A_n$. Il passo base per $n=2$ l'abbiamo già verificato precedentemente. Supponiamo quindi la tesi vera per n-1 e sia $x=M(n)+2k$ un intero maggiore di $M(n)$ (dispari poiché $M(n)$ è dispari e $2k$ è pari). Troviamo ora una rappresentazione per $x$ in termini di $A_n$. Poiché $x$ è dispari, si ha che la nostra rappresentazione deve contenere $2^n-1$. Si ha dunque che $y=x-(2^n-1)=M(n)+2k-2^n+1=2^n(n-2)+1+2k-2^n+1=2^n(n-3)+2k+2$ dev'essere esprimibile come somma di termini di $A_n$: ciò è vero perché $y/2=2^{n-1}(n-3)+1+k>M(n-1)$, e dunque $y/2$ è rappresentabile con termini di $A_{n-1}$ perché per ipotesi $M(n)=L(n)$; di conseguenza, per il Lemma 2, anche $y$ è rappresentabile con termini di $A_n$ e pertanto anche $x$, come volevamo.
Analogamente sia $x=M(n)+2k+1$ un intero pari maggiore di $M(n)$. Allora si ha $x=2^n(n-2)+2k+2$ e $x/2=2^{n-1}(n-3)+1+2^{n-1}+k=M(n-1)+2^{n-1}+k$, dunque $x/2$ è rappresentabile con termini di $A_{n-1}$ e di conseguenza $x$ è rappresentabile con termini di $A_n$. Poiché il passo base per $n=2$ è già stato verificato, ne deriva la tesi.

@Gerald Lambeu è corretta? Come si può scriverla meglio per renderla "da gara"?
EDIT: Ho aggiunto una riga in più al Lemma 2 perché altrimenti la parte con $v$ non era del tutto giustificata.

[Salvador]

Scusate mi sapete dire se è giusta e se è scritta bene?

[Gerald Lambeau]

1) Attento che cambi l'uso della notazione da te introdotta nel Lemma 1 quando spieghi il Lemma 2.
2) Cos'è $M(v)$? Finirei volentieri di correggere, se solo sapessi cosa sto correggendo!!