OliForum Matematico

(Own). Sia $ X:=\{x_1,x_2,\ldots,x_{29}\} $ un insieme di $ 29 $ ragazzi, che si sfidano ad un torneo di Pro Evolution Soccer 2009, rispettando le seguenti regole:

• i) ogni ragazzo gioca una e una sola volta contro tutti gli altri (possiamo quindi assumere che ogni partita ha la forma $ (x_i \text{ Vs } x_j) $ per qualche $ i \neq j $);
  ii) se la partita $ (x_i \text{ Vs } x_j) $, con $ i \neq j $, termina con la vittoria del ragazzo $ x_i $, allora quest’ultimo guadagna $ 1 $ punto, mentre l’altro non guadagna alcun punto;
  iii) se la partita $ (x_i \text{ Vs } x_j) $, con $ i \neq j $, termina con un pareggio allora viene assegnato $ \frac{1}{2} $ punto a ciascuno dei due ragazzi.

(Assumiamo per semplicità che se ha luogo la partita immaginaria $ (x_i \text{ Vs } x_i) $ allora questo ragazzo non guadagna alcun punto).
Mostrare che per qualche intero positivo $ k \le 29 $ esiste un insieme di ragazzi $ \{x_{t_1},x_{t_2},\ldots,x_{t_k}\} \subseteq X $ tali che, per ogni scelta dell’intero positivo $ i \le 29 $, il ragazzo $ x_i $ guadagna un numero intero di punti nel totale delle partite $ \{(x_i \text{ Vs } x_{t_1}),(x_i \text{ Vs } x_{t_2}),\ldots, (x_i \text{ Vs } x_{t_k})\} $.

Pronti? Fate un bel respiro

Definisco $ f(x_i,x_j)=1 $ se $ x_i Vs x_j $ è finita in parità, 0 altrimenti.
Allora, considero questa bella matrice:

$ $\left(\begin{array}{ccc} f(x_1,x_1) & \cdots & f(x_1,x_{29}) \\ \vdots & \ddots & \vdots\\ f(x_{29},x_1) & \cdots & f(x_{29},x_{29}) \end{array}\right) $

Ora, guardiamo il tutto modulo 2. La mia tesi è che sommando un po' di righe di questa matrice ne ottengo una formata solo da zeri, ossia che il determinante della matrice fa 0. E questo probabilmente viene per induzione (anche se io l'ho fatto in modo diverso).

Che schifo, eh?

io lo stavo cercando di fare con i grafi.. comunque sì, fa schifo...
l'idea di base però è sempre quella: far valere solo i pareggi e cercare di contarli...

TBPL ha scritto:Che schifo, eh?

Ci avevo pensato anch'io, ma la cosa difficile da sfruttare è che la matrice è simmetrica... A quando i dettagli?

Ok, ecco i dettagli:

Essendo modulo 2, ce ne possiamo fregare dei segni, quindi dico che il determinante vale $ \displaystyle{\sum_{\sigma\in S}{(\prod{f(x_i,\sigma(x_i))}} $, dove $ S $ è l'insieme di tutte le permutazioni di $ \{1,...,29\} $. Ora, il fatto che è simmetrica ci permette di accoppiarli, in quanto $ \prod{f(x_i,\sigma(x_i))}=\prod{f(\sigma(x_i),x_i)} $. Non posso farlo quando i due prodotti sono lo stesso termine della sommatoria di prima, ma allora vale $ (\sigma(\sigma(x_i)),\sigma(x_i))=(x_i,\sigma(x_i)) $, ossia $ \sigma $ ha ordine $ 2 $. Ma poiché $ 29 $ è dispari, $ \sigma $ ha almeno un punto fisso, quindi i prodotti che non posso accoppiare valgono $ 0 $ (perché hanno un fattore sulla diagonale).

TBPL ha scritto:E questo probabilmente viene per induzione (anche se io l'ho fatto in modo diverso).

Mi sembra difficile che venga per induzione: esiste una matrice 28x28 simmetrica e fatta di 0 e 1, con 0 sulla diagonale, che ha determinante 1.

EvaristeG ha scritto:

TBPL ha scritto:E questo probabilmente viene per induzione (anche se io l'ho fatto in modo diverso).

Mi sembra difficile che venga per induzione: esiste una matrice 28x28 simmetrica e fatta di 0 e 1, con 0 sulla diagonale, che ha determinante 1.

In effetti, ho detto abbastanza una cavolata, visto che uso che 29 è dispari
Comunque, forse ci si riesce passando da un dispari all'altro, anche se nel caso credo sia atroce

Ma non si potrebbe fare anche senza matrici? cioè siccome in ogni partita la somma dei punteggi è 1 allora la somma totale di tutti i punteggi è 29*14.
Essendo un numero intero allora gli 1/2 sono di numero pari.
Siccome i giocatori sono dispari (29) almeno un giocatore ha fatto un numero pari di pareggi, ha quindi totalizzato un numero intero.

...LAM... ha scritto:Ma non si potrebbe fare anche senza matrici? cioè siccome in ogni partita la somma dei punteggi è 1 allora la somma totale di tutti i punteggi è 29*14.
Essendo un numero intero allora gli 1/2 sono di numero pari.
Siccome i giocatori sono dispari (29) almeno un giocatore ha fatto un numero pari di pareggi, ha quindi totalizzato un numero intero.

jordan ha scritto:[...]
Mostrare che per qualche intero positivo $ k \le 29 $ esiste un insieme di ragazzi $ \{x_{t_1},x_{t_2},\ldots,x_{t_k}\} \subseteq X $ tali che, per ogni scelta dell’intero positivo $ i \le 29 $, il ragazzo $ x_i $ guadagna un numero intero di punti nel totale delle partite $ \{(x_i \text{ Vs } x_{t_1}),(x_i \text{ Vs } x_{t_2}),\ldots, (x_i \text{ Vs } x_{t_k})\} $.

Scusate... ma la soluzione olimpica dov'è?
Spero non fosse questa quella che gli autori si aspettavano :|