Senatori divisi in partiti e comitati (Rom TST 2003 ex 13)

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Senatori divisi in partiti e comitati (Rom TST 2003 ex 13)

Messaggio da dario2994 » 05 mar 2010, 21:14

Un bel problema, definibile classico nella combinatoria olimpica 8)

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
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

cromat
Messaggi: 70
Iscritto il: 24 feb 2007, 22:32
Località: roma

Messaggio da cromat » 05 mar 2010, 22:26

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

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 05 mar 2010, 22:40

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???
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

karotto
Messaggi: 357
Iscritto il: 01 gen 1970, 01:00

Messaggio da karotto » 06 mar 2010, 16:38

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

cromat
Messaggi: 70
Iscritto il: 24 feb 2007, 22:32
Località: roma

Messaggio da cromat » 06 mar 2010, 17:13

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 :wink:

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 06 mar 2010, 21:02

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 :|
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

cromat
Messaggi: 70
Iscritto il: 24 feb 2007, 22:32
Località: roma

Messaggio da cromat » 06 mar 2010, 21:05

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

Tin-Tan
Messaggi: 24
Iscritto il: 06 mar 2010, 18:06
Località: Torino
Contatta:

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.

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 07 mar 2010, 14:27

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.
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai

Rispondi