Questo è tosto

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

Questo è tosto

Messaggioda Veritasium » 12/03/2016, 23:57

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.
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36

Re: Questo è tosto

Messaggioda Saro00 » 13/04/2016, 20:22

É arrivato il momento per chiedere un hint...
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi.
Saro00
 
Messaggi: 127
Iscritto il: 26/02/2015, 17:59
Località: Milano Periferia

Re: Questo è tosto

Messaggioda Veritasium » 13/04/2016, 20:49

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à?
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti