Quanti senatori

[mat94]

Tutti i membri del senato si suddividono in S gruppi, di cui ciascun gruppo ha almeno 5 elementi e il numero di senatori di ciascun gruppo sono diversi. Ad un certo punto i gruppi vengono chiusi e se ne aprono di nuovi. Si sa che due senatori che erano nello stesso gruppo in precedenza non possono stare insieme, che le regole di formazione dei gruppi sono le stesse e che alcuni senatori possono rimanere fuori da ogni gruppo. Trovare il minimo numero di senatori esclusi e dimostrare che tale minimo può essere raggiunto.

[Gottinger95]

...che le regole di formazione dei gruppi sono le stesse...

Intendi che i senatori in ogni gruppo devono essere almeno 5 o che i gruppi sono \(S\)? Immagino e perciò suppongo la prima.
Detti \(N_1\) il numero di senatori totali nei gruppi iniziali e \(N_2\) il numero di senatori totali nei gruppi finali, otteniamo \(min(N_1 - N_2)\) in corrispondenza di \(max(N_2)\) e \(min(N_1)\).

MINIMIZZAZIONE:
Il gruppo con meno elementi ne ha almeno 5. Visto che i gruppi hanno numero di senatori diversi, gli altri gruppi avranno almeno cardinalità \(6,7, \ldots, S+4\).
Perciò il minimo di \(N_1\) risulta \(N_1 = T_{S+4} - T_{4} = (S+4)(S+5)/2 - (4)(5)/2 = (S^2 + 9S)/2\).

MASSIMIZZAZIONE:
Il gruppo finale con più senatori può avere al massimo \(S\) senatori , prendendone uno da ogni gruppo. Visto che ogni gruppo ha cardinalità diverse e che il minimo di cardinalità è 5, i gruppi possono essere al massimo \(S-4\), assumendo che il gruppo \(G_i\) abbia cardinalità \(|G_i| = i+4\) per \(i=1, \ldots, S-4\).
E' costruibile in questo modo: il gruppo \(G_i\) attinge i suoi senatori dai primi \(|G_i|\) gruppi iniziali, iniziando ad attingere dal più grande. Così facendo al gruppo più grande verranno chiesti \(S-4\) senatori, al secondo gruppo più grande \(S-3\), e tutti riescono a dare ciò che gli viene chiesto.

EDIT: mi spiego meglio. In pratica il gruppo più grande finale, che è quello più affamato, chiede un senatore a tutti i gruppi; il secondo, chiede un senatore a tutti i gruppi tranne che a quello con meno senatori; il terzo chiede a un senatore a tutti i gruppi tranne ai due con meno senatori; eccetera eccetera. La disuguaglianza sotto dimostra che è possibile farlo.

In simboli, chiamando \(H_i\) i gruppi iniziali e notando che vale ugualmente \(|H_i| = i+4\), dobbiamo verificare che \(|H_{S-i}| \geq |G_{S-4-i}|\), ossia \(S-i \geq S-4-i\), evidentemente vera.
Perciò il massimo di \(N_2\) risulta \(N_2 = T_{S} - T_4 = S(S+1)/2 - (4)(5)/2 = (S^2 +S - 20)/2\)

RISULTATO:
Si ha dunque \(min(N_1 - N_2) = (S^2 + 9S)/2 - (S^2 +S - 20)/2 = 4S+10)\).

[mat94]

C'è un errore di calcolo nella minimizzazione che è 9S e non 11S, quindi alla fine ti viene 4S+10 non ho capito bene la costruzione dei gruppi