Le scalinate del Colonnello

[giobimbo]

Abbiamo un insieme di n mattoni numerati da 1 a n dal quale ne prendiamo m, per costruire una scalinata (poi per semplicità scriveremo solo i numeri per indicare i corrispondenti mattoni numerati). Indichiamo con Sr la scalinata la cui prima fila di mattoni ne contiene r; la seconda fila ne conterrà r-1, la terza r-2 e via salendo fino ad arrivare a una fila di un solo mattone. Nella prima fila mettiamo r mattoni a scelta, mentre per le altre file in alto valgono le regole:
1) Se il mattone s sta sopra il mattone t e a destra di t sta il mattone u, allora dev’essere s=abs(t-u), cioè s dev’essere il valore assoluto della differenza tra t e u.
2) I numeri della scalinata devono essere tutti diversi.
3) Il numero m dev’essere il più piccolo possibile

Alcuni esempi:
S3 r=3 m=6
1
3 4
5 2 6

S4 r=4 m=10
4
2 6
5 7 1
8 3 10 9

Per r=6 e m=21 Herbert Taylor ha dimostrato, in una lettera inviata a Martin Gardner, che non esiste scalinata, allora, rispettando le tre regole che definiscono la scalinata del Colonnello:

Problema: trovare una S6 con r=6 e m=minimo.

[Quelo]

Una soluzione esiste per m=22

Codice: Seleziona tutto

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

[giobimbo]

Bravo Quelo, è la stessa soluzione che ho trovato io, ottimo.

[Quelo]

C'è una soluzione anche per m=23

Codice: Seleziona tutto

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

Si intravede uno schema

[Quelo]

Ecco la soluzione minima (presumo) per r = 7 (m = 33)

Codice: Seleziona tutto

 8
10 18 
12 22  4 
15 27  5  9 
16  1 28 23 14 
13 29 30  2 25 11 
19 32  3 33 31  6 17

per r = 8 non ho trovato niente fino a m = 43

[giobimbo]

@Quelo: il problema del Colonnello Sicherman è un caso particolare di un vecchio argomento su cui torno saltuariamente. L’ho affrontato per tentativi usando sequenze che superassero un certo controllo di parità, una cosa semplice. Se ci hai visto una qualche regolarità mi piacerebbe una tua spiegazione, io, solo guardando le tue soluzioni non ci sono arrivato

[Quelo]

Devo confessare di aver usato un po’ di forza bruta (con qualche semplificazione). Così facendo ho ricavato le soluzioni per r=6, 7 e anche 8.
Eccone 2 per r = 8 m = 46

Codice: Seleziona tutto

9
10 19
15 25  6 
18 33  8 14 
20  2 35 27 13 
16 36 38  3 30 17 
21 37  1 39 42 12 29 
28  7 44 43  4 46 34  5

9 
12 21 
16 28  7 
18 34  6 13 
20 38  4 10 23 
22  2 40 36 26  3 
17 39 41  1 37 11 14 
27 44  5 46 45  8 19 33

La mia idea iniziale era provare tutte le combinazioni del gradino più basso e poi costruire la scalinata per vedere se era coerente. Ha funzionato per r=6 ma con il 7 ci metteva troppo, quindi ho dovuto cambiare strategia e partire dall’alto.
Vediamo cosa hanno in comune le varie soluzioni (almeno le minime).
La prima riga (il mattone più in alto) ha un numero che è della stessa grandezza di r, con qualche eccezione (3 per r=3, 4 per r=4, 5 per r=5, 4 per r=6, 8 per r=7 e 9 per r=8). Quindi non serve provarli tutti, diciamo da r/2 a 2r.
Sulla seconda riga abbiamo 2 numeri (basso a sinistra, alto a destra, in quanto le scalinate sono reversibili, cioè si possono allineare sia a destra che a sinistra)
Scendendo ci accorgiamo che nella prima colonna i numeri sono tendenzialmente crescenti e molto vicini, più in generale i numeri molto bassi e molto alti sono raggruppati al centro, mentre quelli medi alle estremità.
Quindi teniamo la regola che sulla prima colonna il numero che sta sotto è compreso tra la metà e il doppio di quello che sta sopra.
Scelto il numero sulla prima colonna, costruiamo la riga con queste regole
1. Se il numero sopra è più grande, quello a destra sarà la somma dei due
2. Se il numero sopra è più piccolo quello a destra può essere sia la somma che la differenza
Nel secondo caso si sdoppia la soluzione e si prosegue con due rami, questo comporta il moltiplicarsi delle soluzioni da provare, ma è comunque molto più veloce dell’altro metodo.
Nella terza riga, volendo tenere un numero alto come centrale, il seocndo numero sarà necessariamente una somma e il terzo una differenza.
Dalla quarta riga in poi non c’è uno schema fisso.
Ti lascio un po’ di soluzioni non minime se ci vuoi ragionare sopra.

