Pagina 1 di 2

Scambiando i numeri sul quadrante ...

Inviato: mer giu 15, 2016 2:48 pm
da franco
Q1.gif
Q1.gif (2.89 KiB) Visto 11062 volte
Scambiando a due a due i numeri (da 1 a 12) sul quadrante dell'orologio ridisponeteli in modo che ogni coppia adiacente abbia la somma pari a un numero primo.
Qual è il numero minimo di scambi necessario?

ciao

Re: Scambiando i numeri sul quadrante ...

Inviato: mer giu 15, 2016 10:53 pm
da Info
basta uno scambio... l'8 con il 10, ed e`tutto a posto :-)

Re: Scambiando i numeri sul quadrante ...

Inviato: mer giu 15, 2016 11:07 pm
da franco
Info ha scritto:basta uno scambio... l'8 con il 10, ed e`tutto a posto :-)
Uhm...

Direi che 4 e 5 restano adiacenti e sommano 9 che non è primo :twisted:


ciao

Re: Scambiando i numeri sul quadrante ...

Inviato: mer giu 15, 2016 11:19 pm
da Info
Sorry..... invertire 1 e 5 porta ad una possibile soluzione :-)
sono in totale 2 scambi

Re: Scambiando i numeri sul quadrante ...

Inviato: mer giu 15, 2016 11:59 pm
da panurgo
Ecco un esempio con quattro scambi

$\begin{array}{Cc}
1,2,3,4,5,6,7,8,9,10,11,12 \\\\
\downarrow \left(5 \leftrightarrow 7 \right) \\\\
1,2,3,4,7,6,5,8,9,10,11,12 \\\\
\downarrow \left(8 \leftrightarrow 12 \right) \\\\
1,2,3,4,7,6,5,12,9,10,11,8 \\\\
\downarrow \left(9 \leftrightarrow 11 \right) \\\\
1,2,3,4,7,6,5,12,11,10,9,8 \\\\
\downarrow \left(8 \leftrightarrow 10 \right) \\\\
1,2,3,4,7,6,5,12,11,8,9,10
\end{array}$

si verifica facilmente che

$\begin{array}{|CCCCCCCCCCCCCCCCCCCCCCCCC|ccc}
\hline
1 & + & 2 & + & 3 & + & 4 & + & 7 & + & 6 & + & 5 & + & 12 & + & 11 & + & 8 & + & 9 & + & 10 & + & 1 \\\\
& 3 & & 5 & & 7 & & 11 & & 13 & & 11 & & 17 & & 23 & & 19 & & 17 & & 19 & & 11 & \\
\hline
\end{array}$

Ho trovato (via computer) 1024 soluzioni distinte: non ho molta voglia di controllarle tutte.

Re: Scambiando i numeri sul quadrante ...

Inviato: gio giu 16, 2016 8:00 am
da franco
Info ha scritto:Sorry..... invertire 1 e 5 porta ad una possibile soluzione :-)
sono in totale 2 scambi
OK, con due scambi ci si riesce e la soluzione non è nemmeno unica.
Io avevo trovato questa (grazie a Guido per l'idea di come sistemarla graficamente):
Q11.jpg
Q11.jpg (10.72 KiB) Visto 11041 volte
Questo però era solo il riscaldamento :)

Come la mettiamo con quest'altro quadrante dove i numeri sono dall'1 al 24?
Q2.gif
Q2.gif (2.89 KiB) Visto 11041 volte
ciao

Re: Scambiando i numeri sul quadrante ...

Inviato: ven giu 17, 2016 3:40 am
da Pasquale
Sull'orologio da 12, due scambi sono obbligatori e vanno bene ad esempio anche gli scambi 4/8 e 1/11.
L'orologio da 24 mi sa che non si può fare, se non forse con molti scambi, ma non credo o comunque finora non ho saputo risolverlo.

Tuttavia, un orologio da 22 mi è riuscito di sistemarlo con i soli scambi 4/8, 11/19, 12/18, 14/16, che conducono alla seguente situazione:

1--2--3--8--5--6--7--4--9--10--19--18--13--16--15--14--17--12--11--20--21--22--1

Re: Scambiando i numeri sul quadrante ...

Inviato: ven giu 17, 2016 9:40 pm
da Gianfranco
Pasquale, una soluzione da 24 si ricava facilmente dalla tua per 22. Basta aggiungere opportunamente i numeri 23 e 24.
1--2--3--8--5--6--7--4--9--10--19--18--13--16--15--14--17--12--11--20--21--22--1
1--2--3--8--5--6--23--24--7--4--9--10--19--18--13--16--15--14--17--12--11--20--21--22--1
Infatti:
6+23=29 primo
23+24=47 primo
24+7=31 primo

