Somme multiple

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
sprmnt21
Messaggi: 559
Iscritto il: 01 gen 1970, 01:00

Messaggio da sprmnt21 »

Ho trovato, su Internet, proposto il seguente problema (non molto difficile):
<BR>
<BR>1) Comunque dati 17 numeri naturali, provare che se ne possono sempre trovare 5 la cui somma e\' multipla di 5.
<BR>
<BR>In aggiunta ne propongo altri:
<BR>
<BR>2) Comunque dati 3 numeri naturali, provare che se ne possono sempre trovare 2 la cui somma e\' multipla di 2.
<BR>
<BR>
<BR>3) Comunque dati 5 numeri naturali, provare che se ne possono sempre trovare 3 la cui somma e\' multipla di 3.
<BR>
<BR>
<BR>A questo punto non resta che spiccare il salto e provare che:
<BR>
<BR>n) Comunque dati 2n-1 numeri naturali, se ne possono sempre trovare n la cui somma e\' multipla di n.
<BR>
<BR>
<BR>
<BR>
<BR>
<BR>PS
<BR>Al momento il problema n, per me, e\' una congettura (che renderebbe il problema 1 un semplice sotto-corollario di un sottocaso particolare). Ma \"sento\" fortemente che e\' buona.
Kornholio
Messaggi: 49
Iscritto il: 01 gen 1970, 01:00
Località: ~Chieti
Contatta:

Messaggio da Kornholio »

<pre>
<BR>Nel caso dei 17 numeri
<BR>----------------------
<BR>Ogni numero (mod 5) può essere uguale a
<BR>0,1,2,3,4
<BR>
<BR>-------------------
<BR>| 0 | 1 | 2 | 3 | 4 |
<BR>-------------------
<BR>| | | | | | caselle A0-A1-A2-A3-A4
<BR>-------------------
<BR>
<BR>se il primo numero è congruo a 1 mod 5
<BR>mettiamo un puntino sotto la casella \"1\"
<BR>se il secondo numero è congruo a 4 mod 5
<BR>mettiamo un puntino sotto la casella \"4\"
<BR>e così via...
<BR>
<BR>Se le caselle A0-A1-A2-A3-A4 contengono
<BR>almeno un puntino ciascuna il problema è
<BR>immediatamente risolto
<BR>(infatti 0+1+2+3+4 congruo a 0 mod 5)
<BR>
<BR>Mettiamoci quindi nelle peggiori condizioni e
<BR>imponiamo che almeno una delle caselle
<BR>A0-A1-A2-A3-A4 sia vuota. Ci saranno quindi
<BR>17 puntini in 4 caselle, e per il teorema dei
<BR>cassetti almeno una delle celle
<BR>A0-A1-A2-A3-A4 conterrà 5 elementi.
<BR>
<BR>Ma 5*a congruo a 0 mod 5, quindi il problema
<BR>sarà immediatamente risolto anche in questo
<BR>caso.
<BR>--------------------------------------------
<BR></pre>
<BR>
<BR>
<BR>
<BR>
Lex maxima : se qualcosa può andar male, prima o poi lo farà
CassanodiGaeta2000
Messaggi: 35
Iscritto il: 01 gen 1970, 01:00
Località: Bari

Messaggio da CassanodiGaeta2000 »

I casi rimanenti sono il b), c) ed n).
<BR>Ecco le mie soluzioni:
<BR>b) Per il teorema dei cassetti, su 3 numeri 2 hanno la stessa parità, per cui sommati danno un numero divisibile per 2.
<BR>c) Tutti gli n possono essere del tipo 3n, o 3n+1, o 3n+2. Analogamente alla dimostrazione di Crini creo le caselle A0 A1 ed A2 e seguendo la stessa dimostrazione dimostro la tesi.
<BR>n) La tua tesi secondo la quale dati 2n-1 naturali ne esistono n che sommati diano un numero divisibile per n, a mio parere è errata (non a caso, nel punto a )dovremmo avere 2*5-1=9 numeri e non 17).
<BR>Ti propongo la mia soluzione: se n è pari, sono necessari n(n-1)+1 naturali per poter trovare n naturali che sommati diano un naturale divisibile per n. Se è dispari ne occorrono invece (n-1)(n-1)+1. La dimostrazione è molto lunga ma i passaggi sono elementari:
<BR>Osservo che se sommo i primi n-1 naturali avrò n(n-1)/2. voglio capire se questa somma sia divisibile per n quindi divido per n ed ottengo (n-1)/2. Quindi se n è pari ottengo una frazione, dunque non è divisibile; se è dispari ottengo un naturale per cui la somma dei primi n-1 naturali è divisibile per n con n dispari, non lo è per n pari.
<BR>Usando le caselle A0, A1,…,An-1 (come nella dimostrazione precedente) osservo che con n dispari, avendo (n-1)(n-1)+1 naturali questi o saranno disposti in tutte le n caselle oppure no . Nel primo caso sommando i resti di un numero per ogni casella nella divisione per n avrò 0+1+2+…+n-1 ossia n(n-1)/2 che è divisibile per n. Quindi sommando un numero per casella avrò un numero del tipo kn+n(n-1)/2 ossia
<BR>n(k+(n-1)/2 ) che è divisibile per n. Se non vengono riempite tutte le caselle per il principio dei cassetti esisterà almeno una casella con n elementi o più. Sommandone n si ottiene ovviamente un numero divisibile per n. Nel caso di n pari la somma di un elemento per casella è kn+n(n-1)/2 e poiché il secondo addendo per dimostrazione precedente non è divisibile per n, non lo è neanche la somma. Per cui l’ unico modo per avere n naturali la cui somma sia divisibile per n è avere n numeri nella stessa casella. Per il teorema dei cassetti il minimo che soddisfi questa tesi è per l’appunto (n-1)(n-1)+1 per cui la tesi è dimostrata. E’ possibile che si possa trovare una somma divisibile per n non solo sommando un elemento a insieme o avendo n elementi della stessa casella, ma prendendo alcuni elementi da una casella altri da un’ altra…, ma lo ritengo estremamente improbabile (si provi con un semplice numero come 3…), per cui sono abbastanza sicuro del risultato, invito comunque tutti a cercare una dimostrazione che sostenga o confuti questa tesi.
<BR>Spero di essere stato chiaro
<BR> Cassano di Gaeta
<BR>
Bloccato