Codice: Seleziona tutto

[3], [5, 8], [4, 9, 1], [6, 2, 11, 12], [10, 16, 18, 7, 19]
[4], [5, 9], [7, 12, 3], [8, 1, 13, 16], [6, 14, 15, 2, 18]
[4], [6, 10], [7, 13, 3], [8, 15, 2, 5], [9, 1, 16, 14, 19]
[4], [6, 10], [7, 13, 3], [9, 2, 15, 18], [5, 14, 16, 1, 19]
[4], [6, 10], [7, 13, 3], [11, 18, 5, 2], [12, 1, 19, 14, 16]
[4], [7, 11], [5, 12, 1], [8, 3, 15, 16], [6, 14, 17, 2, 18]
[4], [7, 11], [6, 13, 2], [9, 3, 16, 18], [5, 14, 17, 1, 19]
[4], [7, 11], [9, 16, 5], [8, 17, 1, 6], [10, 2, 19, 18, 12]
[4], [7, 11], [9, 16, 5], [10, 1, 17, 12], [8, 18, 19, 2, 14]
[5], [4, 9], [7, 11, 2], [8, 1, 12, 10], [6, 14, 15, 3, 13]
[5], [4, 9], [7, 11, 2], [10, 3, 14, 16], [8, 18, 15, 1, 17]
[5], [4, 9], [7, 11, 2], [10, 3, 14, 12], [8, 18, 15, 1, 13]
[5], [6, 11], [7, 13, 2], [8, 1, 14, 16], [10, 18, 17, 3, 19]
[5], [6, 11], [7, 13, 2], [8, 1, 14, 12], [9, 17, 18, 4, 16]
[5], [6, 11], [7, 13, 2], [8, 1, 14, 12], [10, 18, 17, 3, 15]
[5], [6, 11], [8, 14, 3], [7, 15, 1, 4], [9, 2, 17, 16, 12]
[5], [6, 11], [9, 15, 4], [10, 1, 16, 12], [7, 17, 18, 2, 14]
[5], [7, 12], [6, 13, 1], [8, 2, 15, 14], [9, 17, 19, 4, 18]
[5], [7, 12], [9, 16, 4], [10, 1, 17, 13], [8, 18, 19, 2, 15]
[5], [7, 12], [9, 16, 4], [11, 2, 18, 14], [6, 17, 19, 1, 15]
[6], [4, 10], [7, 11, 1], [9, 2, 13, 12], [5, 14, 16, 3, 15]
[6], [5, 11], [7, 12, 1], [8, 15, 3, 4], [10, 2, 17, 14, 18]
[6], [5, 11], [7, 12, 1], [9, 2, 14, 15], [10, 19, 17, 3, 18]
[6], [5, 11], [7, 12, 1], [9, 2, 14, 13], [10, 19, 17, 3, 16]
[6], [5, 11], [8, 13, 2], [9, 1, 14, 12], [7, 16, 17, 3, 15]
[6], [5, 11], [8, 13, 2], [9, 1, 14, 12], [10, 19, 18, 4, 16]
[6], [5, 11], [9, 14, 3], [10, 1, 15, 12], [8, 18, 19, 4, 16]
[6], [7, 13], [9, 16, 3], [8, 17, 1, 4], [10, 2, 19, 18, 14]
[7], [5, 12], [8, 13, 1], [9, 17, 4, 3], [11, 2, 19, 15, 18]
[7], [5, 12], [8, 13, 1], [10, 2, 15, 14], [6, 16, 18, 3, 17]
[7], [5, 12], [9, 14, 2], [10, 1, 15, 13], [8, 18, 19, 4, 17]
[7], [6, 13], [8, 14, 1], [9, 17, 3, 4], [11, 2, 19, 16, 12]
[7], [6, 13], [9, 15, 2], [10, 1, 16, 14], [8, 18, 19, 3, 17]
[7], [6, 13], [10, 16, 3], [8, 18, 2, 5], [9, 1, 19, 17, 12]
[8], [5, 13], [9, 14, 1], [11, 2, 16, 15], [6, 17, 19, 3, 18]

