Posso sempre fare un numero intero di punti, problema 5

[jordan]

(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})\} $.

[TBPL]

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?

[exodd]

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...

[jordan]

Che schifo, eh?

[kn]

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

[TBPL]

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).

[EvaristeG]

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.

[TBPL]

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

[...LAM...]

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.

[TBPL]

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.

[...]
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})\} $.

[dario2994]

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