Un insieme di 5 numeri interi positivi

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
Info
Livello 5
Livello 5
Messaggi: 377
Iscritto il: lun nov 21, 2005 1:11 pm
Contatta:

Un insieme di 5 numeri interi positivi

Messaggio da Info »

Ciao, provo a mettere mano al problema proposto sulla bacheca

il fatto di avere 5 numeri grandi quanto si vuole e volendone verificare la divisibilita`per 5 si ragiona in termini di resto della divisione.

prendendo di ciascuno il resto della divisione per 5 mi ritrovo a ragionare con 5 numeri che vanno da 0 a 4.
Il problema si riduce dimostrare che posso sommare 5 numeri in modo di arrivare comunque ad un risultato di 5 o un suo multiplo (che equivale a 0 visto che sto ragionando con i resti)

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Un insieme di 5 numeri interi positivi

Messaggio da Gianfranco »

Grazie Info, ricopio qui il testo del problema:

Scegliete in modo del tutto casuale 5 numeri interi positivi. Non ci sono limiti alla grandezza dei numeri. Sono ammesse ripetizioni.
Dimostrate che in questo insieme di 5 numeri, comunque siano stati scelti, ce ne sono sicuramente alcuni (da 1 a 5) la cui somma è divisibile per 5.
Note.
  • Se vi sembra troppo difficile, provate con un insieme più piccolo, per esempio di 3 numeri, fra i quali ce ne sono sicuramente alcuni la cui somma è divisibile per 3.
  • Se invece vi sembra troppo facile, provate a generalizzarlo a n numeri, fra i quali ce ne sono sicuramente alcuni (da 1 a n) la cui somma è divisibile per n.
---
Direi che la tua impostazione è corretta.
Manca per ora il passaggio decisivo.
Pace e bene a tutti.
Gianfranco

Info
Livello 5
Livello 5
Messaggi: 377
Iscritto il: lun nov 21, 2005 1:11 pm
Contatta:

Re: Un insieme di 5 numeri interi positivi

Messaggio da Info »

ciao Gianfranco.... ho provato a proseguire ma non avendo concluso nulla ho postato solo la prima parte.

Certo non bisogna analizzare tutti i casi... ci vuole un ragionamento che si possa generalizzare per qualsiasi n... promesso che nel weekend ci penso (((-;

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Un insieme di 5 numeri interi positivi

Messaggio da gnugnu »

Siano $x_i$ con $i\in[1..n]$ gli n numeri naturali; posto:
$s_0=0; s_i=s_{i-1}+x_i$ (mod n) per $i\in[1..n]$,
il principio dei cassetti permette di dimostrare (almeno due s devono coincidere) l'esistenza di un sottoinsieme non vuoto di x con somma multipla di n.
In una vecchia discussione di questo forum (non conosco bene le consuetudini e nel caso questa parte fosse ritenuta OT chiedo scusa) veniva dimostrato che in un insieme di 17 numeri naturali ne esistono sicuramente 5 la cui somma è multipla di 5.
A mio avviso la dimostrazione è corretta, ma 17 è un po' grande: ne bastano molti meno.

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Un insieme di 5 numeri interi positivi

Messaggio da Gianfranco »

Dimostrazione (quasi) perfetta gnugnu anche se estremamente telegrafica.
Dico -quasi- perché secondo me manca il passaggio finale che forse hai dato per scontato.

Hai scritto:
il principio dei cassetti permette di dimostrare (almeno due s devono coincidere) l'esistenza di un sottoinsieme non vuoto di x con somma multipla di n.
Chiamiamo le due somme (non in modulo n): $s_h$ e $s_k$ con $s_h>s_k$.

OK, visto che $s_h=s_k (\text{MOD } n)$ allora la loro differenza è 0 perciò la differenza $s_h-s_k$ è divisibile per $n$
Ma $s_h-s_k$, per come sono state scelte le varie $s_i$ è a sua volta una delle possibili somme di alcuni degli $n$ numeri dati.

Hai scritto:
In una vecchia discussione di questo forum (non conosco bene le consuetudini e nel caso questa parte fosse ritenuta OT chiedo scusa) veniva dimostrato che...
Effettivamente si è parlato di questo problema (o simili) in altre discussioni. Ormai il Forum è talmente grande che a volte dimentichiamo qualcosa.
In particolare in questa pagina:
https://www.base5forum.it/esercizi-sul-p ... -t841.html
Pietro Vitelli aveva già dimostrato il problema nel caso di n=5
Pace e bene a tutti.
Gianfranco

gnugnu
Livello 4
Livello 4
Messaggi: 147
Iscritto il: dom set 07, 2014 2:00 pm

Re: Un insieme di 5 numeri interi positivi

Messaggio da gnugnu »

Hai ragione Gianfranco: la mia era solo una sommaria traccia della soluzione generale (non volevo interferire più di tanto con i ragionamenti di Info, che aveva scritto di voler utilizzare il fine settimana per approfondire la questione).
Mi sono posto la domanda: l'insieme individuato con il metodo dei cassetti è unico?
Credo si possa dimostrare che la soluzione è unica solo in due casi facilmente individuabili:
a) gli n numeri appartengono alla medesima classe di resto (diversa da 0 e dagli eventuali divisori dello 0);
b) un numero appartiene alla classe 0 ed i restanti n-1 come sopra.

Per quanto riguarda il problema dei 17 numeri da cui estrarne 5 la cui somma sia divisibile per 5, ho trovato la sua soluzione (vecchia di nove anni, il problema è il n. 9 della sezione che hai linkato) proposta dall'amministratore (suppongo sia Pietro Vitelli) ed ho scritto la mia osservazione, che potrebbe intendersi come un nuovo problema.

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Un insieme di 5 numeri interi positivi

Messaggio da Gianfranco »

Rispondo telegrafico e senza garanzie perché mi cala la palpebra.
gnugnu, hai scritto:
l'insieme individuato con il metodo dei cassetti è unico?
In questo particolare problema si mostra come costruire una soluzione ma non è detto che sia l'unica (anche limitandosi alle poche somme considerate), infatti potrebbero esserci più di due somme divisibili per n.

La dimostrazione dimostra qualcosa di "più potente" di quanto richiesto dal problema e cioè che:
Una qualunque permutazione (sequenza ordinata) di n numeri contiene almeno una sottosequenza di termini consecutivi la cui somma è divisibile per n.

E' un esempio di come nel caos ci sia mooolto più ordine di quanto si possa immaginare.
Pace e bene a tutti.
Gianfranco

Rispondi