[4], [7, 11], [6, 13, 2], [9, 3, 16, 14], [15, 24, 21, 5, 19], [10, 25, 1, 22, 27, 8]
[4], [7, 11], [9, 16, 5], [10, 1, 17, 12], [8, 18, 19, 2, 14], [13, 21, 3, 22, 20, 6]
[4], [7, 11], [9, 16, 5], [10, 1, 17, 12], [14, 24, 23, 6, 18], [13, 27, 3, 26, 20, 2]
[5], [7, 12], [9, 16, 4], [11, 2, 18, 22], [10, 21, 19, 1, 23], [17, 27, 6, 25, 26, 3]
[5], [7, 12], [11, 18, 6], [13, 2, 20, 14], [10, 23, 21, 1, 15], [17, 27, 4, 25, 24, 9]
[5], [7, 12], [13, 20, 8], [10, 23, 3, 11], [14, 24, 1, 4, 15], [16, 2, 26, 25, 21, 6]
[5], [8, 13], [6, 14, 1], [9, 3, 17, 16], [15, 24, 21, 4, 20], [11, 26, 2, 23, 27, 7]
[5], [8, 13], [11, 19, 6], [12, 1, 20, 14], [9, 21, 22, 2, 16], [15, 24, 3, 25, 23, 7]
[5], [8, 13], [11, 19, 6], [12, 1, 20, 14], [10, 22, 23, 3, 17], [16, 26, 4, 27, 24, 7]
[5], [9, 14], [8, 17, 3], [10, 18, 1, 4], [12, 2, 20, 19, 15], [13, 25, 27, 7, 26, 11]
[5], [9, 14], [11, 20, 6], [12, 1, 21, 15], [10, 22, 23, 2, 17], [16, 26, 4, 27, 25, 8]
[5], [9, 14], [12, 21, 7], [13, 1, 22, 15], [10, 23, 24, 2, 17], [16, 26, 3, 27, 25, 8]
[6], [7, 13], [9, 16, 3], [10, 1, 17, 20], [8, 18, 19, 2, 22], [15, 23, 5, 24, 26, 4]
[6], [7, 13], [11, 18, 5], [12, 1, 19, 14], [8, 20, 21, 2, 16], [15, 23, 3, 24, 26, 10]
[6], [7, 13], [11, 18, 5], [12, 1, 19, 14], [16, 4, 3, 22, 8], [9, 25, 21, 24, 2, 10]
[6], [8, 14], [9, 17, 3], [10, 19, 2, 5], [11, 1, 20, 18, 13], [15, 26, 27, 7, 25, 12]
[6], [8, 14], [10, 18, 4], [9, 19, 1, 5], [12, 3, 22, 21, 16], [15, 27, 24, 2, 23, 7]
[6], [8, 14], [10, 18, 4], [11, 1, 19, 15], [9, 20, 21, 2, 17], [16, 25, 5, 26, 24, 7]
[6], [8, 14], [11, 19, 5], [12, 1, 20, 15], [9, 21, 22, 2, 17], [16, 25, 4, 26, 24, 7]
[6], [9, 15], [11, 20, 5], [12, 1, 21, 16], [13, 25, 24, 3, 19], [14, 27, 2, 26, 23, 4]
[6], [10, 16], [8, 18, 2], [9, 1, 19, 17], [12, 21, 22, 3, 20], [14, 26, 5, 27, 24, 4]
[7], [6, 13], [9, 15, 2], [12, 3, 18, 20], [10, 22, 19, 1, 21], [17, 27, 5, 24, 25, 4]
[7], [6, 13], [10, 16, 3], [11, 1, 17, 14], [12, 23, 22, 5, 19], [15, 27, 4, 26, 21, 2]
[7], [6, 13], [11, 17, 4], [12, 1, 18, 14], [10, 22, 23, 5, 19], [15, 25, 3, 26, 21, 2]
[7], [8, 15], [11, 19, 4], [10, 21, 2, 6], [12, 22, 1, 3, 9], [17, 5, 27, 26, 23, 14]
[7], [8, 15], [12, 20, 5], [9, 21, 1, 6], [11, 2, 23, 22, 16], [14, 25, 27, 4, 26, 10]
[7], [9, 16], [11, 20, 4], [12, 1, 21, 17], [10, 22, 23, 2, 19], [15, 25, 3, 26, 24, 5]
[7], [10, 17], [11, 21, 4], [13, 2, 23, 19], [9, 22, 24, 1, 20], [16, 25, 3, 27, 26, 6]
[8], [5, 13], [9, 14, 1], [11, 2, 16, 17], [10, 21, 19, 3, 20], [15, 25, 4, 23, 26, 6]
[8], [5, 13], [9, 14, 1], [11, 2, 16, 15], [10, 21, 19, 3, 18], [17, 27, 6, 25, 22, 4]
[8], [6, 14], [9, 15, 1], [12, 3, 18, 19], [11, 23, 20, 2, 21], [16, 27, 4, 24, 26, 5]
[8], [6, 14], [9, 15, 1], [12, 3, 18, 17], [11, 23, 20, 2, 19], [16, 27, 4, 24, 26, 7]
[8], [7, 15], [10, 17, 2], [11, 1, 18, 16], [14, 3, 4, 22, 6], [26, 12, 9, 5, 27, 21]
[8], [7, 15], [12, 19, 4], [9, 21, 2, 6], [10, 1, 22, 20, 14], [16, 26, 27, 5, 25, 11]
[8], [9, 17], [12, 21, 4], [13, 1, 22, 18], [10, 23, 24, 2, 20], [16, 26, 3, 27, 25, 5]
[9], [6, 15], [11, 17, 2], [12, 1, 18, 16], [8, 20, 21, 3, 19], [13, 5, 25, 4, 7, 26]
[9], [6, 15], [11, 17, 2], [12, 1, 18, 16], [10, 22, 21, 3, 19], [14, 4, 26, 5, 8, 27]

