Newsgroup: it.hobby.enigmi
Titolo: Dai, fate la differenza!

Un "ben ritrovati" a tutti! Tra i meandri della tesi, ogni tanto si 
affaccia qualche bella idea per qualche problemino di quelli che 
piacciono a noi :). Provate con questo!
Mi sono ispirato a un gioco dell'ultima Google Contest.
Il gioco è stato proposta anche su Google in questi giorni.
  _ _ _ _ _
|_|_|_|_|_|
|_|_|*|*|*|
|_|*|*|_|_|
|_|_|*|*|_|
|_|_|_|_|_|
Al quadrato sono state tolte le caselle segnate dall'asterisco.
Si deve riempire il rimanente spazio con i numeri tra 1 e 14, in modo 
che la distanza tra 1 e 2 sia minore della distanza tra 2 e 3, e che 
questa sia minore della distanza tra 3 e 4, e così via.
Il gioco non è banale, soprattutto data la sagomatura della forma.
Ma abbandoniamo questo vincolo per una generalizzazione che potrebbe 
essere carina.
Sia dato il quadrato NxN. Qual è il più grande numero D che sia 
possibile inserire nel quadrato in modo che ci siano tutti i numeri tra 
1 e D e che soddisfino la regola delle differenze discussa sopra?
Ad esempio:
N = 2 --> D = 3
  _ _
|1|2|
|3|_|
N = 3 --> D = 6
  _ _ _
|_|2|6|
|3|1|4|
|5|_|_|
N = 4 --> D = 10 = A
  _ _ _ _
|9|7|1|_|
|_|_|2|5|
|_|4|_|3|
|_|6|8|A|
D ha un tetto massimo che è "classico", nel senso che è il risultato di 
un noto problema di teoria dei numeri (non dico quale, però!) ma è 
possibile ricavarlo nuovamente. Tale tetto massimo è raggiungibile?
(Il primo problema sussiste già per N = 5 in cui D <= 15. Penso non sia 
possibile arrivare a 15, mentre la soluzione per il 14 è la stessa che 
si ottiene dal problema di Google...)
Esiste un modo per esprimere semplicemente D in funzione di N?
ciao!
Stefano

possibile arrivare a 15,
Quest'impossibilita` si dimostra al volo.
Con 5x5 la massima distanza per dritto e` 4, ergo le
distanze disponibili sono tutte e sole queste:
 1. 1x0
 2. 1x1
 3. 2x0
 4. 2x1
 5. 2x2
 6. 3x0
 7. 3x1
 8. 3x2
10. 3x3
 9. 4x0
11. 4x1
12. 4x2
13. 4x3
14. 4x4
Per esempio con 6x6 se ne avrebbero in piu` 6, in
generale: [n+k-1 sopra k] - 1 (perche' 0x0 non c'e`).
Ma la distanza radice 25 la becca anche la prima terna
pitagorica, dunque 19 max.
Poi pero` a vedere se si possono piazzare tutti e 19,
ma certamente di piu` no.
-- 
Ciao, rez	||  -- GNU/Linux 2.4.25 su Slackware 9.1  ||

ma certamente di piu` no.
Mi correggo: la distanza 19-ma vale per i numeri 19 -> 20,
dunque max=20.


 dunque max=20.
per lo stesso ragionamento, la 14-esima distanza nel caso 5x5 vale per 
il collegamento tra 14 e 15.
L'impossibilità non si dimostra come hai fatto tu, ma partendo da 15 e 
ricostruendo all'indietro. Le uniche scelte che si possono fare non sono 
vincolanti, visto che godono di una certa simmetria. e a un certo punto 
non è possibile proseguire nell'assegnamento dei numeri.
O almeno così mi è parso.
Ma 14 distanze prevedono l'inserimento di 15 numeri! ;-)
pazqo

ricostruendo all'indietro.
Ma che differenza c'e`? che tu lo faccia in un verso o
nell'altro di scriverle, il max e` sempre le combinazioni
con ripetizione di n+1 elementi: 0,1,2,..,n, a 2 a 2.
Ecco le combinazioni: 1x0, 1x1, 2x0,..,nxn.
Piuttosto questa va diminuita dei possibili duplicati,
come ho mostrato per le 5x0 e 4x3, cioe`: 
5x0=sqrt(5^2+0^2)=5 <-> 4x3=sqrt(4^2+3^2)=5,
non utilizzabili entrambi contemporaneamente.
E queste distanze duplicate non so/trovo un modo di
individuarle e scriverle in una formola generale.
Bisogna pensare alla storia degli interi somma di due
quadrati.. magari e` facile e immediato.


 non utilizzabili entrambi contemporaneamente.
come dicevo. ma questo è proprio quello che rende interessante (e 
difficile) il gioco :-)
comunque sul tabellone 5x5 ci sono 14 distanze (le indico al quadrato):
1-2   1,
2-3   1+1,
3-4   4,
4-5   1+4,
5-6   4+4,
6-7   9,
7-8   1+9,
8-9   4+9,
9-10  16,
10-11 1+16,
11-12 9+9,
12-13 16+4,
13-14 16+9,
14-15 16+16.
perché escludi il 15 a priori, come possibilità di inserimento? le 
distanze sono le stesse inserite da te...
ciao
Stefano

