USAMO $1989$, Problema $2$

Aug 17 2020

Problema $2$ da USAMO, $1989$: Il $20$ i membri di un club di tennis locale hanno programmato esattamente $14$giochi per due persone tra di loro, con ogni membro che gioca almeno una partita. Dimostra che all'interno di questo programma deve esserci un set di sei partite con$12$ giocatori distinti.

Il mio tentativo di una soluzione: poiché ci sono$20$ giocatori, ognuno dei quali ha giocato almeno una partita, il minor numero di partite che deve essere organizzato per accogliere tutti i giocatori sarebbe $10$. Adesso,$4$restano più partite, che possono essere giocate al massimo $8$ di questi $20$Giocatori. Così, almeno $12$ dei giocatori possono giocare non più di $1$match, e quindi deve esistere un set di sei partite con$12$giocatori distinti . Questo, credo, sarà il principio guida di una prova rigorosa.

Ho i seguenti dubbi che mi offuscano la mente:

  1. Il mio ragionamento è valido, cioè privo di insidie?
  2. Se corretto, come inquadrare il ragionamento di cui sopra in una dimostrazione matematicamente rigorosa?

Modifica: come sottolineato da Ben nei commenti, l'affermazione in corsivo è ingiustificata. Ho trascurato molte possibilità mentre inquadravo questa prova, a quanto pare. Pertanto, vorrei ricevere alcuni suggerimenti per procedere con prove più ragionevoli.

Risposte

2 cgss Aug 17 2020 at 12:31

Temo che ci sia una trappola. Se provi a dimostrare che ci sono 6 partite con 12 giocatori distinti tra quelli che hanno giocato esattamente 1 partita, fallirai. Ecco un esempio:

$$ 1-2\\ 3-4\\ 5-6\\ 7-8\\ 9-10\\ 11-12\\ 12-13 \\ 13-14\\ 14-15\\ 15-16\\ 16-17\\ 17-18\\ 18-19\\ 19-20$$

Sebbene ci siano 6 partite con 12 giocatori distinti, solo 5 partite sono tra i giocatori con esattamente una partita.

Quindi ecco un suggerimento: dividi i giocatori in due gruppi, quelli con una partita e quelli con più. Quindi abbina i giocatori con una partita, dopo abbina i giocatori con una partita con i giocatori con più e infine i giocatori con più giochi.

EDIT : secondo approccio

Se ogni persona è vista come un vertice e ogni gioco come un bordo, la domanda chiede di dimostrare che esiste almeno una corrispondenza di dimensione $6$. In modo equivalente, possiamo dimostrare che la dimensione della corrispondenza massima$MM$ è di dimensioni almeno $6$. Si noti che un massimo di corrispondenza divide i vertici in due insiemi, uno con i bordi in$MM$, di dimensioni $2\cdot |MM|$, e uno senza, di dimensioni $20 - 2\cdot |MM|$per il nostro problema. Poiché tutti i vertici sono almeno di grado$1$, concludiamo che ci sono almeno $20 - 2\cdot |MM|$bordi tra le due partizioni. Adesso,

$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$