OliForum Matematico

Un bel problema, definibile classico nella combinatoria olimpica

Il parlamento italiano ha $ $n $ senatori. I senatori formano 100 partiti e 100 comitati. Ogni senatore appartiene ad un solo partito e fa parte di un solo comitato.
Trovare il minimo $ $n $ per cui sia sempre possibile numerare i partiti da 1 a 100 e i comitati da 1 a 100 in modo che ci siano almeno 101 senatori per i quali il numero del partito e del comitato corrispondente sono uguali.

p.s. POTD 5/3/2010 http://www.mathlinks.ro/viewtopic.php?t=53281

a primo impatto direi che è da piccioni come risoluzione... e abbozzerei un N=10001

avevo pensato ad una scacchiera (partiti;comitati) 100 x 100 con righe e colonne numerate e N=somma dei senatori sulla diagonale. Posso sistemare i primi 10000 uno in ogni casella ma il 10001° (considerando il fatto che posso scambiare tra loro le varie righe o colonne) andrà sulla diagonale -> N=101

manca tutta una serie di casistica che visto la mia incapacità a scrivere le dimostrazioni vi risparmio... aspetto correzioni

Per quanto mi risulta quello che hai scritto non vuol dir nulla... se ritieni sia giusta (non ne sono convinto) scrivila decentemente.

p.s. sei o eri del righi???

ci sono 100 comitati e 100 partiti: questo significa che in ogni comitato ci sta almeno un partito rappresentato. Il problema diventa quindi trovare un comitato in cui ci siano almeno 2 persone dello stesso partito. La condizione peggiore si ha quando in ogni comitato è presente ogni partito una e una sola volta. ovvero 100 x 100 = 10000. Basta quindi aggiungere 1 senatore di qualsiasi partito in qualsiasi dei comitati per raggiungere il risultato desiderato. Quindi N = 10001

karotto ha scritto:ci sono 100 comitati e 100 partiti: questo significa che in ogni comitato ci sta almeno un partito rappresentato. Il problema diventa quindi trovare un comitato in cui ci siano almeno 2 persone dello stesso partito. La condizione peggiore si ha quando in ogni comitato è presente ogni partito una e una sola volta. ovvero 100 x 100 = 10000. Basta quindi aggiungere 1 senatore di qualsiasi partito in qualsiasi dei comitati per raggiungere il risultato desiderato. Quindi N = 10001

era questo il ragionamento solo che direi che si nota che non sono capace a riformularlo in maniera decente

si comunque ero del righi

Si, peccato che quella roba abbia valenza matematica rasente lo 0. Non voglio essere pedante però quella non è una dimostrazione, è una speranza che sia davvero così... chi vi dice che il caso peggiore è proprio quello che dite voi??? Magari lo è (magari no...) ma è da dimostrare.
Non è un esercizio tostissimo ma per essere nel TST Rumeno forse forse potrebbe non essere banale :|

ne ero pienamente consapevole... era solo un dire la prima idea aspettando una vera soluzione

Risposta: n=10001.
Lemma 1: In una scacchiera di mxm si può fare una partizione in m sottoinsiemi (considerando come elementi le caselle), tale che ogni sottoinsieme ha esattamente m caselle e se le caselle A e B appartengono allo stesso sottoinsieme allora A e B si trovano su diverse colone e diverse righe.
Per dimostrare questo lemma è sufficiente numerare le caselle così: nella riga_j si mettono consecutivamente i numeri dal 1 al m iniziando per il numero j (il numero m e il 1 si dicono consecutivi), poi si fa la partizione mettendo nello stesso sottoinsieme le caselle con lo stesso numero, ed è chiaro che questa partizione soddisfa le condizione dette.

Dopo, come ha detto cromat prendiamo la scacchiera (partiti ; comitati), in ciascuna delle caselle le qualli sono della forma (partito i; comitati j) mettiamo il numero k, dove k sarà il numero di senatori che appartengono al “partito i” e al “comitato j” entrambi. Allora la somma dei numeri nelle caselle sarà n (numero di senatori). Adesso facciamo una partizione delle caselle in 100 sottoinsiemi con le condizioni del Lemma 1, sia S_j la soma dei numeri nelle caselle appartenenti al sottoinsieme j, la somma dei S_j (j=1,2…100) sarà =n=10001, siccome ci sono 100 sottoinsiemi, per piccionaie esiste un sottoinsieme X con soma 101, e con questo abbiamo finito poiché in questo sottoinsieme non ci sono due caselle sulla stessa colona o sulla stessa riga, allora si possono numerare i partiti e i comitati in maniera tale che se un comitato e un partito hanno numeri corrispondenti allora la casella ripresentata per quella copia apartene a X, di dove al meno 101 senatori appartengono a un partito e comitato con lo stesso numero.
Per dimostrare che n è il minimo manca costruire un caso in cui n=10000 e non si soddisfano le condizioni del problema, ma questo è banale.

Bueno
Piazzo la mia perchè è differente. Anche io parto dalla disposizione a griglia in ogni quadratino piazzo il numero di senatori in quel partito e comitato.
Chiamo una colorazione pulita una colorazione tale che sono colorate 100 caselle tutte su righe e caselle diverse. Ad ogni colorazione pulita associo la sua potenza: la somma delle caselle colorate. La somma di tutte le potenze associate alle colorazioni pulite è: $ $n\cdot99! $ poichè ogni casella è presente esattamente in n-1! colorazioni pulite. Inoltre le colorazioni pulite sono $ $100! $
Chiamo M la media della potenza delle colorazioni pulite; perciò vale (sfruttando n=10001):
$ $ M=\frac{n\cdot 99!}{100!}=\frac{n}{100}=\frac{10001}{100}>100 $
Dato che la media è maggiore di 100 almeno una colorazione pulita lo è quindi quella colorazione soddisfa le richieste
Per il 10000 basta piazzare in ogni casella un 1.