Saldi d'inizio d'anno

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
giobimbo
Livello 5
Livello 5
Messaggi: 238
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Saldi d'inizio d'anno

Messaggio da giobimbo » gio gen 29, 2009 5:55 pm

Nei suoi saldi di fine anno Franco chiedeva:
6) Fra i numeri interi naturali 1, 2, 3, ..., 2008 costituire il più grande sottoinsieme possibile tale che nessuna delle differenze fra due dei suoi elementi abbia come valore 6 o 11.

Dopo averlo risolto ho visto che tale problema si può visualizzare come un grafo in cui ad ogni vertice si assegni un numero da 1 a 17, con due vertici collegati da un arco, una linea, se e solo se la differenza dei numeri dei due vertici vale 6 o 11. Bisogna allora colorare di blu il massimo numero di vertici, con l'unica regola che due vertici blu non possono essere collegati da una linea.
Nota bene: il massimo numero di elementi si ottiene colorando i vertici 1 e 2 di blu, se possibile, come spiegato in "Saldi di fine anno".
Nelle figure sotto i vertici sono rappresentati da circoletti numerati.
La figura A dà la soluzione del problema di Franco, il sottoinsieme più grande è formato dai numeri che sono congrui a 1, 2, 4, 6, 9, 11, 14 e 16 (modulo 17), con un totale di 946 elementi. Mi sembra che usando i grafi tutto diventi più facile, per cui propongo altri tre problemi:

6bis) Fra i numeri interi naturali 1, 2, 3, ..., 2008 costituire il più grande sottoinsieme possibile tale che nessuna delle differenze fra due dei suoi elementi abbia come valore 4, 7, 10 o 13 (figura B sotto).

6ter) Fra i numeri interi naturali 1, 2, 3, ..., 2008 costituire il più grande sottoinsieme possibile tale che nessuna delle differenze fra due dei suoi elementi abbia come valore 3, 5, 12 o 14 (figura C sotto).

6quater) Fra i numeri interi naturali 1, 2, 3, ..., 2008 costituire il più grande sottoinsieme possibile tale che nessuna delle differenze fra due dei suoi elementi abbia come valore 3, 7 e 8.
Allegati
franco-saldi.gif
franco-saldi.gif (24.12 KiB) Visto 1456 volte

Rispondi