Una terna ancora!

[enomis_costa88]

L'insieme X ha n elementi.
Scelgo n+1 terne distinte di elementi da X.
Dimostrare che ho scelto due terne con un solo elemento in comune.

Buon lavoro (e provate ad indovinare la fonte..)!

[pi_greco_quadro]

Osserviamo innanzitutto che perché il problema abbia senso |X|>4 altrimenti non potremmo scegliere n+1 terne distinte. A questo punto però mi accorgo che con 4 elementi posso costruire esattamente 4 terne che rispettino le richieste del problema (es ABC BCD ABD ACD). A questo punto mi accorgo che non riesco a migliorare il numero di possibilità che ho trovato con quattro elementi a meno che non abbia a disposizione altri 4 elementi distinti con cui rifare il "giochetto", ovviamente con terne che non avranno in comune con le prime alcun elemento. Detto questo posso affermare che il numero max di terne che riesco a costruire senza che ve ne siano due con in omune uno ed un solo elemento è [n/4]*4<=n. Quindi per il pigeonhole se ne scelgo n+1 ne avrò sicuramente due con un solo elemento in comune.

[edriv]

Sì è giusta, ma a me non pare sia una dimostrazione... in particolare quel "mi accorgo" mi sa che andrebbe spiegato.

Ciao - Andrea

[Salva]

A me non sembra giustissima. ABC BCD ABD ACD hanno tutte DUE elementi in comune... ed anche l'applicazione finale del pigeonhole ti garantisce solo che esistono terne con elementi in comune, ma non specifica se uno o due.

[pi_greco_quadro]

@edriv: giustissimo quello che dici..

@salva: appunto. L'idea è proprio quella di cercare quante sono al massimo le terne che hanno esattamente o nessuno oppure due elementi in comune. Questo perché una volta detto che al max sono n, allora per il pigeonhole la n+1-esima che mi scelgo per forza avrà in comune con una di quelle già precedentemente trovate uno ed uno solo elemento in comune no? quindi non capisco l'obiezione

[edriv]

Vabeh, scrivo la mia dimostrazione, che è probabile sia quello che intendeva $ ~ \pi^2 $.

Supponiamo di avere un insieme di terne, a due a due disgiunte o con esattamente 2 elementi in comune.
Nell'insieme delle terne, dimostro che la relazione "A non è disgiunta da B" è di equivalenza:
- un insieme ovviamente non è disgiunto da se stesso (a meno che non sia vuoto, vabeh, ma certo questo non è il caso)
- se A non è disgiunto da B, ovviamente B non è disgiunto da A
- se A ha due elementi in comune con B e B ha due elementi in comune con C, per il pigeonhole c'è un elemento che appartiene sia ad A sia a C, quindi A ha elementi in comune con C.

Verificato questo, possiamo partizionare l'insieme delle terne in insiemi in cui, a due a due, le terne hanno esattamente 2 elementi in comune (se sono distinte, ovviamente).

A questo punto si comincia un po' a smanettare.
E si vede facilmente che, se in un insieme le terne hanno intersezione 2, o si raggiunge la configurazione ABC BCD ABD ACD, oppure non si supera le 4 terne.

Concludendo questo, gli insiemi della partizione sono così fatti:
- 4 terne e 4 elementi
- 1 terna e 3 elementi
- oppure, con un po' di spreco, 4 elementi e 2,3 terne.

Sommando tutto (le terne in elementi diversi della partizione sono disgiunti), si vede che la disuguaglianza è vera, e anche che è stretta se e soltanto se n è un multiplo di 4.

[edriv]

Mi correggo; i vari insiemi in cui ho partizionato le terne possono essere di un altro tipo:
- tutte le terne con 2 elementi in comune e il terzo elemento che le distingue
Ma in questo caso la disuguaglianza non è stretta, quindi la conclusione va bene.

[rand]

Non vi annoierò con un'altra domanda impossibile... ma con una soluzione algebrica di questo problema così maltrattato .
Ammettiamo per assurdo che ogni coppia di triple sia disgiunta o abbia due elementi nell'intersezione.
Numeriamo gli n elementi e le n+1 triple e costruiamo una matrice X di dimensioni n x n+1 tale che $ X_{i,j} $ è 1 se l'elemento i-esimo sta nella tripla j-esima o 0 altrimenti. Allora la matrice $ A = X^{T}X $ ha dimensioni n+1 x n +1 e ci si accorge subito che $ A_{i,j} $ è uguale proprio alla cardinalità dell'intersezione tra le triple i e j. Ora A ha rango al più n quindi $ det(A) = 0 $. Tuttavia per ipotesi A ha tutti 3 nella diagonale principale e 0 o 2 altrove, questo vuol dire che il determinante è del tipo $ 3^{n+1} + M $ dove M è pari, dunque non può essere zero. Assurdo. Come questo messaggio.