[L05] Catene e anticatene

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

[L05] Catene e anticatene

Messaggioda Delfad0r » 15/11/2015, 23:42

Sia $S$ un insieme finito (ma non vuoto) di interi positivi tale che, se $x$ è un elemento di $S$, allora anche tutti i divisori positivi di $x$ lo sono. Un insieme non vuoto $B\subseteq S$ si dice buono se, per ogni $x,y\in B,x < y$, accade che $\frac{y}{x}$ è una potenza di un primo (in particolare, ogni singoletto è buono). Un insieme non vuoto $C\subseteq S$ si dice cattivo se, per ogni $x,y\in C$, accade che $\frac{y}{x}$ non è una potenza di un primo (in particolare, ogni singoletto è cattivo).
Sia $k$ la cardinalità del più grande sottoinsieme buono di $S$. Dimostrare che $k$ è anche il minimo numero di insiemi cattivi in cui è possibile partizionare $S$.


PS: nella BMO da cui proviene è classificato come TdN, ma a me pare più combinatoria, quindi finisce qui.
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: [L05] Catene e anticatene

Messaggioda cip999 » 16/11/2015, 16:10

È un po' un mix tra il PreIMO 14/C5, il secondo non noto del TF del Senior 15 e il C della Codeforces di ieri...

Testo nascosto:
Sia $n$ il numero di primi distinti che dividono almeno un elemento di $S$ e siano $p_1, \: p_2, \: \cdots, \: p_n$ questi primi. Gli elementi in $S$ saranno dunque interi della forma $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$ ($\alpha_i \ge 0$), con la restrizione che, ogni qualvolta $p_1^{\alpha_1}\cdots p_n^{\alpha_n} \in S$, anche $p_1^{\beta_1}\cdots p_n^{\beta_n} \in S$ per ogni possibile scelta di $\beta_i \le \alpha_i$. Definiamo inoltre $M_i$ il massimo esponente con cui $p_i$ compare nella fattorizzazione di almeno un elemento di $S$.
Chiamiamo $k'$ la minima cardinalità di un cover di $S$. Banalmente $k' \ge k$, poiché, preso un insieme buono di cardinalità massima, due suoi elementi non possono appartenere a uno stesso insieme cattivo. Non resta che mostrare l'altra disuguaglianza.
Consideriamo quindi un insieme buono $B$ di cardinalità $\ge 2$ e siano $a, \: b \in B$, $a > b$ tali che $\frac{a}{b} = p_i^u$ ($u \ge 1$). Allora, presi comunque $x, \: y$ in $B$, $x > y$, $\frac{x}{y}$ è potenza di $p_i$. Difatti, se così non fosse esisterebbero $c, \: d \in B$, $c > d$ e $j \ne i$ tali che $\frac{c}{d} = p_j^v$, $v \ge 1$. Ora, almeno uno tra $v_{p_j}(c)$ e $v_{p_j}(d)$ è diverso da $v_{p_j}(a)$ (WLOG $v_{p_j}(c)$), dunque $v_{p_i}(c) = v_{p_i}(a) \ne v_{p_i}(b)$; ma allora $\frac{b}{c} = p_i^{u'}p_j^{v'}$ (con $u', \: v' \ne 0$), ergo né $\frac{b}{c}$ né $\frac{c}{b}$ sono potenza di un primo, assurdo per definizione di $B$. Ne consegue che la massima cardinalità di un insieme buono è pari a $\displaystyle \max_{1 \le i \le n}\{M_i\} + 1$.
Ora WLOG $M_1 \ge M_2 \ge \cdots \ge M_n$. Vogliamo mostrare che è sempre possibile partizionare $S$ in al più $M_1 + 1$ insiemi cattivi. Senza perdita di generalità, possiamo assumere che $p_1^{M_1}p_2^{M_2}\cdots p_n^{M_n} \in S$: è chiaro infatti che la tesi in questo caso particolare è più forte che in tutti gli altri casi. Da adesso, induzione su $n$.
  • Passo base. $n = 1$: ovvio.
  • Passo induttivo. $n - 1 \mapsto n$ ($n \ge 2$). Supponiamo di saper partizionare l'insieme $S' = \{p_1^{\alpha_1}\cdots p_{n - 1}^{\alpha_{n - 1}} : 0 \le \alpha_i \le M_i\}$ in non più di $M_1 + 1$ insiemi cattivi. Preso $p_1^{\alpha_1}\cdots p_n^{\alpha_n} \in S$, lo mettiamo nello stesso insieme cattivo di $p_1^{\alpha_1}\cdots p_{n - 2}^{\alpha_{n - 2}}p_{n - 1}^r$, essendo $r$ il resto nella divisione per $M_{n - 1} + 1$ di $\alpha_{n - 1} + \alpha_n$.
    A questo punto verifichiamo che si tratti effettivamente di un cover in insiemi cattivi. Prendiamo $m = p_1^{\alpha_1}\cdots p_i^{\alpha_i}\cdots p_n^{\alpha_n}$ e $\ell = p_1^{\alpha_1}\cdots p_i^{\alpha_i'}\cdots p_n^{\alpha_n}$ in $S$, con $0 \le i < n$ e $\alpha_i > \alpha_i'$: per ipotesi induttiva, $m$ ed $\ell$ sono in insiemi diversi. Siano invece $s = p_1^{\beta_1}\cdots p_n^{\beta_n}$ e $t = p_1^{\beta_1}\cdots p_n^{\beta_n'}$ (con $\beta_n > \beta_n'$) ancora due elementi di $S$. Se, per assurdo, si trovassero nello stesso insieme cattivo, si dovrebbe avere (per costruzione) $$\beta_{n - 1} + \beta_n \equiv \beta_{n - 1} + \beta_n' \pmod{M_{n - 1} + 1} \implies \beta_n \equiv \beta_n' \pmod{M_{n - 1} + 1}$$ Ma questo non è possibile a meno che $\beta_n = \beta_n'$, dal momento che $\beta_n, \: \beta_n' \le M_n < M_{n - 1} + 1$.
E quindi fine.
Ultima modifica di cip999 il 16/11/2015, 17:08, modificato 1 volta in totale.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47

Re: [L05] Catene e anticatene

Messaggioda Delfad0r » 16/11/2015, 16:51

Direi che va tutto bene, e che non ti sei fatto trarre in inganno dal titolo fuorviante :mrgreen:

PS: hanno fatto un Codeforces e non ne sapevo nulla? Mannaggia a loro che non mandano le mail per i contest della Div2.
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19

Re: [L05] Catene e anticatene

Messaggioda cip999 » 16/11/2015, 17:09

Vabbè dai, ma si vede che quel coso non è un poset... E poi una meccanica applicazione di Dilworth sarebbe stata troppo palese anche per un Balkan.

Delfad0r ha scritto:PS: hanno fatto un Codeforces e non ne sapevo nulla? Mannaggia a loro che non mandano le mail per i contest della Div2.

Yep, ma credo non ci sia nulla di particolarmente interessante da fare in Haskell... :D
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 584
Iscritto il: 26/02/2014, 16:47


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti