Saldi d'inizio d'anno
Inviato: 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.
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.