[5], [8, 13], [14, 22, 9], [15, 29, 7, 16], [19, 4, 33, 26, 10], [12, 31, 35, 2, 28, 18], [20, 32, 1, 36, 34, 6, 24]
[5], [8, 13], [15, 23, 10], [14, 29, 6, 16], [18, 4, 33, 27, 11], [12, 30, 34, 1, 28, 17], [20, 32, 2, 36, 37, 9, 26]
[5], [8, 13], [15, 23, 10], [14, 29, 6, 16], [18, 4, 33, 27, 11], [12, 30, 34, 1, 28, 17], [20, 32, 2, 36, 35, 7, 24]
[5], [8, 13], [15, 23, 10], [16, 1, 24, 14], [11, 27, 28, 4, 18], [19, 30, 3, 31, 35, 17], [25, 6, 36, 33, 2, 37, 20]
[6], [8, 14], [15, 23, 9], [11, 26, 3, 12], [13, 2, 28, 31, 19], [17, 30, 32, 4, 35, 16], [24, 7, 37, 5, 1, 36, 20]
[6], [9, 15], [11, 20, 5], [12, 1, 21, 16], [13, 25, 24, 3, 19], [14, 27, 2, 26, 23, 4], [22, 8, 35, 33, 7, 30, 34]
[6], [9, 15], [13, 22, 7], [14, 1, 23, 16], [11, 25, 26, 3, 19], [18, 29, 4, 30, 27, 8], [20, 2, 31, 35, 5, 32, 24]
[6], [11, 17], [13, 24, 7], [16, 3, 27, 20], [15, 31, 28, 1, 21], [18, 33, 2, 30, 29, 8], [22, 4, 37, 35, 5, 34, 26]
[7], [6, 13], [10, 16, 3], [15, 5, 21, 18], [12, 27, 22, 1, 19], [17, 29, 2, 24, 23, 4], [25, 8, 37, 35, 11, 34, 30]
[7], [8, 15], [10, 18, 3], [14, 4, 22, 19], [13, 27, 23, 1, 20], [16, 29, 2, 25, 26, 6], [21, 5, 34, 36, 11, 37, 31]
[7], [8, 15], [13, 21, 6], [11, 24, 3, 9], [16, 5, 29, 26, 17], [19, 35, 30, 1, 27, 10], [18, 37, 2, 32, 31, 4, 14]
[7], [9, 16], [13, 22, 6], [17, 30, 8, 14], [19, 2, 32, 24, 10], [12, 31, 33, 1, 25, 15], [23, 35, 4, 37, 36, 11, 26]
[7], [9, 16], [13, 22, 6], [17, 30, 8, 14], [19, 2, 32, 24, 10], [15, 34, 36, 4, 28, 18], [20, 35, 1, 37, 33, 5, 23]
[7], [10, 17], [11, 21, 4], [12, 1, 22, 18], [13, 25, 24, 2, 20], [15, 28, 3, 27, 29, 9], [23, 8, 36, 33, 6, 35, 26]
[7], [11, 18], [12, 23, 5], [13, 1, 24, 19], [14, 27, 26, 2, 21], [16, 30, 3, 29, 31, 10], [22, 6, 36, 33, 4, 35, 25]
[8], [7, 15], [12, 19, 4], [17, 29, 10, 14], [18, 1, 30, 20, 6], [13, 31, 32, 2, 22, 16], [21, 34, 3, 35, 33, 11, 27]
[8], [10, 18], [12, 22, 4], [15, 27, 5, 9], [16, 1, 28, 23, 14], [13, 29, 30, 2, 25, 11], [19, 32, 3, 33, 31, 6, 17]
[8], [10, 18], [15, 25, 7], [12, 27, 2, 9], [13, 1, 28, 26, 17], [16, 3, 4, 32, 6, 23], [14, 30, 33, 37, 5, 11, 34]
[8], [10, 18], [15, 25, 7], [12, 27, 2, 9], [13, 1, 28, 26, 17], [16, 3, 4, 32, 6, 23], [20, 36, 33, 37, 5, 11, 34]
[8], [10, 18], [15, 25, 7], [16, 1, 26, 19], [11, 27, 28, 2, 21], [17, 6, 33, 5, 3, 24], [14, 31, 37, 4, 9, 12, 36]
[8], [11, 19], [9, 20, 1], [17, 26, 6, 7], [13, 30, 4, 10, 3], [18, 5, 35, 31, 21, 24], [14, 32, 37, 2, 33, 12, 36]
[8], [11, 19], [13, 24, 5], [14, 1, 25, 20], [12, 26, 27, 2, 22], [17, 29, 3, 30, 28, 6], [16, 33, 4, 7, 37, 9, 15]
[8], [11, 19], [13, 24, 5], [14, 1, 25, 20], [12, 26, 27, 2, 22], [18, 30, 4, 31, 29, 7], [21, 3, 33, 37, 6, 35, 28]
[8], [12, 20], [9, 21, 1], [17, 26, 5, 6], [11, 28, 2, 7, 13], [15, 4, 32, 34, 27, 14], [16, 31, 35, 3, 37, 10, 24]
[8], [14, 22], [12, 26, 4], [19, 31, 5, 9], [20, 1, 32, 27, 18], [13, 33, 34, 2, 29, 11], [23, 36, 3, 37, 35, 6, 17]
[9], [6, 15], [11, 17, 2], [12, 1, 18, 20], [10, 22, 23, 5, 25], [16, 26, 4, 27, 32, 7], [24, 8, 34, 30, 3, 35, 28]
[9], [7, 16], [10, 17, 1], [12, 2, 19, 18], [13, 25, 23, 4, 22], [15, 28, 3, 26, 30, 8], [21, 6, 34, 31, 5, 35, 27]
[9], [7, 16], [11, 18, 2], [12, 1, 19, 17], [13, 25, 24, 5, 22], [15, 28, 3, 27, 32, 10], [21, 6, 34, 31, 4, 36, 26]
[9], [7, 16], [13, 20, 4], [18, 31, 11, 15], [19, 1, 32, 21, 6], [14, 33, 34, 2, 23, 17], [22, 36, 3, 37, 35, 12, 29]
[9], [8, 17], [11, 19, 2], [12, 1, 20, 18], [14, 26, 25, 5, 23], [15, 29, 3, 28, 33, 10], [21, 6, 35, 32, 4, 37, 27]
[9], [10, 19], [14, 24, 5], [16, 30, 6, 11], [18, 2, 32, 26, 15], [13, 31, 33, 1, 27, 12], [21, 34, 3, 36, 35, 8, 20]
[9], [11, 20], [13, 24, 4], [17, 30, 6, 10], [18, 1, 31, 25, 15], [14, 32, 33, 2, 27, 12], [21, 35, 3, 36, 34, 7, 19]
[10], [7, 17], [11, 18, 1], [13, 2, 20, 19], [9, 22, 24, 4, 23], [16, 25, 3, 27, 31, 8], [21, 5, 30, 33, 6, 37, 29]
[10], [8, 18], [13, 21, 3], [17, 30, 9, 12], [19, 2, 32, 23, 11], [15, 34, 36, 4, 27, 16], [20, 35, 1, 37, 33, 6, 22]
[10], [9, 19], [13, 22, 3], [17, 30, 8, 11], [18, 1, 31, 23, 12], [16, 34, 35, 4, 27, 15], [20, 36, 2, 37, 33, 6, 21]
[10], [11, 21], [13, 24, 3], [15, 28, 4, 7], [16, 1, 29, 25, 18], [14, 30, 31, 2, 27, 9], [22, 36, 6, 37, 35, 8, 17]
[11], [7, 18], [12, 19, 1], [14, 2, 21, 20], [9, 23, 25, 4, 24], [17, 26, 3, 28, 32, 8], [27, 10, 36, 33, 5, 37, 29]
[11], [7, 18], [12, 19, 1], [14, 2, 21, 20], [13, 27, 25, 4, 24], [17, 30, 3, 28, 32, 8], [23, 6, 36, 33, 5, 37, 29]
[11], [8, 19], [14, 22, 3], [15, 29, 7, 10], [16, 1, 30, 23, 13], [17, 33, 32, 2, 25, 12], [20, 37, 4, 36, 34, 9, 21]
[11], [9, 20], [12, 21, 1], [15, 27, 6, 7], [17, 2, 29, 23, 16], [13, 30, 32, 3, 26, 10], [22, 35, 5, 37, 34, 8, 18]

