Scambiando i numeri sul quadrante ...

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

Moderatori: Gianfranco, Bruno

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

Re: Scambiando i numeri sul quadrante ...

Messaggio da Gianfranco » lun giu 20, 2016 6:33 am

Pasquale ha scritto:
Tuttavia devo osservare che se una soluzione c'è, vuol dire che esiste un percorso che, per quanto complesso, topograficamente altro non è che un anello; per cui lungo tale percorso è sempre possibile partire da qualsiasi numero e ritornare sullo stesso.
Hai ragione, grazie, ho apportato alcune correzioni al mio post di ieri (19/giugno).
Pace e bene a tutti.
Gianfranco

Pasquale
Livello 11
Livello 11
Messaggi: 2307
Iscritto il: mer mag 25, 2005 1:14 am

Re: Scambiando i numeri sul quadrante ...

Messaggio da Pasquale » lun giu 20, 2016 8:15 am

Scusate, anch'io ho dovuto apportare una correzione su un piccolo lapsus (avevo scritto topograficamente invece che topologicamente).
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

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

Re: Scambiando i numeri sul quadrante ...

Messaggio da Gianfranco » lun giu 20, 2016 8:29 am

Pasquale ha scritto:
Inoltre una tabella può risultare utile per impostare una routine di ricerca del percorso
Perfetto, la tabella che hai proposto descrive il grafo con una lista di adiacenze.
A questo punto sarebbe bello scrivere un programma che trovi automaticamente il percorso cercato...
Pace e bene a tutti.
Gianfranco

Pasquale
Livello 11
Livello 11
Messaggi: 2307
Iscritto il: mer mag 25, 2005 1:14 am

Re: Scambiando i numeri sul quadrante ...

Messaggio da Pasquale » mar giu 21, 2016 12:11 am

Perché, credi che non ci abbia già pensato? E' da un pezzo che sto rimuginando sulla faccenda, ma il problema è che se n cresce appena più di tanto, bisogna combattere con numeri troppo grandi e quindi troppa lentezza. Allora bisogna semplificare e comunque riferirsi ad n "piccini".
Alla luce di quanto già detto precedentemente, stavo pensando di orientare lo studio su dati già noti.
Ad esempio, se l'obiettivo è quello di trovare un percorso valido di andata e ritorno, quasi come se si dovesse affrontare il labirinto d'un giardino all'italiana senza perdersi al suo interno (il grafo), allora si potrebbe limitare lo studio ad un solo qualsivoglia numero di partenza, che come abbiamo visto comunque deve far parte di un circuito completo.
Stavo pensando ad esempio, dato un n, ad una matrice da riempire, dimensionata DIM a(n+1), in cui a(1)=1, a(n+1)=1.
Limitare quindi la ricerca solo ai valori da inserire nelle posizioni fra a(2) ed a(n), in cui alternativamente inserire validi numeri pari e dispari (validi nel senso che la somma con gli adiacenti deve restituire sempre un primo già non utilizzato in altra posizione).
In sostanza si tratta di stabilire un criterio da seguire per la costruzione di una routine che, se di tipo "stupido", non porta lontano.
Al momento non ho messo ancora nero su bianco, sia per mancanza di tempo, sia per scarsa convinzione sul risultato, che potrebbe consentire una certa soddisfazione solo per piccoli n.