distanze sono le stesse inserite da te...
Ma no che non lo escludo, si vede che mi sono espresso
male.. lo ridico.
Con una nxn le DISTANZE sono d=n(n+1)/2 - 1, i NUMERI
inseribili sono invece uno in piu`: N=d+1=n(n+1), ma
a condizione che le distanze abbiano tutte un valore
distinto.



Credo di aver trovato una soluzione con D = 15 (in realtà le soluzioni
che ho trovato sono 48, ma credo che siano moltiplicate da riflessioni
e rotazioni).
Ecco la prima soluzione trovata:
  *  * 10  7 14
  8  5  2  * 12
  *  3  1  4  *
 13  *  *  6  *
 15 11  9  *  *
Mentre per il quadrato 6x6 sono fermo a D = 20 (808 soluzioni), ma ho
ancora qualche speranza.
Il primo quadrato che hai proposto (quello con le caselle bloccate) é
stato risolto? 
A proposito cose é il Google Contest? Dove é stato posto questo
problema (Google ?????)
-- 
Ciao, Dano

 problema (Google ?????)
Leggi qua: 
http://wpc.puzzles.com/google/
peccato averlo saputo tardi. si è ancora in tempo per iscriversi, ma
temo si difficile organizzarsi per tempo...
magari per il prossimo anno, sperando sia più vicino all'Italia!
ciao!
Stefano

 sbaglio?). Avevo fatto il conto a mano.
intendevo 6*7/2-1-1+1, quindi i numeri fino a 20, come dicevi tu. non
tentare oltre! :-)
hai un programmino che lavora su quadrati di ogni dimensione?
Stefano

hai un programmino che lavora su quadrati di ogni dimensione?
Si, ho scritto un programmino in C che si adatta a qualsiasi
dimensione, ma i tempi di calcolo si allungano parecchio.
Il quadrato 6x6 é stato completamente analizzato in circa 2,5 minuti;
adesso sono 10 minuti che sta lavorando sul quadrato 7x7 e per il
momento ha trovato soluzioni con 26 posizioni, ecco la prima:
 25  * 21 19 15  *  *  
 23  9 11  *  7  * 17
  * 13  5  2  *  *  *  
  *  *  3  1  4  *  * 
  *  *  *  8  6 12  *
  * 10 16  *  * 14 24
  *  *  * 18 20 22 26
Mi sembra di intravedere una sorta di ripetitività progressiva nelle
soluzioni....
-- 
Damiano (Dano)


Purtoppo non é così!
Il massimo per il quadrato 7*7 é solo di 26 (esempio che ho postato),
ho scansionato tutte le possibilità e non esiste alcuna soluzione con
27 posizioni.
Stessa situazione per il quadrato 8*8 non esiste alcuna soluzione con
34 posizioni (che é il massimo teorico), non ho ancora provato se
esiste una soluzione per 33 posizioni.
-- 
Ciao, Damiano

"Dano" <ju...@interpuntonet.it.invalid> wrote

Ho scritto anch'io un programmino e confermo che non ci sono soluzioni con 
il massimo teorico per N = 7 e almeno fino a N = 100.
E credo che la cosa sia anche facilmente verificabile. Se prendiamo ad 
esempio il quadrato 7 e partiamo dal fondo possiamo solo mettere i seguenti 
numeri nelle seguenti posizioni forzate (a parte r&r):
 27 25  .  .  .  .  .
 23  .  .  .  .  .  .
  .  .  .  .  .  .  .
  .  .  .  .  .  .  .
  .  .  .  .  .  . 22
  .  .  .  .  .  .  .
  .  .  .  .  . 24 26
Le distanze usate sono, nell'ordine:
6, 6
5, 6
4, 6
5, 5
3, 6
Ora si dovrebbe mettere il 21 a una distanza (4, 5) dal 22, ma il posto è 
già occupato dal 25.
Mi sembra che la stessa situazione si riproponga per tutti gli N >= 7. Forse 
non è difficile da dimostrare (se qualcuno con questo caldo ne avesse 
voglia...) oppure trovare un caso con N >= 7 in cui questo non si verifica.
Ciao
Giorgio 
Inviato da X-Privat.Org - Registrazione gratuita 
http://www.x-privat.org/join.php

 Esiste un modo per esprimere semplicemente D in funzione di N?
Ciao Stefano! :-)
Non so se esiste un modo semplice, però simulando ho trovato questi 
risultati. Riporto in fondo per N da 8 a 20 i valori di D, tra parentesi lo 
scarto rispetto al valore massimo teorico e la prima soluzione trovata.
Va detto che quando ci sono soluzioni, ce ne sono in numero notevole. Ad 
esempio per N = 9, il programma ne trova più di 16 milioni.
Per quanto riguarda l'andamento dello scarto tra D e il massimo teorico, la 
tendenza è a diventare sempre maggiore coll'aumentare di N.
Ciao
Giorgio
N=8 D=33 (-1)
 33 31 29  . 24  . 18 20
  . 22  .  .  6  8  . 26
  .  . 13 15  .  .  .  .
 27 17  5 11  .  .  .  .
  .  .  .  9  7  .  . 10
  .  4  1  .  .  .  .  .
 12  .  2  .  . 21 19 28
  .  3 14 25 23 16 30 32
N=9 D=40 (-2)
 40 38 32  .  5  .  .  . 27
 29 23 25 14 16 10  4  1 30
 36 12  6  8  . 19  .  2 21
 34  .  .  .  .  .  3  .  .
  .  .  .  .  .  .  .  .  .
 17  .  7  . 11  9  .  .  .
  .  . 15 13  .  .  .  . 33
  .  .  .  . 22 28 26  . 37
  . 24  .  . 31 18 20 35 39
N=10 D=47 (-4)
 47 45 30 14 16 37  . 33  .  .
 43 39  . 19  .  3 21  .  . 35
 41  . 26  . 12  .  2 28  .  .
  . 24  .  8  6  4  1  . 23  .
 13  .  .  .  .  .  .  . 17 31
  9 11 15  .  .  .  5  .  .  .
  . 32 22  .  7  .  .  .  .  .
  .  .  . 18 20  .  .  .  . 42
N=11 D=58 (-3)
 58 56 44 38 36 46  .  . 24  .  .
 54 50  .  7  . 34  . 30  .  .  .
 52  5  .  .  .  .  .  .  .  .  .
 48  . 28 26 20 18 10  . 32 42  .
  4  1 22  6  8  . 16  .  . 40 12
 31  2  .  .  .  .  .  .  .  .  .
  3  .  .  .  .  .  .  .  .  .  .
 41  .  .  .  .  .  9 11 23 25 49
 35  . 17 14  .  .  .  . 13  . 53
  . 39 33  . 37 19 21 29 15 51  .
  .  . 43 45  . 27  .  . 47 55 57
N=12 D=66 (-5)
 66 64 46 56 15 44 38 36  .  .  .  .
 62 58 54 40 42  . 17  .  .  .  .  .
 60 48  1  4  . 29  .  .  .  .  .  .
 50  .  2  9 11  . 25 23  . 31 34 51
 52  .  .  3  5 19  .  . 21  .  . 18
  . 32 16 14  .  .  . 27  .  .  . 47
  . 12  .  .  .  8  6  .  .  .  .  .
 26  .  . 10  .  .  .  .  .  .  .  .
 28  .  . 35  .  .  .  .  .  .  . 43
  .  .  .  . 22  .  7 37 39 49 53 61
 41  .  . 13 45 30 20 24  . 55 59  .
  .  .  .  .  .  .  . 33 57  . 63 65
N=13 D=77 (-6)
 77 75 61 67 51 53  7 33 16  .  .  .  .
 73 69 65  8 45 12 41  3  5 59  .  .  .
 71  .  . 23 39  1  2  . 55  .  . 47  .
  . 19 27 35 21  .  6  4  . 43  .  .  .
 63  9 11  . 17  .  .  . 25 31 29  .  .
 49  .  .  .  .  . 15 13  .  .  . 57  .
  . 32  .  .  .  .  .  .  .  .  .  .  .
  .  . 37  .  .  .  .  .  .  .  . 36 62
 22 10  .  .  .  .  .  .  .  . 34 38  .
 58 18 20 24  .  .  .  .  .  . 50  .  .
 54  . 42  . 26 28  . 14  . 40  . 64 72
  . 56  . 44 52  . 46  .  .  . 66 70  .
  .  .  .  . 60  .  .  . 48 68 30 74 76
N=14 D=87 (-7)
 87 85 51 77 69 71  . 65  .  . 29 31  .  .
 83 79 73 62  . 17  .  8  6 12  .  .  .  .
 81  .  . 33  .  .  .  . 48 37 55  .  .  .
 75 57  .  .  . 35  5  .  .  . 46  . 67  .
  .  .  .  . 39  9 11  .  7  .  .  .  .  .
 45 16 14 24  1  4  . 13  . 42 23  .  .  .
 26  . 19 21  2 28  .  . 18  . 44 50  .  .
 59  .  .  .  .  3  .  .  .  .  .  . 58  .
  .  .  .  .  . 10  .  .  . 32 30  . 60 63
 41  .  .  .  .  .  .  .  .  .  .  .  .  .
 34 49 54 15  .  .  .  .  .  .  .  . 74  .
  . 64 52  .  .  .  . 22  . 36 38  .  . 82
  . 20 43 66 25 47  .  .  . 40  . 76 80 53
  . 61 27 70 68  .  . 56 72  . 78  . 84 86
N=15 D=98 (-8)
 98 96 88 86 25 67  8 31  2  1 74  . 78  .  .
 94 90 84  . 49 19 15 76  5  3 46 62  . 44  .
 92  . 51 58 60  .  . 40 17  . 13 33  . 52 42
  . 56 53 35  9 11  .  7  .  4  6  .  .  .  .
 30 80  .  . 22  .  .  .  .  .  .  .  . 72  .
 82  . 65  .  .  .  .  .  .  .  .  .  .  .  .
 26 47  .  . 16 28  . 14 12  .  .  . 55  .  .
 71  . 37 24 10 18 20  .  .  . 23 36  .  .  .
  . 63  .  .  . 32  .  .  .  .  . 38  .  .  .
 21  .  .  .  .  .  . 43  .  .  . 48  . 70 66
 69 73 39  .  .  .  .  . 34  .  .  .  . 68 83
  .  .  .  .  .  .  .  . 50  . 41  . 45 64 89
 29  .  .  .  .  .  .  .  .  .  .  .  . 85 93
  .  . 27  .  .  .  . 57  . 61  .  . 81 91 75
  .  .  . 59 54  .  .  .  .  . 87 79 77 95 97
N=16 D=113 (-7)
 113 111  93 105  99   .  73  82   9  91  67  24   .   .   .   .
 109  95 103   1  78   .  26   .  22   .   .   .   .   .  85   .
 107 101   .   2   .   .   .  64  31  76   .   .   .   .   .  61
  97  53   3   .   .  45   8  41  16   .   .   .   .   .   .   .
   .  36  59  62  33   .   .   .  10  39  37   .  47   .  58   .
  88   .   4   .  12  50   .   .   .   .  43   .   .   .   .  80
  86  19   .   .  21   7   .   .   .   .   .  55   .   .   .  87
  70   .  48   5  17   .   .   .   .   .  25  23  34   .   .  89
  68  84   .   .  27   .  15  11   .   .   .   .   .  69   .   .
  56  66  13   .  30   6   .   .   .   .   .   .  29  71   .  96
   .   .   .   .   .   .   .   .   .   .  32   .   .   .   .  74
   .   .   .   .   .   .   .   .   .   .   .   .   .  94   .   .
  72  18  20  42  40  35   .   .   .   .   .   .   .   .   .  83
   .  90   .   .  44  14   .  46   .   .  60  38   .  65   . 108
  52   .  75  54  81   .   .   .   .   .  63  51   . 100 104   .
   .   .   .   .  77  79  92  28   .  49  57  98 102 106 110 112
N=17 D=127 (-8)
 127 125  10 117 113 107  41   .   .  92  79  77  59   .   .   .   .
 123 119 115   .  19  86  88   .  57  75   .  27   .   .   .   .   .
 121 105 109   .  23  25   .  84  47  43  31   .   .  96  90   .   .
   .   .  13  15   7  66   .   .   .   .   .   .   . 102   .   .   .
   .   .   9  11  68   .  33  64  37   .   .  39  49   .  73   .  94
 111  81  70   .  35   .   .   .   .   .   .   .   .  53  51   .   .
   .   .   .  30   6   8   1   4   .   .   .   .   .   .   .   .   .
  12   .  61  20  18   .   2   .   .   .   .   .   .   .   .  71   .
   .  22  14  55   .  16   5   3  28  26   .   .   .   .   .  82 100
   .   .  42  40  24   .   .   .   .   .   .   .   .  45  62   . 104
  99   .  72  44   .   .   .   .   .   .   .   .  32   .   .   .   .
  97   .   .  46   .   .   .   .   .   .   .   .   .   .  56   .  98
   .  17   .   .   .  48   .   .   .  34   .   .  58  60  67   . 110
 103   .   .   .   .  21   .   .  36  38   .   .   .   .   .   .  76
   . 101   .  29   .  74   .   .  50   .   .  78  80   .   . 112 122
  85  65   .   .   .  93  91   .   .   .   .   .   . 108 116 120   .
   .   .   .  83  63  87  95   .  89  69 106  54 114 118  52 124 126
N=18 D=140 (-8)
 140 138   . 132 126  92 114   .   .  18  20   . 109 103   .  76 106   .
 136 100 130 124  98   .  88   .   .   .  82  68   .   .   .   .   . 111
 134 128 122  85   5  48  27   .   .  96  90   .  66   .   .   .   .   .
 112 120 116   .  44  59   .  46  25   .  36  38   .   .  64   .   .   .
   .  34   .  42  40   4   6  13  15  57   .   .  94   .   .   .  80   .
 107   .  77   .  62  73  17   .  51  53   .   .   .   .   .   .  78   .
 118   .  79   .   1   3   .   .  21  19  32   .   .   .   .   .   .  70
   .  10   .  75   2   .   7   .  30   .   .   .  55   .   .   . 101  86
   .   .   .   8  71  12   .   .   .   .   .   .   .   .   .   .   .   .
   .   . 105  28  26   .   .  14   .   .  16   .   .   .   .   .  84   .
 102   .   .   .   .   .   .  24   .   .   .   .  49   .   .   .   .   .
   .   9  11  67  22   .  35   .   .   .  43   .   .   .   .   .   .  72
   .   .  47   .  33   .   .   .   .  39  37   .   .  60   .   .   . 119
   .   .  83   .   .  45  69  41   .   .   .   .   .   .   .   .   .   .
   .   .  50  56   .   .   .   .  65   .   .   .  31   .   .   . 117   .
   .  93  91   .  54  58   .  81  29   .   .  63   .   .  74 115 125 135
   .   .  95   .  89  87   .   .  52   .   .   .   .   . 121 127 131 104
   .   .  61  99  97   .   .  23   .   . 113 110 108 123 129 133 137 139
N=19 D=154 (-11)
 154 152   . 144   . 138   . 122  75 132 120  36  38  61   . 113   .   .   .
 150 146  34   . 136   1  97  99   .   .   .   .   . 109 103   .   . 116   .
 148 140   . 105  63   2  71   7   .  11   9   .   . 124   . 101   .  92 118
 142  65  88  73   3   5   .   .  30   .   .  32   .   .   .   .   .   .   .
   .   .  23  25   .   .  90  16  14  84   .  69   .   .  52   .   .   .   .
   .  58  60  28   4   .  12   6   8  41  54   .   .   .   . 130   .   .   .
   . 107  93   .   .   .   .   .  50   .  10  56  86   .  67   .   .   .   .
 134  95  77  81   .   .  19   .   .   .   .   .  43  45   .   .  78   .   .
   .   .  79  17   .   .   .  35   .   .   .  48   .   .   .   .   . 128 111
   .   .   .  46   .  33   .   .  13  15   .  37   .   .  39   .   .   .   .
   . 112 115   .   .  22   .  26   .   .   .   .   .   .   .   .   .  82   .
   .   .  24   .   .   .   .   .  29  31   .   .   .   .   .   .   . 106 126
  27   .   .   .   .   .   .   .   .   .   .  62   .   .   .  76   .   .   .
   .   .  55   . 117   .  18  20   .   .   .   .  74   .   .   .   .   .   .
   .   . 110   . 102  42  40  64   .   .   .   .   .   .   .  96   .   . 141
 125  21   .   .  70  66   .   .   .  72   .   .   .   .  51  53   .   . 135
 127   .   .   .  49  57  68   .   .   .   .   .   .   .   .   .   . 137 149
 131  59  85   .   .   .  98   .   . 100 104   .  44  94  91   . 143 147 114
  89 129   .  87 123  83   .   .  47 121 119   .  80 108 139 145 133 151 153
N=20 D=169 (-11)
 169 167 114 161 153  72 147   .  29   1   2   .   .   .   .  90   .   . 140 
.
 165   . 159   . 145  24 120 122  63   4 128   3 124 134   .  98   . 117   . 
142
 163 155  74  81   .   . 107   5  26   .  96  65  34   .   .   .   .   .   . 
.
 157   . 149  18  20   .   . 103  10   .  49   .   .  76   .   .   .   .   . 
.
   . 151  60  32  11   6 101   .  83   . 105  53  51  94   .   . 126   .   . 
115
   .   .  58   .   .  85  67   .   .   .   .   .   .   .  59   .   .   .   . 
.
 118  89   .  28   .   .   .   .   .   .   .   .  56   .   .   .  44   .   . 
.
 143  87   .  42  40   7  45  12   9   .   .   .   .   .   .   .   .   .   . 
112
  77   .  91  38  25  23  17   .  30   .   .   .   .  47  78   .  88   . 130 
.
  79  54 111  19   .   .  21  35   .   .  27   .   .  61   .   .   .   .   . 
136
   . 139  69   .   .   .   8   .   .  33   .   .   .   .   .   .   .   .   . 
.
   .  62   .  48   .  13   .   .   .   .   .   .   .   .  80  70   .  92   . 
.
   .  31  16   .   .   .   .   .   .   .   .  73   .   .   .   .   .   .   . 
.
 137   .  71   . 116  64  50   .   .   .   .   .   .   .   .   .   .   .   . 
.
 131 109  22   . 141   .   .   .   .   .  43   .   .   .   .  66   .   . 108 
132
 133   .  93   .   .   .  75   .   .  39   .   .  52   .  68   .   .   . 110 
156
  82 135   .  95   .  14  57  41   .   .   .   .   .   .   .   .   . 102 144 
152
  15   .  37 125   . 113   .   .  46  55   .  36   .   . 119  97  99   . 150 
164
   . 106 129   .   .   .   .   .   .   .   .   .  84   .   .   .   . 148 160 
138
 100   .   . 104   . 127 121   .   . 123  86   .   .   . 146 154 158 162 166 
168 
