Numeri uguali e distinti - SNS 1970

[elios]

"Fissato un intero positivo \( \displaystyle {n} \), determinare il più piccolo intero \( \displaystyle {m} \) tale che, presi comunque \( \displaystyle {m} \) interi, una almeno delle seguenti eventualità si verifichi:
a) tra gli \( \displaystyle {m} \) numeri considerati, ve ne sono \( \displaystyle {n} \) uguali;
b) tra gli \( \displaystyle {m} \) numeri considerati, ve ne sono \( \displaystyle {n} \) distinti."

Non mi è molto chiaro il testo. Presi \( \displaystyle {m} \) numeri, se \( \displaystyle {n} \) sono uguali, allora \( \displaystyle {m}-{n} \) sono distinti, oppure devo considerare anche i casi di più gruppi di numeri uguali? Grazie per l'aiuto dell'interpretazione del testo.

[WiZaRd]

Io lo vedo così.
Se prendo \( \displaystyle {n} \) allora devo prendere il più piccolo naturale \( \displaystyle {m} \) tale che in \( \displaystyle {m} \) numeri ce ne siano almeno \( \displaystyle {n} \) uguali o distinti, ma potrebbero essercene anche di più. Trattandosi però del più piccolo \( \displaystyle {m} \) si può ragionare direttamente sul caso di avere esattamente \( \displaystyle {n} \) elementi uguali o distinti.

[elios]

Intendi che \( \displaystyle {m} \) deve essere tale da ottenere solo \( \displaystyle {n} \) numeri uguali o distinti e non di più, giusto?
Non capisco come ottenere il caso che tu mi inviti ad analizzare: io ho \( \displaystyle {n} \) dato. E' chiaro che se potessi prendere \( \displaystyle {m} \) numeri uguali o distinti, mi basterebbe \( \displaystyle {m}={n} \), è solo che non posso farlo. Quindi non ho capito come mi consigli di ragionare..

[WiZaRd]

E perché mai non potresti farlo? Puoi, il punto è che non risolvi il problema.
Prendiamo \( \displaystyle {n}={3} \). Cerchiamo allora il più piccolo naturale \( \displaystyle {m} \) tale che comunque presi \( \displaystyle {m} \) numeri naturali, ce ne siano esattamente \( \displaystyle {n} \) uguali o distinti.
Se prendo \( \displaystyle {m}={3} \) e scelgo \( \displaystyle {12},{12},{12} \) allora sono a posto. Ma il problema è che per qualunque terna di naturali devo avere \( \displaystyle {3} \) numeri uguali o distinti, il che non è possibile. Se provi euristicamente noterai che per \( \displaystyle {n}={3} \) bisogna prendere \( \displaystyle {m}={5} \), il che dovrebbe suggerirti che il numero \( \displaystyle {m} \) è dato da...

[elios]

Il numero \( \displaystyle {m} \) per cui ancora non si realizzano le condizioni richieste è \( \displaystyle {m}={\left({n}-{1}\right)}+{\left({n}-{1}\right)} \) (è come se considerassi la prima parentesi come i numeri uguali e la seconda parentesi come numeri diversi, es: \( \displaystyle {n}={3} \), \( \displaystyle {m}={\left({3}-{1}\right)}+{\left({3}-{1}\right)}={4} \), che non va bene solo per il caso in cui ci siano \( \displaystyle {\left({3}-{1}\right)} \) numeri uguali e \( \displaystyle {\left({3}-{1}\right)} \) numeri diversi). Quindi aggiungendo 1 a questo numero (cioè aggiungendo un numero che sia o uguale ai precedenti o distinto da essi) ottengo l'\( \displaystyle {m} \) che cerco, cioé \( \displaystyle {m}={\left({n}-{1}\right)}+{\left({n}-{1}\right)}+{1}={2}{n}-{1} \).

Che ne dici?

[WiZaRd]

Che non funziona per \( \displaystyle {n}={4} \).
Indizio: \( \displaystyle {m}={{\left({n}-{1}\right)}}^{{2}}+{1} \).

[elios]

perché per \( \displaystyle {n}={4} \) non va bene \( \displaystyle {m}={7} \)? Il caso limite è con 3 diversi e 4 uguali, o 4 diversi e 3 uguali, la cui somma è 7.. Per me il minimo \( \displaystyle {m} \) è un numero dispari, la cui metà più un mezzo è uguale a \( \displaystyle {n} \)..

[ViciousGoblin]

perché per \( \displaystyle {n}={4} \) non va bene \( \displaystyle {m}={7} \)? Il caso limite è con 3 diversi e 4 uguali, o 4 diversi e 3 uguali, la cui somma è 7.. Per me il minimo \( \displaystyle {m} \) è un numero dispari, la cui metà più un mezzo è uguale a \( \displaystyle {n} \)..

perche' puoi prendere \( \displaystyle {1},{1},{1},{2},{2},{2},{3},{3},{3} \) che in tutto sono 9 numeri tra cui non ce ne sono ne' quattro eguali ne' quattro diversi.

[elios]

Ho capito.. Quindi il più piccolo \( \displaystyle {m} \) per cui non valgono ancora le condizioni richieste è quel \( \displaystyle {m} \) con cui si possono creare \( \displaystyle {\left({n}-{1}\right)} \) gruppi di \( \displaystyle {\left({n}-{1}\right)} \) numeri uguali (perché in questo caso troveremmo al massimo \( \displaystyle {n}-{1} \) numeri uguali e al massimo \( \displaystyle {n}-{1} \) numeri distinti), cioé \( \displaystyle {m}={{\left({n}-{1}\right)}}^{{2}} \). Quindi il minimo \( \displaystyle {m} \) con le condizioni richieste è \( \displaystyle {m}={{\left({n}-{1}\right)}}^{{2}}+{1} \)
Giusto?
Grazie infinite.

[WiZaRd]

Esattamente.