Questo è tosto

[Veritasium]

Sia [tex]A[/tex] un insieme di naturali (a due a due distinti). Diciamo che un sottoinsieme [tex]S[/tex] di [tex]A[/tex] è trascendente se, per ogni coppia [tex](x_i, x_j) \in S^2[/tex] di elementi distinti, [tex]x_i + x_j \notin A[/tex].

Dimostrare che, se [tex]|A| = 2^n \ \ (n > 0)[/tex] e [tex]B[/tex] è il sottoinsieme trascendente di [tex]A[/tex] con cardinalità massima, allora [tex]|B| > n[/tex].

Testo nascosto:

La fonte non è olimpica e quindi non ho modo di tarare con certezza il livello (non l'ho risolto, avendo letto subito la soluzione, ma mi pareva carino da postare qui), so solo che dovrebbe essere difficile, almeno [L06], credo.

[Saro00]

É arrivato il momento per chiedere un hint...

[Veritasium]

Hint 1 (giusto un accenno)

Testo nascosto:

Potrebbe essere un'idea iniziare a costruire un insieme trascendente. Per esempio, iniziando con l'inserirci il numero maggiore presente in [tex]A[/tex]

Hint 2 (avvio di soluzione):

Testo nascosto:

Seguendo il ragionamento dell'hint 1, possiamo costruire "ricorsivamente" un insieme trascendente, considerando sempre l'elemento maggiore ancora non considerato, e includendolo o escludendolo in base alla proprietà richiesta, ottenendo così un insieme di cardinalità [tex]c[/tex]. Ora, tenendo conto di questa costruzione, come possiamo esprimere ogni elemento di [tex]A[/tex] in funzione di quelli dell'insieme trascendente? Ciò cosa ci porta a dire sulla sua cardinalità?