Messaggio
da Tin-Tan » 07 mar 2010, 13:28
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.
Genio es aquel que no se limita a la escasa percepción de sus sentidos para describir el universo que lo rodea.
