Somma multipla di 5 - ridurre il limite

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
Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1716
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Somma multipla di 5 - ridurre il limite

Messaggio da Gianfranco »

Pietro ha risolto il seguente problema:
Somma multipla di 5
In un qualunque gruppo di 17 numeri naturali se ne trovano 5 la cui somma è divisibile per 5.
Per la soluzione vedi: https://www.base5forum.it/post22301.html#p22301
Secondo gnugnu, il limite di 17 numeri è, però, troppo ampio.
Per essere certi che esista un sottoinsiema di 5 numeri aventi somma multipla di 5 bastano un gruppo di "candidati" più piccolo di quello proposto.
Proviamo a ridurre questo limite?
Riformulo il problema in termini più ricreativi (o forse solo da rompicapo combinatorio?)
Trascrivo la lista di tutte le possibili cinquine NON ordinate di numeri naturali la cui somma è divisibile per 5.
Naturlmente intendo le classi modulo 5, perciò i numeri scritti sono compresi fra 0 e 4.

01) 0 0 0 0 0
02) 0 0 0 1 4
03) 0 0 0 2 3
04) 0 0 1 1 3
05) 0 0 1 2 2
06) 0 0 2 4 4
07) 0 0 3 3 4
08) 0 1 1 1 2
09) 0 1 1 4 4
10) 0 1 2 3 4
11) 0 1 3 3 3
12) 0 2 2 2 4
13) 0 2 2 3 3
14) 0 3 4 4 4
15) 1 1 1 1 1
16) 1 1 1 3 4
17) 1 1 2 2 4
18) 1 1 2 3 3
19) 1 2 2 2 3
20) 1 2 4 4 4
21) 1 3 3 4 4
22) 2 2 2 2 2
23) 2 2 3 4 4
24) 2 3 3 3 4
25) 3 3 3 3 3
26) 4 4 4 4 4


Nota.
Con il termine "cinquina non ordinata" intendo un insieme di 5 numeri.

Come si vede, sono 26 cinquine.
Ora la domanda è:
usando soltanto i numeri 0, 1, 2, 3, 4, scrivete il più grande insieme di numeri che non contenga nessuna delle cinquine scritte sopra.
Il più facile che si possa trovare è il seguente:
{0, 0, 0, 0, 1, 1, 1, 1}
E' formato da 8 elementi.
Chi è in grado di trovarne un più grande, cioè con più di 8 elementi?
Pace e bene a tutti.
Gianfranco

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

Re: Somma multipla di 5 - ridurre il limite

Messaggio da gnugnu »

Le 26 5-ple ordinate elencate da Gianfranco sono accomunate da una semplice proprietà geometrica (oppue fisica se si preferisce) che rende facile completare la dimostrazione.

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

Re: Somma multipla di 5 - ridurre il limite

Messaggio da Gianfranco »

Credo di aver dimostrato che:
In un qualunque insieme di 9 numeri naturali se ne trovano 5 la cui somma è divisibile per 5. E che 9 è il limite minimo.
Uso il principio dei cassetti ma devo esaminare un certo numero di casi e sottocasi.

Però gnugnu parla di una semplice proprietà geometrica che permette di dimostrare facilmente il teorema.
Gnugnu, la dimostrazione di cui parli è breve o anch'essa richiede di esaminare alcuni casi e sottocasi?
Pace e bene a tutti.
Gianfranco

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

Re: Somma multipla di 5 - ridurre il limite

Messaggio da gnugnu »

La dimostrazione non è brevissima, esamina più casi e sotto casi, fa uso di un mini principio dei cassetti; probabilmente coincide nella sostanza con quella di Gianfranco.
Le classi di resto modulo n sono rappresentabili come vertici di un poligono regolare; quarantanni fa, quando insegnavo alle magistrali, si parlava di “aritmetica dell'orologio”: in questo caso un orologio con solo 5 ore, come nell'immagine, dove compaiono anche i 5 assi di simmetria.
mod5.jpg
mod5.jpg (13.98 KiB) Visto 4890 volte
Vale la proprietà: se i punti che rappresentano i 5 numeri formano una configurazione simmetrica allora la somma dei numeri è divisibile per 5.
Essendo 5 dispari, almeno uno dei punti deve appartenere all'asse di simmetria, i restanti potranno formare una o due coppie simmetriche rispetto a questo. Spostare una coppia, descrivendo l'arco più breve, fino a raggiungere il punto sull'asse non modifica la somma, perché i due spostamenti avranno la medesima lunghezza, uno in senso orario e l'altro antiorario, il che equivale a sommare e contemporaneamente sottrarre il medesimo numero (1 o 2). Quindi la somma è la stessa di 5 numeri appartenenti alla medesima classe, sicuramente multipla di 5.

