[L06] $\sqrt[3]{6n}$

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

[L06] $\sqrt[3]{6n}$

Messaggioda Federico II » 29/09/2015, 14:12

Sia $n$ un intero positivo. Sia $A$ un sottoinsieme di $\{1,\ldots,n\}$. Un'$A$-partizione di $n$ in $k$ parti è una rappresentazione di $n$ nella forma $a_1+\ldots+a_k$, dove $a_1,\ldots,a_k$ sono elementi di $A$ non necessariamente distinti. Il numero di parti distinte dell'$A$-partizione è il numero di elementi distinti dell'insieme $\{a_1,\ldots,a_k\}$. Un'$A$-partizione di $n$ in $k$ parti si dice ottimale se non esistono $A$-partizioni di $n$ in $r$ parti con $r<k$. Dimostrare che ogni $A$-partizione di $n$ ottimale ha al più $\sqrt[3]{6n}$ parti distinte.
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53

Re: [L06] $\sqrt[3]{6n}$

Messaggioda Federico II » 03/10/2015, 13:16

Up!
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53

Re: [L06] $\sqrt[3]{6n}$

Messaggioda Delfad0r » 03/10/2015, 21:02

Vorrei innanzitutto ringraziare Federico II per i suoi problemi, sempre stimolanti ed interessanti :D

Testo nascosto:
Se $\Xi$ è un insieme finito, indichiamo con $\sum_{\Xi}$ la somma dei suoi elementi.

Lemma Vagamente Utile. Sia $\mathfrak{A}=\{a_1,\ldots,a_m\}$ un insieme finito di interi positivi (distinti fra loro), tale che
$$
a_1+\ldots+a_m\le \frac{m^3}{6}
$$
Allora esistono $\mathfrak{A}_1,\mathfrak{A}_2$ sottoinsiemi di $\mathfrak{A}$ tali che $|\mathfrak{A}_1|\neq|\mathfrak{A}_2|$ e $\sum_{\mathfrak{A}_1}=\sum_{\mathfrak{A}_2}$.

Dimostrazione. Supponiamo per comodità $a_1<\ldots<a_m$.
Cominciamo col dimostrare il seguente fatto: esistono almeno $1+j(m-j)$ sottoinsiemi di $\mathfrak{A}$ di cardinalità $j$ in modo che, presi due di questi sottoinsiemi, la somma dei loro elementi sia diversa. Mostriamo direttamente come costruirli; partiamo con l'insieme $\mathfrak{U}=\{a_1,\ldots,a_j\}$ e applichiamo ripetutamente la seguente mossa: prendiamo il più grande $i<m$ tale che $a_i\in\mathfrak{U}$ e $a_{i+1}\not\in\mathfrak{U}$, eliminiamo $a_i$ da $\mathfrak{U}$ e lo sostituiamo con $a_{i+1}$. Si vede che a ogni mossa $\sum_{\mathfrak{U}}$ aumenta strettamente (togliamo un elemento e ne inseriamo uno più grande). L'algoritmo funziona così: in $m-j$ mosse sostituisce $a_j\to a_{j+1}\to\ldots\to a_{m}$, poi con altre $m-j$ mosse sostituisce $a_{j-1}\to\ldots\to a_{m-1}$, e così via fino alle ultime $m-j$ mosse, che sono $a_1\to\ldots\to a_{m-j+1}$; abbiamo così $j$ gruppi di $m-j$ mosse. Quindi, considerando anche l'insieme iniziale, abbiamo costruito $1+j(m-j)$ insiemi di cardinalità $j$ tutti con somme diverse.
Pertanto, se definiamo
$$
K(j):=\left\{\sum_{\mathfrak{U}}:\mathfrak{U}\subseteq\mathfrak{A},|\mathfrak{U}|=j\right\}
$$
abbiamo dimostrato che $|K(j)|\ge 1+j(m-j)$. Supponiamo ora per assurdo che la tesi sia falsa. Ciò vuol dire che, per ogni $i\neq j$, $K(i)$ e $K(j)$ sono disgiunti. Pertanto il numero di somme distinte ottenibili con i sottoinsiemi di $\mathfrak{A}$ è
$$
\sum_{j=1}^{m}|K(j)|\ge\sum_{j=1}^{m}(1+mj-j^2)=m+\frac{m^2(m+1)}{2}-\frac{m(m+1)(2m+1)}{6}=\frac{m(m^2+5)}{6}>\frac{m^3}{6}
$$
il che è assurdo, dato che la somma massima ottenibile è $a_1+\ldots+a_m\le\frac{m^3}{6}$ e la minima è almeno $1$.

Veniamo ora al problema vero e proprio. Come di consuetudine, supponiamo per assurdo che la tesi sia falsa, ovvero che esista un'$A$-partizione ottimale di $n$ con più di $\sqrt[3]{6n}$ parti distinte; in particolare, siano $a_1,\ldots,a_m$ le parti distinte di questa partizione, con $m>\sqrt[3]{6n}$. Sicuramente vale
$$
a_1+\ldots+a_m\le n<\frac{m^3}{6}
$$
e inoltre tutti gli $a_i$ sono interi positivi (se ci fosse uno $0$ la partizione non sarebbe ottimale), quindi possiamo applicare il Lemma Vagamente Utile: questo ci dice che esistono indici $u_1,\ldots,u_r,w_1\ldots,w_s$ con $r>s$ e $a_{u_1}+\ldots+a_{u_r}=a_{w_1}+\ldots+a_{w_s}$. Ma ciò è assurdo: possiamo infatti sostituire l'occorrenza nella partizione di $a_{u_1}+\ldots+a_{u_r}$ con $a_{w_1}+\ldots+a_{w_s}$, ottenendo una nuova $A$-partizione di $n$ in meno parti di quella originale, che quindi non era ottimale.
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: [L06] $\sqrt[3]{6n}$

Messaggioda Federico II » 04/10/2015, 12:58

Buona, i problemi che metto li scelgo tra i migliori che mi capitano in modo da far uscire roba interessante. Comunque,
Testo nascosto:
sei pronto per la duplice trasferta Hong Kong - Russia?
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite