OliForum Matematico

Un $(n,k)$-torneo è un torneo con $n$ giocatori che si svolge in $k$ rounds tale che:

• In ogni round ogni giocatore gioca esattamente una volta e 2 giocatori si incontrano al massimo una volta
• Se i giocatori $A,B$ si incontrano nell'$i$-esimo round, i giocatori $C,D$ si incontrano nell'$i$-esimo round e i giocatori $A,C$ si incontrano nel $j$-esimo round allora anche i giocatori $B,D$ si incontrano nel $j$-esimo round

Trovare tutti gli $n,k$ tali che esista un $(n,k)$-torneo

IMO Shortlist 2006

p.s. questo è fighissimo (in effetti è molto più figo del combinatorico che hanno messo quell'anno nell'IMO... la difficoltà è circa la stessa mi pare, non capisco perchè non hanno piazzato questo )

E' possibile il torneo solo se $n\equiv 0 \mod 4$ e $n>k$

1) $n$ è pari altrimenti non posso accoppiare tutti i giocatori al primo round. Se $n \equiv 2 \mod 4$ al secondo round se si scontrano due giocatori allora si scontrano tra loro anche gli ex compagni (condizione 2).
Quindi ho sistemato 4 giocatori e il numero di giocatori rimasti rimane congruo modulo quattro. Ripetendo il ragionamento arrivo che rimangono 2 giocatori che si sono scontrati il turno precedente e quindi non possono giocare, assurdo.
Inoltre si giocano $\frac{n}{2}k$ incontri, e io posso scegliere al massimo $\binom{n}{2}$ coppi diverse di persone, quindi $\frac{nk}{2}\leq \binom{n}{2}$ da cui $n>k$

paga92aren ha scritto:E' possibile il torneo solo se $n\equiv 0 \mod 4$ e $n>k$

1) $n$ è pari altrimenti non posso accoppiare tutti i giocatori al primo round. Se $n \equiv 2 \mod 4$ al secondo round se si scontrano due giocatori allora si scontrano tra loro anche gli ex compagni (condizione 2).
Quindi ho sistemato 4 giocatori e il numero di giocatori rimasti rimane congruo modulo quattro. Ripetendo il ragionamento arrivo che rimangono 2 giocatori che si sono scontrati il turno precedente e quindi non possono giocare, assurdo.
Inoltre si giocano $\frac{n}{2}k$ incontri, e io posso scegliere al massimo $\binom{n}{2}$ coppi diverse di persone, quindi $\frac{nk}{2}\leq \binom{n}{2}$ da cui $n>k$

Sì giusto ma hai perso le soluzioni $k=1$ e n solo pari.
Ovviamente questa non è una soluzione completa (non lo dico a te, tu l'hai capito è chiaro ): è solo una condizione necessaria, ben lontana dall'essere sufficiente

p.s. esticazzi del millesimo messaggio figo... alla fine un enorme scritta mille basterà

1000esimo messaggio
1000esimo messaggio
1000esimo messaggio
1000esimo messaggio
1000esimo messaggio
1000esimo messaggio
1000esimo messaggio
1000esimo messaggio
1000esimo messaggio
1000esimo messaggio

(ne piazzo tante perchè non riesco a farla enorme come vorrei )

Faccio anch'io qualche considerazione:
1) se (n,k) va bene e h<h allora (n,h) va bene: basta sopprimere un po' di rounds;
2) (n,1) va sempre bene, quindi bisogna trovare per ogni n il massimo k;
3) se (n,k) va bene anche (mn,k) va bene: basta organizzare m tornei paralleli del tipo (n,k);
4) ($ 2^h, 2^h-1 $) va bene per ogni h intero positivo: associo ad ogni giocatore uno dei vettori a h componenti considerate modulo 2 (un elemento di $ \mathbb{F}_2^h $) e ad ogni round ancora uno di quei vettori, escluso il vettore nullo. Infine impongo che il giocatore cotrassegnato dal vettore A gioca con quello con il vettore B nel round con il vettore I se A+B=I, ovvero ogni round contiene le coppie di vettori che hanno somma il vettore del round. Per ogni quaterna A,B,C,D di vettori a h componenti modulo 2 si ha che A+B=C+D se e solo se A+C=B+D, perché A+A=0 sempre e per passare da un'equazione al'altr basta aggiungere B+C a entrambi i membri. Inoltre nessun giocatore gioca mai con se stesso perché nessun round è contrassegnato dal vettore nullo, né due giocatori giocano due volte tra loro o saltano un round, perché il giocatore A gioca con B solo al round A+B, e il giocatore A al round I gioca con A+I.

Mi sembra sensato congetturare che se $ n=2^hd $ con d dispari, allora $ k<2^h $, ma devo ancora pensarci.

La tua congettura mi sembra sbagliata, il torneo dovrebbe esistere per $k<n$ (con $n\equiv 0 \mod 4$).
Per una dimostrazione mi serve un po' di tempo...