Tornando alla questione del minimo è già stato dimostrato che con due sole classi occorrono almeno 9 numeri per essere certi di poterne estrarre 5 con somma multipla di 5. Potrebbe sorgere il dubbio che questa quantità possa crescere aumentando il numero delle classi, invece diminuisce.

Supponiamo di avere numeri di esattamente 3 classi diverse. Il triangolo che ha queste come vertici è isoscele per il principio dei cassetti: in un pentagono regolare, fra lati e diagonali, disponiamo solo di due lunghezze. Se non vogliamo avere cinquine con somma multipla di 5, nel vertice da cui escono i lati congruenti possono stare solo due punti (numeri): con tre si avrebbe la configurazione simmetrica 1-3-1. In almeno uno dei restanti deve stare un solo numero (altrimenti si otterrebbe la simmetria 2-1-2), nell'altro non più di 4. In tutto al massimo 1+2+4=7 numeri. Esempio (0 0 0 0 1 1 2).

Nel caso di 4 classi diverse ne possiamo sistemare solo 6. Da ciascuno dei quattro punti escono tre segmenti che terminano in un altro punto della quaterna, per il principio dei cassetti, due segmenti devono essere congruenti, perciò, per quanto visto prima, al massimo due numeri in ognuna delle 4 classi ed anche meno di tre classi con due numeri. Dunque, al più 2+2+1+1=6 numeri. Esempio (0 0 1 2 3 3).

Sono abbastanza convinto ( ma lontanissimo dal dimostrarlo) che il risultato si possa generalizzare con l'affermazione: in un insieme di 2n–1 numeri interi qualsiasi esiste sempre almeno un sottoinsieme di n numeri la cui somma è multipla di n. L'estensione del bell'esempio proposto da Gianfranco ( n–1 zeri ed n–1 uno) basterebbe allora per provare che 2n–1 è il minimo possibile

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

Re: Somma multipla di 5 - ridurre il limite

Messaggio da Gianfranco »

Grazie gnugnu per questa bella soluzione "geometrica".
In effetti, io che sono più "aritmetico" che "geometrico" avevo pensato a 9 colombe che devono sistemarsi in 5 cassette.
Se ne occupano soltanto 1, oppure soltanto 2, oppure tutte 5, allora la conclusione è immediata.
Se invece ne occupano 3 oppure 4 allura bisogna esaminare alcuni sottocasi.
Pace e bene a tutti.
Gianfranco

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

Re: Somma multipla di 5 - ridurre il limite

Messaggio da gnugnu »

Gabulando sulla generalizzazione ad n classi diverse, ho trovato una dimostrazione che non richiede la disamina di tanti casi e sottocasi.
Escludendo le soluzioni banali, 5 numeri che divisi per 5 danno il medesimo resto o 5 resti tutti diversi; per essere 4*2<9, in almeno una cassetta ci devono essere almeno tre colombe.
Osservo la classe di resto riportata sulla cassetta e sommo ai numeri delle 9 colombe (stringono un bigliettino nel becco o hanno un anello attorno ad una zampa?) quanto basta affinchè la classe della cassetta diventi 0.
Per quanto visto nella discussione "Un insieme di 5 numeri interi positivi", se considero una qualsiasi sequenza di 5 colombe che non stanno nella cassetta 0 (nella cassetta 0 non ce sono più di 4) esiste una sottosequenza con somma multipla di 5.
Questa sottosequenza è formata da almeno due colombe, perché nessuna porta un numero divisibile per 5; posso allora aggiungervi, se necessario, colombe della cassetta 0 fino ad averne in tutto 5.
I 5 numeri che ho trovato hanno somma multipla 5 e se sottraggo a ciascuno di essi quanto ho precedentemente sommato, tolgo un multiplo di 5 e, perciò, anche la differenza sarà ancora multipla di 5.

@Gianfranco:
anch'io preferisco i numeri ai segmenti, in particolare mi piace giocare con i problemi di combinatoria; forse è in qualche modo collegato con l'abitudine, che con te condivido, a formulare orari scolastici. I tuoi ringraziamenti mi paiono eccessivi; sono io ad esserti riconoscente per gli anni di lavoro che hanno portato a quest'inesauribile sorgente di problemi divertenti e stimolanti.

Rispondi