Matrici stupende

[Leblanc]

Data una matrice $ n * n $, chiamiamo $ X_i $ l'insieme di tutti i valori presenti nell'i-esima riga; chiamiamo $ Y_j $ l'insieme di tutti i valori presenti nella j-esima colonna. Diciamo che una matrice e' 'stupenda' se gli insiemi $ X_1,X_2, ... X_n, Y_1, ... Y_n $ sono tutti distinti.
Trovare il minimo n per cui esiste una matrice 'stupenda' 2004x2004 contenente solo numeri appartenenti all'insieme $ \{1,2,...,n \} $.

[herbrand]

dato che non mi sembra nuovo puoi indicare da dove proviene (forse da qualche gara del 2004 ma quale?)

grazie

[Leblanc]

E' del TST tedesco dell'anno scorso...

[hydro]

Data una matrice $ n * n $, chiamiamo $ X_i $ l'insieme di tutti i valori presenti nell'i-esima riga; chiamiamo $ Y_j $ l'insieme di tutti i valori presenti nella j-esima colonna. Diciamo che una matrice e' 'stupenda' se gli insiemi $ X_1,X_2, ... X_n, Y_1, ... Y_n $ sono tutti distinti.
Trovare il minimo n per cui esiste una matrice 'stupenda' 2004x2004 contenente solo numeri appartenenti all'insieme $ \{1,2,...,n \} $.

cosa vuol dire insiemi distinti? vuol dire disgiunti?

[Leblanc]

Insiemi distinti significa che o hanno un numero diverso di elementi, oppure, se hanno lo stesso numero di elementi, c'e' almeno un elemento diverso. Insomma, in pratica distinti significa 'non uguali', mentre non significa necessariamente disgiunti.
Una precisazione che potrebbe non essere chiara dal testo: in una riga o colonna si puo' anche ripetere piu' volte uno stesso valore; in tal caso l'insieme corrispondente contiene una sola volta questo elemento. Ad esempio, se una riga e' formata dai numeri 1 1 2 3 5 3 l'insieme definito su quella riga e' {1, 2, 3, 5}, che e' considerato uguale all'insieme della riga 1 2 2 2 3 5.
Invece, gli insiemi corrispondenti alle ipotetiche righe 1 1 1 1 1 2 e 1 1 1 1 1 1 sono distinti, perche' nel primo c'e' anche il valore 2 che non e' presente nel secondo.

[Marco]

Ummmh... a questo problema ci avevo pensato un pochino prima di partire, e mi sembra che 13 fosse sufficiente, e senz'altro 12 necessario. Da li', confesso che mi sono un po' perso via.

Ad occhio scommetterei sul 13, ma e' abbastanza sottile...