Anér ha scritto:Faccio anch'io qualche considerazione:
1) se (n,k) va bene e h<h allora (n,h) va bene: basta sopprimere un po' di rounds;
2) (n,1) va sempre bene, quindi bisogna trovare per ogni n il massimo k;
3) se (n,k) va bene anche (mn,k) va bene: basta organizzare m tornei paralleli del tipo (n,k);
4) ($ 2^h, 2^h-1 $) va bene per ogni h intero positivo: associo ad ogni giocatore uno dei vettori a h componenti considerate modulo 2 (un elemento di $ \mathbb{F}_2^h $) e ad ogni round ancora uno di quei vettori, escluso il vettore nullo. Infine impongo che il giocatore cotrassegnato dal vettore A gioca con quello con il vettore B nel round con il vettore I se A+B=I, ovvero ogni round contiene le coppie di vettori che hanno somma il vettore del round. Per ogni quaterna A,B,C,D di vettori a h componenti modulo 2 si ha che A+B=C+D se e solo se A+C=B+D, perché A+A=0 sempre e per passare da un'equazione al'altr basta aggiungere B+C a entrambi i membri. Inoltre nessun giocatore gioca mai con se stesso perché nessun round è contrassegnato dal vettore nullo, né due giocatori giocano due volte tra loro o saltano un round, perché il giocatore A gioca con B solo al round A+B, e il giocatore A al round I gioca con A+I.

Mi sembra sensato congetturare che se $ n=2^hd $ con d dispari, allora $ k<2^h $, ma devo ancora pensarci.

Stai risolvendo il problema al contrario di come l'ho fatto io Tutto giusto tranne un piccolo errore quando dici (n,1) va sempre, questo è falso serve comunque n pari (come poi congetturi alla fine )

Diamo un ordine ai rounds: $ r_1,r_2,\cdots, r_k $. Se consideriamo il torneo formato non da tutti i rounds ma solo dai primi $ h $, alcune partite saranno state giocate e altre no. Posso allora definire $ G_h $ come il grafo che ha come vertici i giocatori e come archi le partite giocate in un round tra i primi h. Questo grafo $ G_h $ avrà come ogni grafo che si rispetti le sue componenti connesse. Dimostriamo allora che ogni componente connessa contiene un numero di vertici esprimibile come potenza di 2. Passo base: $ G_0 $ è il grafo senza collegamenti, per cui ogni componente connessa ha un solo vertice, e 1 è una potenza di 2. Passo induttivo da h a h+1: aggiungendo $ r_{h+1} $ chiaramente può capitare che alcune componenti di $ G_h $ si fondano, ovvero compaia un arco tra due componenti disgiunte di $ G_h $. Se una componente non si allarga allora la sua grandezza rimane uguale a prima, dunque ancora una potenza di 2; se invece esistono due componenti $ C_1,C_2 $ di $ G_h $ tali che in $ r_{h+1} $ c'è un arco che va da una all'altra, allora o $ r_{h+1} $ è una corrispondenza biunivoca per le due componenti, ovvero collega ogni giocatore di una componente con uno dell'altra, oppure no. Se sì abbiamo che senz'altro $ C_1,C_2 $ hanno la stessa cardinalità perché sono in corrispondenza biunivoca in $ G_{h+1} $, e in più poiché ogni giocatore del torneo acquista un solo arco in $ r_{h+1} $ non possono esserci archi da una delle due componenti al resto del mondo; dunque le due componenti si fondono e formano una nuova componente connessa di cardinalità doppia, e chiaramente il doppio di una potenza di 2 è una potenza di 2. Se invece esiste un giocatore di una delle due componenti, diciamo in $ C_1 $, che con $ r_{h+1} $ non acquista un collegamento verso $ C_2 $, allora possiamo dividere i giocatori di $ C_1 $ in due sottoinsiemi non vuoti contenenti i giocatori che con $ r_{h+1} $ vengono collegati con $ C_2 $ e quelli che acquistano un collegamento esterno a $ C_2 $. Poiché $ C_1 $ è connessa esistono due giocatori adiacenti in $ G_h $ che appartengono a sottoinsiemi diversi, diciamo $ A\in C_1 $ che è collegato a $ X\in C_2 $ in {tex}r_{h+1}[/tex] e $ B\in C_1 $ collegato con $ A $ in $ r_i $m per un certo i minore o uguale a h. Ma allora se chiamo $ Y $ l'amico di $ X $ in $ r_i $ ho che $ B,Y $ sono collegati in $ r_{h+1} $ per ipotesi, e chiaramente $ Y\in C_2 $, assurdo. A questo punto se prendo una componente connessa $ C $ di $ G_k $ so che $ |C|\geq| k+1 $ perché un vertice in C ha k collegamenti, dunque lui e i suoi k amici sono k+1 interni a C, e so anche che $ |C| $ è una potenza di 2, da cui è facile concludere che n, come somma di potenze di 2 maggiori o uguali a k+1 è divisibile per la più piccola potenza di 2 maggiore o uguale a k+1,
Spero che ci sia una soluzione più semplice!

Non l'ho letta con attenzione, ma l'idea è la stessa mia (e a occhio anche la dimostrazione) Cioè che le robe connesse hanno cardinalità una potenza di 2... e a dir la verità a me era parsa "naturale" come dimostrazione, quasi bella
Forse ti appare complicata perchè hai dovuto scrivere ciò che si sarebbe dovuto disegnare (insomma 2 o 3 disegnini e la dimostrazione mia si fa )