Bel problema.
L'ho trasformato in una versione quasi equivalente ma per me più interessante:
"Data la sequenza dei numeri naturali da 1 a n, quante delle sue permutazioni circolari sono tali che la somma di ogni coppia di numeri successivi sia un numero primo?"
Per n dispari, probabilmente la soluzione è sempre 0.
Per n pari, ci sono sempre soluzioni?
E se ci sono, formano a loro volta una sequenza di qualche interesse?

Re: Scambiando i numeri sul quadrante ...

Inviato: ven giu 17, 2016 10:45 pm
da franco
Gianfranco ha scritto:L'ho trasformato in una versione quasi equivalente ma per me più interessante:
...
Allora a questo punto metto subito gli altri due quesiti che avevo pronti:

3. Ripetere l'esercizio con i numeri dei minuti anziché quelli delle le ore (numeri da 1 a 60)
Q3.gif
Q3.gif (3.65 KiB) Visto 11009 volte
4. Esiste un metodo che permetta di posizionare i primi n interi (con n pari) su un quadrante circolare in maniera tale che tutte le coppie adiacenti abbiano per somma un numero primo?


Questo problema è il casse-tete del mese di giugno su diophante.fr

Re: Scambiando i numeri sul quadrante ...

Inviato: ven giu 17, 2016 10:53 pm
da Gianfranco
Aggiunta notturna.
Anch'io ho fatto un programmino tipo quello citato da Panurgo.
Riporto qualche risultato.
Numero di soluzioni in funzione di n.
n ... num.sol.
2 ... 1
3 ... 0
4 ... 2
5 ... 0
6 ... 2
7 ... 0
8 ... 4
9 ... 0
10 ... 96
11 ... 0
12 ... 1024

Pe n>12 i tempi di calcolo diventano troppo lunghi (con il mio programmino).

Re: Scambiando i numeri sul quadrante ...

Inviato: sab giu 18, 2016 12:07 am
da Pasquale
OK, oggi sono stato al mare rimuginando sulla questione e stasera mi sono messo all'opera con l'idea che non bisogna mai demordere, trovando una soluzione a mano per orologio da 24, che posto pur avendo trovato il quesito già risolto.
Dunque, con gli scambi 1/5, 8/10, 13/17 e 20/22 si ottiene:

5--2--3--4--1--6--7--10--9--8--11--12--17--14--15--16--13--18--19--22--21--20--23--24--5

Passo quindi allo studio dell'orologio da 60.

Re: Scambiando i numeri sul quadrante ...