Esempio:
se decido di partire da 1, nella suddetta matrice (che una volta riempita servirebbe per la stampa dell'intero percorso), il successivo passo sarebbe la ricerca del secondo numero da inserire in posizione a(2), da scegliere fra 2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40 42, 46, 52, 58 e 60 (nel caso di n=60).
Seguirebbe poi per a(3) un numero dispari da scegliere per ognuno dei suddetti numeri fra una quantità dello tesso ordine di grandezza [17 se a(2)=2].
Si comprende ben presto, considerato che la validità del percorso sarà nota solo al momento dell'inserimento di un numero valido in posizione a(n), che se non si è fortunati, bisogna riprovare tutti gli altri valori inseribili in a(n-1), lasciando inalterati i precedenti e così continuando all'indietro, prima di decidere che magari a(2) non era valido e quindi ripartire con altro valore in tale posizione e reiterare il procedimento.
Può anche accadere che la ricerca si interrompa ad esempio in a(25), perché nessun numero in tale posizione consente di proseguire.
Insomma nonostante la limitazione della ricerca ad una partenza prefissata ad un solo numero già noto, non vedo una luce su questa strada (si pensi ad esempio ad un n=1000, dove andiamo a finire?).

Il fatto strano è che i quesiti similari già risolti sopra, limitati ad n=12, n=24, n=60, è stato possibile risolverli più facilmente "ad occhio", con l'ausilio di una tabella: occhio batte routine, ma soltanto perché la tabella di studio era visibile per intero in una sola pagina; però con un n maggiore ............ ??

Dunque, anche per queste considerazioni non mi sono applicato più di tanto nella questione, pensando che chissà non sia possibile un approccio diverso su una strada piena di ostacoli, dovendosi confrontare con numeri primi e valori combinatori stratosferici.

Vediamo se scappa fuori qualche nuova idea da parte di qualcuno: io al momento mi fermo qui, anche perché sennò corro il rischio che qualcuna di mia conoscenza possa corrermi dietro brandendo un minaccioso mestolo da cucina.
Ultima modifica di Pasquale il sab giu 25, 2016 1:35 pm, modificato 1 volta in totale.
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Pasquale
Livello 11
Livello 11
Messaggi: 2307
Iscritto il: mer mag 25, 2005 1:14 am

Re: Scambiando i numeri sul quadrante ...

Messaggio da Pasquale » ven giu 24, 2016 12:03 am

OK, stimolato da Gianfranco, in un momento di pausa ho studiato un compromesso per una routine in Decimal Basic valida per piccoli numeri e che potrebbe abbisognare di qualche aggiustamento. In caso di blocco, rilanciare il programma e magari cambiare il numero iniziale e/o ritoccare il valore di reiterazione fisso che al momento ho fissato per sicurezza a 5000, ma che può essere abbassato anche a 1000 per k più piccoli, oppure ricercare possibili errori o apportare i miglioramenti del caso.
L'ho provata fino a k=100, dovendo però attendere un po' per il risultato ed ancora di più per k=200 (non ci sono stati blocchi dopo un ultima mia correzione).
Per k=60 è abbastanza veloce e naturalmente ancora di più per k minori.

Dunque, copiare e incollare su Decimal Basic ed iniziare a provarlo con k crescenti:

!'ordinare numeri su circonferenza:
!'fissati lungo una circonferenza i numeri compresi fra 1 e k, !'con k pari, ordinarli in modo che la somma di ogni coppia adiacente sia un numero primo
!'Per iniziare il percorso, ogni numero fra 1 e k va bene, come abbiamo già visto in precedente studio, e quindi ho lasciato la scelta libera

INPUT PROMPT "Quantità pari di numeri sul cerchio ->":k
DIM a(k) !'matrice dei numeri costituenti il percorso, o meglio un percorso valido, cercato con procedimento misto/casuale
INPUT PROMPT "inserisci numero iniziale/finale del percorso ->":a(1)
DIM TA(k,0 TO k/2)!'tabella dei numeri abbinabili validamente a ciascuno dei k numeri, cioè che sommati a questi diano per risultato un numero primo
DIM TB(k,0 TO k/2)!'copia di TA per esigenze di lavoro
PRINT

FOR m=1 TO k ' costruisci tabella TA
LET cont=0
FOR n=1 TO k
IF MOD(m,2)<>MOD(n,2)THEN
LET p=m+n
LET s1=0
LET s2=0
FOR q= 1 TO p
LET s1=s1+INT(p/q)
LET s2=s2+INT((p-1)/q)
NEXT q
IF s1-s2=2 THEN
LET cont=cont+1
LET TA(m,cont)=n
END IF
END IF
NEXT n
LET TA(m,0)=cont
NEXT m

!'cancella a(1) da tutta la tabella
FOR p=1 TO k
FOR q=1 TO TA(p,0)
IF TA(p,q)=a(1) THEN LET TA(p,q)=0
NEXT Q
NEXT P

!'costruisci il percorso
DO
MAT TB = TA 'copia in TB la tabella TA
FOR m=2 TO k

LET v=a(m-1)
LET w=TB(v,0) ' in questa posizione viene memorizzata la quantità di numeri validamente abbinabili a ciascuno dei k

!'tentativi ricerca numero valido rispetto al precedente
FOR n=1 TO 2000
LET x=1+INT(RND*w)
IF TB(v,x)=0 THEN
IF n<2000 THEN
GOTO 20
ELSE
GOTO 30
END IF
ELSE
LET a(m)=TB(v,x)
IF m=k THEN
LET p=a(m)+a(1)
LET s1=0
LET s2=0
FOR q=1 TO p
LET s1=s1+INT(p/q)
LET s2=s2+INT((p-1)/q)
NEXT q
IF s1-s2=2 THEN
EXIT DO
ELSE
GOTO 20
END IF
END IF
!'cancella a(m) da tutta la tabella
FOR p=1 TO k
FOR q=1 TO TB(p,0)
IF TB(p,q) = a(m) THEN LET TB(p,q)=0
NEXT q
NEXT p
EXIT FOR
END IF
20 NEXT N
NEXT M
30 LOOP

PRINT "PERCORSO VALIDO:"
PRINT
FOR m=1 TO k
PRINT a(m);
NEXT M

Di seguito alcune sequenze.

per k=100:

99 2 81 26 45 68 95 96 7 66 61 22 25 6 17 20 87 40 39 98 69 70 37 76 91 60 49 88 13 30 1 78 11 50 57 80 23 48 41 86 93 44 35 62 5 84 97 54 53 18 65 32 75 64 9 4 33 74 83 14 47 92 71 8 51 56 27 52 55 12 31 36 67 46 85 72 77 90 59 38 29 24 89 42 19 82 21 10 79 58 15 94 73 34 3 28 43 16 63 100

per k=150:

75 136 63 20 111 146 5 36 95 72 101 98 53 144 119 150 89 74 15 124 69 142 85 94 105 34 97 102 25 112 129 68 131 140 117 122 59 90 133 96 83 30 67 4 147 2 107 134 29 14 123 26 41 6 55 16 45 148 43 88 39 40 139 42 37 66 7 106 1 130 109 118 13 138 143 48 31 100 57 56 125 12 19 132 79 22 21 10 121 18 149 114 17 24 35 128 71 120 137 54 73 28 103 108 23 78 113 86 65 84 127 64 115 126 145 82 141 50 33 104 77 62 47 92 135 76 87 44 9 70 61 46 91 60 49 52 27 32 51 58 99 80 93 8 11 116 81 110 3 38

per k=250:

1 138 199 78 29 42 221 146 207 232 25 64 9 230 149 188 201 32 161 122 231 248 213 136 127 124 67 22 171 56 33 250 151 88 243 50 47 180 167 114 23 24 209 72 179 174 245 102 37 4 229 160 117 134 77 20 131 98 143 236 5 194 113 66 173 210 59 48 175 76 31 118 75 52 177 220 247 10 7 94 15 214 145 82 49 40 3 190 159 152 129 104 69 202 241 90 17 44 195 112 237 74 83 228 203 26 137 120 91 36 233 150 239 222 125 212 249 200 183 16 57 170 227 86 11 246 133 216 95 62 89 84 139 142 169 162 217 6 41 60 121 130 63 116 197 186 107 204 185 168 61 28 79 132 181 192 191 182 215 14 153 128 99 158 21 178 115 234 97 166 105 68 71 108 205 46 165 34 123 208 223 240 193 196 43 30 163 18 35 92 45 154 103 126 73 244 109 238 211 172 19 54 85 184 225 224 155 38 93 164 147 110 119 12 187 70 27 140 141 206 111 2 39 100 157 226 87 176 81 148 189 80 51 242 219 58 13 144 55 156 101 96 235 198 53 8 65 218 135 106

BUON DIVERTIMENTO :D
Ultima modifica di Pasquale il lun giu 27, 2016 10:53 pm, modificato 1 volta in totale.
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Pasquale
Livello 11
Livello 11
Messaggi: 2307
Iscritto il: mer mag 25, 2005 1:14 am

Re: Scambiando i numeri sul quadrante ...

Messaggio da Pasquale » ven giu 24, 2016 4:03 pm

Nei precedenti interventi ci si è posti il quesito "Per quali k esiste la sequenza voluta? Esiste sempre, per qualsiasi k, posto che k deve essere sempre pari?"
Ricordo che la sequenza deve essere ordinata in modo che la somma di ogni coppia adiacente sia un numero primo e che se completa (inizio e fine sullo stesso numero),
può iniziare da uno qualsiasi dei k numeri.
A tale proposito, segue una routine, tratta dalla precedente con piccoli adattamenti, la quale genera tabelle dimensionate in modo che siano sempre capienti per contenere tutti i numeri validi per la soluzione del quesito principale (ricerca della giusta sequenza dei numeri fra 1 e k): infatti, poiché la sequenza cercata è costituita alternativamente da numeri pari e dispari, ad ognuno dei k numeri potrebbero essere abbinati al massimo k/2 numeri con le caratteristiche richieste (ammesso che tutti ce l'abbiano), per un totale di K^2/2 presumibilmente sufficienti, pur se con molteplici ripetizioni degli stessi numeri nell'ambito della tabella, che possono condurre a sequenze con o senza uscita.
Può notarsi comunque che nella ricerca effettuata a mezzo della precedente routine, K/2 numeri da abbinare non ci sono mai, essendone presenti in quantità minore e variabile in relazione allo specifico valore fra quelli dei k in gioco.
Capire se tale quantità di numeri utilizzabile sia sempre sufficiente non mi è dato, salvo la formulazione di qualche "congettura probabilistica" basata sull'osservazione e sulla tendenza delle quantità in gioco.
La routine che segue, viene utilizzata per eseguire un conteggio, sfruttando la colonna zero della tabella, nella quale sono appunto memorizzate le quantità dei numeri validi abbinabili a ciascuno dei k numeri.
La routine finché può restituisce per ogni k la quantità di numeri validi contenuti nella tabella e dai dati che se ne ricavano si può notare un andamento crescente del rapporto fra la quantità di numeri in tabella e lo stesso k, tale da far immaginare una tendenza a {k^2}{2} dei numeri in tabella, comprese tutte le ripetizioni, anche se in realtà il valore k/2 di numeri attribuibili ad ognuno dei k numeri non potrà mai essere raggiunto, in quanto ad un qualsiasi numero dispari dei k/2 non è possibile abbinare qualsiasi pari dei k/2 esistenti, perché ci sarà sempre una somma con risultato non primo; altrettanto dicasi per i numeri dispari da abbinare ai k/2 pari.
In sostanza, possiamo supporre che un percorso risolutore possa probabilmente sempre esistere, considerata la molteplicità di numeri in gioco, ma più di tanto non saprei dire.



Riporto qui di seguito una piccola lista dei numeri presenti in tabella rispetto a diversi valori di k crescenti:

k
002.....02
004.....08
006.....14
008.....22
010.....36
012.....50
014.....62
016.....80
018.....96
020....112
022....134
024....156
026....180
028....208
030....234
032....262
034....292
036....326
038....362
040....400
.
.
.
100..2088
200..7352

Infine, considerata come unica la soluzione in cui una sequenza, iniziata da uno qualsiasi dei k numeri, procedendo in senso orario o antiorario, conserva sempre la stessa disposizione relativa dei numeri fra loro, sarei portato a pensare che tale soluzione sia unica, per il fatto semplicemente pratico/intuitivo che altre non ne ho trovato, anche se poco matematico.

Esempio di soluzione considerata unica, ritenuta tale come da precedente definizione (k=6):

1 4 3 2 5 6
1 6 5 2 3 4
4 3 2 5 6 1
4 1 6 5 2 3
3 2 5 6 1 4
3 4 1 6 5 2
2 5 6 1 4 3
2 3 4 1 6 5
5 6 1 4 3 2
5 2 3 4 1 6
6 1 4 3 2 5
6 5 2 3 4 1

vale a dire 2k soluzioni apparentemente diverse, ma che non cambiano la disposizione dei k numeri sulla circonferenza/orologio.



INPUT PROMPT "inserisci la quantità pari di numeri sulla circonferenza -> ":k
DIM TA(k,0 TO k/2)!'matrice dei numeri abbinabili ai k numeri
PRINT

FOR m=1 TO k
LET cont=0
FOR n=1 TO k
IF MOD(m,2)<>MOD(n,2)THEN
LET p=m+n
LET s1=0
LET s2=0
FOR q= 1 TO p
LET s1=s1+INT(p/q)
LET s2=s2+INT((p-1)/q)
NEXT q
IF s1-s2=2 THEN
LET cont=cont+1
LET TA(m,cont)=n
END IF
END IF
NEXT n
LET TA(m,0)=cont
NEXT m

LET tot=0
FOR m=1 TO k
LET tot=tot+ta(m,0)
NEXT M
PRINT k;tot

END

Ho dovuto trarre i risultati delle tabelle uno alla volta, perché mi pare che nel Decimal Basic non sia previsto il comando REDIM, presente in altre versioni Basic.
Gianfranco, tu che ne pensi? E' superabile in altro modo questa carenza? Mi sfugge qualcosa? In sostanza, avevo bisogno di avviare un ciclo in cui fosse possibile azzerare una matrice (cancellarla del tutto dalla memoria) e crearne un'altra di dimensione diversa, ma con lo stesso nome della precedente cancellata.
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Pasquale
Livello 11
Livello 11
Messaggi: 2307
Iscritto il: mer mag 25, 2005 1:14 am

Re: Scambiando i numeri sul quadrante ...

Messaggio da Pasquale » mar giu 28, 2016 12:47 am

Grazie alla dritta di Gianfranco, riporto la precedente routine modificata, relativa allo studio circa una possibile limitazione o meno dei numeri inseribili sulla circonferenza.
Come avevo già detto, si può adesso meglio notare l'andamento del fenomeno al crescere di k, anche se i k sono limitati per ragione della lentezza di elaborazione.
In sostanza si intravvede che, per ogni k, l'esistenza di un percorso di ordinamento dei k numeri, secondo la ripetuta regola, è più probabile al crescere di k e dunque induttivamente sempre possibile. Quanto meno, penso che sia più difficoltoso dimostrare il contrario.
Nella tabella generata dalla routine vengono indicati la grandezza del k, i numeri totali abbinabili secondo la regola di cui trattasi, il rapporto fra questi ed il rispettivo k.
Come si può notare, pur nella scarsità del campione, tale rapporto ha andamento crescente.

DIM TA (200,0 TO 100)
PRINT " k ";"Num.Abbin. ";"Rapporto"


FOR k=10 TO 200 STEP 10

REDIM TA(k,0 TO k/2)!'matrice dei numeri abbinabili ai k numeri
PRINT

FOR m=1 TO k
LET cont=0
FOR n=1 TO k
IF MOD(m,2)<>MOD(n,2)THEN
LET p=m+n
LET s1=0
LET s2=0
FOR q= 1 TO p
LET s1=s1+INT(p/q)
LET s2=s2+INT((p-1)/q)
NEXT q
IF s1-s2=2 THEN
LET cont=cont+1
LET TA(m,cont)=n
END IF
END IF
NEXT n
LET TA(m,0)=cont
NEXT m

LET tot=0
FOR m=1 TO k
LET tot=tot+ta(m,0)
NEXT M
PRINT USING "### ":k;
PRINT USING "######## ":tot;
PRINT USING "########.##":tot/k
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Rispondi