[2], [12, 14], [13, 25, 11], [18, 31, 6, 17], [19, 1, 32, 26, 9], [15, 34, 35, 3, 29, 20], [23, 38, 4, 39, 36, 7, 27], [28, 5, 43, 47, 8, 44, 37, 10]
[3], [9, 12], [16, 25, 13], [18, 2, 27, 14], [15, 33, 35, 8, 22], [19, 34, 1, 36, 28, 6], [24, 5, 39, 40, 4, 32, 26], [17, 41, 46, 7, 47, 43, 11, 37]
[5], [7, 12], [13, 20, 8], [17, 30, 10, 18], [22, 39, 9, 19, 1], [25, 3, 42, 33, 14, 15], [16, 41, 44, 2, 35, 21, 6], [29, 45, 4, 48, 46, 11, 32, 38]
[5], [7, 12], [13, 20, 8], [17, 30, 10, 18], [22, 39, 9, 19, 1], [25, 3, 42, 33, 14, 15], [16, 41, 44, 2, 35, 21, 6], [29, 45, 4, 48, 46, 11, 32, 26]
[5], [9, 14], [17, 26, 12], [15, 32, 6, 18], [23, 8, 40, 34, 16], [13, 36, 44, 4, 38, 22], [24, 37, 1, 45, 41, 3, 25], [35, 11, 48, 47, 2, 43, 46, 21]
[5], [10, 15], [14, 24, 9], [18, 32, 8, 17], [22, 4, 36, 28, 11], [12, 34, 38, 2, 30, 19], [23, 35, 1, 39, 37, 7, 26], [29, 6, 41, 42, 3, 40, 47, 21]
[5], [10, 15], [14, 24, 9], [18, 4, 28, 19], [12, 30, 34, 6, 25], [20, 32, 2, 36, 42, 17], [27, 7, 39, 37, 1, 43, 26], [13, 40, 47, 8, 45, 46, 3, 29]
[5], [11, 16], [18, 29, 13], [17, 35, 6, 19], [21, 4, 39, 33, 14], [15, 36, 40, 1, 34, 20], [23, 38, 2, 42, 41, 7, 27], [32, 9, 47, 45, 3, 44, 37, 10]
[5], [13, 18], [17, 30, 12], [21, 38, 8, 20], [25, 4, 42, 34, 14], [15, 40, 44, 2, 36, 22], [26, 41, 1, 45, 43, 7, 29], [32, 6, 47, 48, 3, 46, 39, 10]
[6], [8, 14], [16, 24, 10], [19, 3, 27, 17], [12, 31, 28, 1, 18], [21, 33, 2, 30, 29, 11], [25, 4, 37, 35, 5, 34, 23], [15, 40, 44, 7, 42, 47, 13, 36]
[6], [9, 15], [13, 22, 7], [14, 1, 23, 16], [11, 25, 26, 3, 19], [18, 29, 4, 30, 27, 8], [20, 2, 31, 35, 5, 32, 24], [21, 41, 43, 12, 47, 42, 10, 34]
[6], [10, 16], [17, 27, 11], [20, 3, 30, 19], [14, 34, 37, 7, 26], [21, 35, 1, 38, 31, 5], [25, 4, 39, 40, 2, 33, 28], [18, 43, 47, 8, 48, 46, 13, 41]
[7], [10, 17], [15, 25, 8], [13, 28, 3, 11], [18, 5, 33, 30, 19], [21, 39, 34, 1, 31, 12], [20, 41, 2, 36, 35, 4, 16], [26, 6, 47, 45, 9, 44, 48, 32]
[7], [10, 17], [15, 25, 8], [13, 28, 3, 11], [18, 5, 33, 30, 19], [21, 39, 34, 1, 31, 12], [20, 41, 2, 36, 35, 4, 16], [26, 6, 47, 45, 9, 44, 40, 24]
[8], [13, 21], [12, 25, 4], [19, 31, 6, 10], [22, 3, 34, 28, 18], [14, 36, 39, 5, 33, 15], [23, 37, 1, 40, 35, 2, 17], [32, 9, 46, 47, 7, 42, 44, 27]
[8], [14, 22], [15, 29, 7], [20, 35, 6, 13], [21, 1, 36, 30, 17], [19, 40, 39, 3, 33, 16], [23, 42, 2, 41, 44, 11, 27], [28, 5, 47, 45, 4, 48, 37, 10]
[9], [7, 16], [12, 19, 3], [17, 29, 10, 13], [22, 5, 34, 24, 11], [15, 37, 42, 8, 32, 21], [26, 41, 4, 46, 38, 6, 27], [28, 2, 43, 47, 1, 39, 45, 18]
[9], [8, 17], [20, 28, 11], [22, 2, 30, 19], [13, 35, 37, 7, 26], [23, 36, 1, 38, 31, 5], [27, 4, 40, 41, 3, 34, 29], [15, 42, 46, 6, 47, 44, 10, 39]
[9], [10, 19], [15, 25, 6], [18, 33, 8, 14], [20, 2, 35, 27, 13], [16, 36, 38, 3, 30, 17], [21, 37, 1, 39, 42, 12, 29], [28, 7, 44, 43, 4, 46, 34, 5]
[9], [12, 21], [16, 28, 7], [18, 34, 6, 13], [20, 38, 4, 10, 23], [22, 2, 40, 36, 26, 3], [17, 39, 41, 1, 37, 11, 14], [27, 44, 5, 46, 45, 8, 19, 33]
[9], [12, 21], [20, 32, 11], [15, 35, 3, 14], [25, 40, 5, 8, 22], [26, 1, 41, 36, 28, 6], [18, 44, 43, 2, 38, 10, 16], [30, 48, 4, 47, 45, 7, 17, 33]
[11], [9, 20], [15, 24, 4], [12, 27, 3, 7], [17, 5, 32, 29, 22], [16, 33, 38, 6, 35, 13], [18, 34, 1, 39, 45, 10, 23], [26, 8, 42, 41, 2, 47, 37, 14]
[11], [9, 20], [19, 28, 8], [13, 32, 4, 12], [18, 5, 37, 33, 21], [17, 35, 40, 3, 36, 15], [24, 41, 6, 46, 43, 7, 22], [25, 1, 42, 48, 2, 45, 38, 16]
[12], [11, 23], [17, 28, 5], [15, 32, 4, 9], [20, 35, 3, 7, 16], [25, 45, 10, 13, 6, 22], [27, 2, 47, 37, 24, 30, 8], [19, 46, 48, 1, 38, 14, 44, 36]