Inviato: sab giu 18, 2016 11:26 am
da Info
che dire Pasquale.... la tua e`certamente migliore di quella di Gianfranco, aggiungendo 24 e 23 sicuramente aumenta il numero di scambi rispetto ai 4 iniziali :-)

tu hai risolto con soli 4 scambi

Re: Scambiando i numeri sul quadrante ...

Inviato: dom giu 19, 2016 1:53 am
da Pasquale
Si, ma per quanto riguarda l'orologio da 60, non è stato tanto semplice.
Segue una soluzione senz'altro migliorabile, fatta sempre a mano, salvo una piccola routine per generare un foglio di appunti su cui lavorare, tenuto conto del fatto che la modifica della sequenza iniziale deve rispettare l'alternanza di numeri pari e dispari.
Ho quindi generato una tabella di tutti i numeri pari fra 2 e 60 ai quali abbinare per lo studio, fra i numeri dispari compresi nell'intervallo 1/59, solo quelli la cui somma desse come risultato un numero primo.

Gli scambi effettuati: 1/17 - 5/7 - 11/19 - 12/24 - 14/28 - 17/29 - 23/49 - 25/47 - 27/45 - 32/40 - 34/38 - 43/59 - 51/57 - 53/55

La sequenza modificata dagli scambi:

29-2-3-4-7-6-5-8-9-10-19-24-13-28-15-16-1-18-11-20-21-22-49-12-47-26-45-14-17-30-31-40-33-38-35-36-37-34-39-32-41-42-59-44-27-46-25-48-23-50-57-52-55-54-53-56-51-58-43-60-29

Aggiungo per chi voglia tentare un miglioramento la tabella utilizzata, con l'aggiunta nel riquadro superiore destro dei numeri primi che interessano (è possibile copiare l'immagine in un documento Word orizzontale e poi ingrandirla):
Tabella.JPG
Tabella.JPG (31.27 KiB) Visto 10995 volte
La suddetta tabella credo sia sufficiente per rispondere al quesito n.4 postato da Franco, che non riguarda più lo scambio di numeri.
Infatti, guardando i numeri contenuti nella tabella si può procedere ad esempio così:

parto col 60 ed aggiungo subito il 53, perché 60+53=113 (primo)
cerco quindi a quale altro numero pari si può accoppiare il 53 e trovo subito che esiste un 53 fra i numeri accoppiabili al 56
vedo quindi che fra i numeri accoppiabili al 56 c'è anche un 57 non ancora utilizzato
vado a cercare quale altro numero pari si accoppia al 57 e trovo il 52
al 52 può seguire il 55 e vado allora a cercare un altro numero pari accoppiabile al 55; trovo il 54......e così via

Certo che se n è troppo grande, allora è una faticaccia; probabilmente il sito francese vuole riferirsi ad un criterio diverso....magari qualche formula o routine generalizzabile che semplifichi il procedimento; la mia proposta si riferisce al vecchio e famoso, pur se limitato, :mrgreen: "metodo a mano".
Ad ogni modo penso che si possa generare una routine che faccia la ricerca sulla tabella, generando una sequenza valida in breve tempo, seguendo il criterio sopra accennato.

Re: Scambiando i numeri sul quadrante ...

Inviato: dom giu 19, 2016 10:19 pm
da Gianfranco
Franco ha scritto:
4. Esiste un metodo che permetta di posizionare i primi n interi (con n pari) su un quadrante circolare in maniera tale che tutte le coppie adiacenti abbiano per somma un numero primo?
Attenzione: ho apportato alcune correzioni segnalate in rosso, in seguito a un'osservazione di Pasquale.

Ho messo assieme un metodo simile a quello per risolvere i problemi del tipo "Ponti di Konisberg", con i grafi di divisibilità (che non hanno niente a che fare l'uno con l'altro).
Telegraficamente, il metodo sarebbe questo.
Faccio un esempio molto semplice per n=8.
a) Scrivo i numeri in cerchio e collego con una linea le coppie di numeri la cui somma è un numero primo.
grafo_primi1.png
grafo_primi1.png (14.34 KiB) Visto 10986 volte
I collegamenti formano un grafo.
b) Per risolvere il problema devo trovare una linea che parta da un numero e tocchi tutti gli altri numeri una volta sola etc. ritornando al numero di partenza.
Il grafo in questione si può risolvere e la linea può partire da qualunque numero (deve partire dal numero 7 o dal numero 8 (nodi di ordine pari)). I numeri 7 e 8 sono "critici" perché hanno soltanto due collegamenti.
Ecco una soluzione.
grafo_primi2.png
grafo_primi2.png (24.88 KiB) Visto 10986 volte
Tale metodo si generalizza a qualunque n.
Abbiamo già visto che il problema non ha soluzione per n dispari.

Ora c'è una bella domanda (anzi due): il problema è risolvibile per ogni numero pari? E quante soluzioni ha?

Re: Scambiando i numeri sul quadrante ...

Inviato: lun giu 20, 2016 2:58 am
da Pasquale
Bene Gianfranco, la rappresentazione grafica ridotta, cioè con n piccolo, consente di comprendere bene la problematica, che meglio ancora si comprende per n=4 ed n=6.
Tuttavia devo osservare che se una soluzione c'è, vuol dire che esiste un percorso che, per quanto complesso, topologicamente altro non è che un anello; per cui lungo tale percorso è sempre possibile partire da qualsiasi numero e ritornare sullo stesso.
Ad esempio, seguendo il percorso tracciato nel grafo da 8 numeri, posso benissimo partire da 3 verso 2, o da 3 verso 8, e proseguire sino al ritorno sul 3 (così dicasi per qualsiasi altro numero che si incontra lungo il percorso)
In definitiva, possiamo affermare che dato un n è sufficiente trovare un solo anello per dare soluzione al problema, con partenza da qualsiasi numero lungo quel dato percorso; l'unica difficoltà consiste nel trovare tale percorso e se poi ce n'è più d'uno, tanto meglio.
Quando n cresce, aumentano le difficoltà nel trovare una sequenza valida e mi sa che l'approccio grafico diviene complicato da applicare; dunque bisogna trovare qualcosa d'altro, che certamente esiste, perché sennò quelli del sito francese non avrebbero proposto il quesito.
Ad ogni modo, il tuo grafo mi è stato utile per capire di più. Quando sono andato alla ricerca delle soluzioni precedenti (lo scambio nelle coppie di numeri non cambia i termini del problema più generale), ho dovuto un po' faticare per trovare i percorsi risolutivi e mi sono aiutato con la tabella di cui sopra, sviluppata solo rispetto ai numeri pari, perché mi faceva comodo così; però è sempre possibile costruire una tabella completa per tutti gli n numeri, la quale per un n piccolo aiuta anche nella costruzione di un grafo.
Inoltre una tabella può risultare utile per impostare una routine di ricerca del percorso, purché n non cresca più di un tot; ecco perché penso che debba esserci qualche altra soluzione.............