[giobimbo]

@Quelo: più o meno sono i ragionamenti che ho fatto anche io, comunque altri esempi fanno sempre comodo, grazie.

[Quelo]

Nel frattempo è emerso un r=8, m=44

Codice: Seleziona tutto

11
 8 19
16 24  5
18 34 10 15
22  4 38 28 13
14 36 40  2 30 17
23 37  1 41 39  9 26
29  6 43 44  3 42 33  7

Rer r=9 niente fino a m=57

[Quelo]

Ci abbiamo ragionato e sono emersi dei pattern che ci hanno permesso di ricavare una soluzione per r=9, m=62

Codice: Seleziona tutto

11 
15 26 
14 29  3 
25 39 10 13 
27  2 41 31 18 
16 43 45  4 35 17 
28 44  1 46 42 7 24 
34  6 50 51  5 47 54 30 
19 53 59  9 60 55  8 62 32

[Maurizio59]

Ci abbiamo ragionato e sono emersi dei pattern che ci hanno permesso di ricavare una soluzione per r=9, m=62
...

Il valore minimo di m per r = 9 è m = 59.
Questi valori di m formano la sequenza A226239 di OEIS.
Essa è: 1,3,6,10,15,22,33,44,59,76,101,125,158

[Quelo]

Interessante!
Non avevo dubbi che qualcuno avesse già affrontato la questione.
Con una discreta potenza di calcolo e con le giuste ottimizzazioni ha potuto testare la maggior parte della combinazioni, arrivando fino al 13° gradino.
Qui si è fermato perchè, come giustamente ci segnala, per indagare il 14° ci sarebbero voluti 27.000 anni.
A questo punto la sfida è trovare il minimo per r = 14 o almeno un valore vicino al minimo.

Dobbiamo sviluppare una strategia euristica.
Il primo passo è analizzare i risultati che abbiamo già.
Se disponiamo la sequenza nota su un grafico, vediamo che segue una curva regolare.
Excel suggerisce una polinomiale di terzo grado che approssima molto bene i risultati attesi.
Il minimo per r = 14 sarà intorno a m = 194

Un primo risultato lo abbiamo ottenuto, anche se molto lontano dal minimo.
Al momento possiamo dire che il minimo è uguale o inferiore a 434

Codice: Seleziona tutto

337	424	150	154	130	114	434	36	431	432	26	411	401	161
87	274	4	24	16	320	398	395	1	406	385	10	240	
187	270	20	8	304	78	3	394	405	21	375	230		
83	250	12	296	226	75	391	11	384	354	145			
167	238	284	70	151	316	380	373	30	209				
71	46	214	81	165	64	7	343	179					
25	168	133	84	101	57	336	164						
143	35	49	17	44	279	172							
108	14	32	27	235	107								
94	18	5	208	128									
76	13	203	80										
63	190	123											
127	67												
60													

[Quelo]

Ecco un nuovo risultato (r=14, m=246), questo è stato ottenuto semplicemente espandendo una soluzione da 13 gradini
Sicuramente non è ottimale ma è più vicina al minimo (statisticamente)
Soluzioni peggiorative dei gradini inferiori possono produrre soluzioni migliorative per quelli superiori

Codice: Seleziona tutto

174	58	197	219	61	212	216	59	213	234	78	221	246	131
116	139	22	158	151	4	157	154	21	156	143	25	115	
23	117	136	7	147	153	3	133	135	13	118	90		
94	19	129	140	6	150	130	2	122	105	28			
75	110	11	134	144	20	128	120	17	77				
35	99	123	10	124	108	8	103	60					
64	24	113	114	16	100	95	43						
40	89	1	98	84	5	52							
49	88	97	14	79	47								
39	9	83	65	32									
30	74	18	33										
44	56	15											
12	41												
29