[HOME - BASE Cinque - Appunti di Matematica ricreativa]
Oh no! Sei ancora in tempo a tornare indietro!
Se però vuoi affrontare a tutti i costi il problema di questa pagina, devo almeno avvertirti che:
Per affrontare il Problema Impossibile senza correre il rischio di cadere in una confusione mentale senza ritorno, è necessaria un'adeguata preparazione. Questa può essere raggiunta risolvendo i problemi dal n. 2 al n. 6.
Ed ora... in bocca al lupo!
1. Il Problema Impossibile
Il professor Somma ed il professor Prodotto sono due
logici perfetti, capaci di dedurre quasi istantaneamente
tutte le verità da qualunque sistema di assiomi.
Un giorno uno studente incontra i due professori al bar
dell'università e gli chiede: "Mi permettete una
domanda?"
"Certo!"
"Ho scelto due numeri interi compresi tra 2 e 100 e
questa è la loro somma."
Lo studente dà un foglio al prof. Somma. L'altro professore
non vede cosa c'è scritto.
Lo studente aggiunge: "E questo è il loro prodotto."
Dà un altro foglio al professor Prodotto. Il prof. Somma,
naturalmente, non vede cosa c'è scritto.
"Sapete dirmi quali numeri ho pensato?"
E dicono in coro i due numeri che ha pensato lo studente.
Lo studente indietreggia con gli occhi spalancati e fugge dal
bar.
Quali sono i due numeri?
2. Somma e prodotto
La somma di due numeri è 20 e il loro prodotto è
91.
Sai trovare i due numeri?
3. Prodotto 35
Si sa che due numeri interi sono stati scelti a caso
nell'intervallo 2 - 20 e che il loro prodotto è 35.
Quali sono i due numeri?
4. Prodotto 36
Si sa che due numeri interi sono stati scelti a caso
nell'intervallo 2 - 20 e che il loro prodotto è 36.
Quali sono i due numeri?
5. Somma 19
Si sa che due numeri interi sono stati scelti a caso
nell'intervallo 1 - 10 e che la loro somma è 19.
Quali sono i due numeri?
6. Somma 12
Si sa che due numeri interi sono stati scelti a caso
nell'intervallo 1 - 10 e che la loro somma è 12
Quali sono i due numeri?
Risposte & riflessioni
Prima risolviamo i problemi di allenamento, poi passeremo al problema impossibile.
2. Somma e prodotto
Si risolve l'equazione:
x2 - 20x + 91 = 0
e si ottiene:
x1 = 7
x2 = 13
che sono i numeri cercati.
3. Prodotto 35
35 = 7x5
4. Prodotto 36
Non possono essere determinati perché:
36 = 2x18 = 3x12 = 4x9 = 6x6
5. Somma 19
Dato che i numeri si trovano nell'intervallo 1-10,
si può concludere che:
19 = 10+9
6. Somma 12
Non possono essere determinati perché:
12 = 2+10 = 3+9 = 4+8 = etc.
1. Il problema impossibile
Premetto che tutti i numeri di cui si parla nel seguito sono
interi positivi.
Perciò, con la parola "numero" si intende "numero
intero positivo".
Chiamo x, y i numeri scelti dallo studente.
Chiamo s la loro somma e p il loro prodotto.
s = x + y
p = x*y
Denoto con l'espressione [a-b] il range (o intervallo) nel
quale sono stati scelti i due numeri x e y.
Suppongo che il range sia il medesimo per entrambi i numeri.
Ciò significa che i numeri x e y sono tali che:
a <= x <= b
a <= y <= b
Poiché, nel caso di questo problema, il range è [2-100],
si può dire che:
2 <= x <= 100
2 <= y <= 100
Le seguenti considerazioni sono così articolate:
1. Dimostrazione che s = 17 e p = 52 costituiscono
una soluzione corretta.
N.B. Posso aggiungere che il range minimo a partire dal quale
esiste una soluzione é [2-62].
2. Dimostrazione che (ad esempio) s = 10 e p = 24 NON costituiscono una soluzione del problema.
I punti 1. e 2. servono a prendere dimestichezza con la logica del problema.
3. Risoluzione vera e propria del problema, ossia descrizione dettagliata del procedimento da seguire per trovare s, p e quindi x, y basandosi soltanto sul range e sul dialogo tra i due professori.
4. Dimostrazione che s = 17, p = 52, x = 13, y = 4 NON sono una soluzione nel range [2-20]. Questo fatto può sembrare strano perché in effetti x, y appartengono al range.
5. Presentazione di un programma in BASIC che risolve il problema dopo aver chiesto il range.
Ed ecco lo sviluppo dei 5 punti.
1. Dimostrazione che s = 17 e p = 52 costituiscono una soluzione corretta.
Seguiamo attentamente il dialogo, mettendoci, di volta in volta, nei panni di uno dei due professori.
----------
Mettiamoci nei panni del prof. Prodotto.
Egli sa che x*b = 52
Egli NON può determinare x e y perché, nel range del
problema:
52 = 2*26
52 = 4*13
Perciò dice: "Non posso determinare i due numeri."
----------
Pausa di riflessione.
Definiamo P-ambiguo (PRODOTTO-ambiguo) nel
range [a-b] un numero intero che può essere scomposto in due
fattori in più di un modo. I fattori devono essere scelti
nel range [a-b].
Esempi:
36 è P-ambiguo nel range [2-14]: 36 = 6*6 = 2*12
36 non è P-ambiguo nel range [2-11]: 36 = 6*6
35 non è P-ambiguo nel range [2-10]: 35 = 7*5
35 è P-ambiguo nel range [1-40]: 35 = 1*35 = 7*5
----------
Mettiamoci ora nei panni del prof. Somma.
Egli sa che x + y = 17
Egli NON può determinare x e y perché:
17 = 15+2 = 14+3 = 13+4 = 12+5 = 11+6 = 10+7 = 9+8
INOLTRE, calcolando i prodotti, si rende conto che:
15*2 = 30 = 10*3 = 6*5
14*3 = 42 = 7*6
13*4 = 52 = 26*2
12*5 = 60 = 6*10 = 4*15 = 3*20 = 2*30
11*6 = 66 = 22*3 = 33*2
10*7 = 70 = 5*14 = 2*35
9*8 = 72 = 6*12 = 4*18 = 3*24 = 2*36
Egli, di conseguenza, CAPISCE che il prof. Prodotto deve
avere uno dei numeri indicati, cioè: 30, 42, 52, 60, 66, 70,
72.
Egli SI RENDE CONTO inoltre che CIASCUNO dei numeri
dell'elenco è P-ambiguo, cioè è scomponibile in due
fattori in più di un modo, perciò DEDUCE che il prof.
Prodotto non può essere in grado di determinare i suoi due
numeri.
Perciò dice: "Io lo sapevo che tu non potevi
determinare i due numeri."
----------
Pausa di riflessione.
Per capire il seguito è bene porsi la seguente domanda:
Quali altri numeri hanno la stessa proprietà del 17, NEL
RANGE DEL PROBLEMA?
Chiameremo SP-ambiguo (SOMMA-PRODOTTO-ambiguo)
un numero che ha la stessa proprietà del 17.
Precisiamo meglio la proprietà.
Un numero è detto SP-ambiguo se e solo se, scomponendo il
numero in tutte le possibili coppie di addendi e calcolando
il prodotto di ciascuna di tali coppie, si ottiene in ogni
caso un numero P-ambiguo.
Con un po' di pazienza (o con un semplice programma per
computer) si può verificare che i numeri SP-ambigui, nel
range [2-100] sono:
11, 17, 23, 27, 29, 35, 37, 41, 47, 53
Questo elenco sarà molto utile nel seguito.
----------
Mettiamoci ora nei panni del prof. Prodotto.
Siccome:
52 = 2*26
52 = 4*13
egli DEDUCE che il prof. Somma ha uno dei seguenti due numeri:
2+26 = 28
4+13 = 17
Ma ora ha anche UN'ALTRA INFORMAZIONE. Sa che il prof
Somma ha potuto dedurre che lui non era in grado di
determinare i due numeri.
Ciò gli permette di dedurre che il prof. Somma deve avere un
numero SP-ambiguo.
Questa informazione gli permette di ESCLUDERE che il prof.
Somma abbia il numero 28.
Infatti 28 NON E' SP-ambiguo e vediamo perché:
28 = 2+26 = 3+25 = ... = 23+5 = ...
In questo caso:
3*25 = 75 E' scomponibile in più di un modo, ad es 15*5
23*5 = 105 NON E' scomponibile in più di un modo NEL RANGE
DEL PROBLEMA
Perciò, se il prof. Somma avesse avuto il numero 28 non
avrebbe potuto trarre la sua deduzione.
Perciò egli DEDUCE che il prof. Somma ha il numero 17 e
da qui calcola i due numeri cercati:
p = 52, s = 17, x = 4, y = 13.
Quindi può dire: "Ora posso determinare i due numeri."
----------
Mettiamoci ora nei panni del prof. Somma.
Egli sa che il suo numero è 17.
Egli sa inoltre che il prof. Prodotto deve avere uno dei
numeri indicati, cioè: 30, 42, 52, 60, 66, 70, 72.
Ma ora ha anche UN'ALTRA INFORMAZIONE. Sa che il prof. Prodotto ha potuto dedurre che lui ha il numero 17.
Questa informazione gli permette di DEDURRE, esaminando
caso per caso, che il prof. Prodotto.
Esaminiamo tutti i casi.
NON HA il numero 30 perché:
30 = 15*2; 15+2 = 17
30 = 10*3; 10+3 = 13
30 = 6*5; 6+5 = 11
Se il prof. Prodotto avesse il numero 30, dovrebbe ipotizzare
che il prof. Somma potrebbe avere uno dei numeri: 17, 13, 11.
In questo caso il prof. Prodotto si fermerebbe di fronte al
fatto che 11 e 17 sono SP-ambigui. Egli infatti non saprebbe
quale scegliere.
NON HA il numero 42 perché
42 = 14*3; 14+3 = 17
42 = 6*7; 6+7 = 13
42= 2*21; 2+21 = 23
Se il prof. Prodotto avesse il numero 42 dovrebbe ipotizzare
che il prof. Somma potrebbe avere uno dei numeri: 17, 13, 23.
In questo caso il prof. Prodotto si fermerebbe di fronte al
fatto che 17 e 23 sono SP-ambigui. Egli infatti non saprebbe
quale scegliere.
HA il numero 52 perché
52 = 13*4; 13+4 = 17
52 = 26*2; 26+2 = 28
Come vedremo, 52 è l'unico numero, nel range del problema,
che CORRISPONDE ad UN SOLO NUMERO SP-ambiguo, cioè il 17.
NON HA il numero 60 perché
60 = 12*5; 12+5 = 17
60 = 6*10; 6+10 = 16
60 = 4*15; 4+15 = 19
60 = 3*20; 3+20 = 23
60 = 2*30; 2+30 = 32
In questo caso il prof. Prodotto si fermerebbe di fronte al
fatto che 17 e 23 sono SP-ambigui. Egli infatti non saprebbe
quale scegliere.
NON HA il numero 66 perché
66 = 11*6; 11+6 = 17
66 = 22*3; 22+3 = 25
66 = 33*2; 33+2 = 35
In questo caso il prof. Prodotto si fermerebbe di fronte al
fatto che 17 e 35 sono SP-ambigui. Egli infatti non saprebbe
quale scegliere.
NON HA il numero 70 perché
70 = 10*7; 10+7 = 17
70 = 5*14; 5+14 = 19
70 = 2*35; 2+35 = 37
In questo caso il prof. Prodotto si fermerebbe di fronte al
fatto che 17 e 37 sono SP-ambigui. Egli infatti non saprebbe
quale scegliere.
NON HA il numero 72 perché
72 = 9*8; 9+8 = 17
72 = 6*12; 6+12 = 18
72 = 4*18; 4+18 = 22
72 = 3*24; 3+24 = 27
72 = 2*36; 2+36 = 38
In questo caso il prof. Prodotto si fermerebbe di fronte al
fatto che 17 e 27 sono SP-ambigui. Egli infatti non saprebbe
quale scegliere.
2. Dimostrazione che (ad esempio) s = 10 e p = 24 NON costituiscono una soluzione del problema.
----------
Mettiamoci nei panni del prof. Prodotto.
Egli sa che x*y = 24
Egli NON può determinare x e y perché, nel range del
problema:
24 = 2*12
24 = 3*8
24 = 4*6
Perciò dice: "Non posso determinare i due numeri."
----------
Mettiamoci ora nei panni del prof. Somma.
Egli sa che x+y = 10
Egli NON può determinare x e y perché:
10 = 8+2 = 7+3 = 6+4 = 5+5
INOLTRE, calcolando i prodotti, si rende conto che:
8*2 = 16 = 4*4
7*3 = 21
6*4 = 24 = 8*3 = 12*2
5*5 = 25
Egli, di conseguenza, CAPISCE che il prof. Prodotto deve
avere uno dei numeri indicati, cioè: 16, 21, 24, 25.
Egli SI RENDE CONTO inoltre che 21 e 25 NON sono P-ambigui,
cioè non sono scomponibili in due fattori in più di un
modo, perciò NON PUO' DEDURRE che il prof. Prodotto non può
essere in grado di determinare i suoi due numeri.
Perciò non può dire: "Io lo sapevo che tu non potevi
determinare i due numeri."
----------
E' chiaro che il dialogo non può andare avanti.
Perciò s = 10 e p= 24 non costituiscono una soluzione del
problema.
3. Risoluzione vera e propria del problema, ossia descrizione dettagliata del procedimento da seguire per trovare s, p e quindi x, y basandosi soltanto sul range e sul dialogo tra i due professori.
Per risolvere il problema bisogna porsi ora da un nuovo punto di vista: quello di un osservatore esterno che, ascoltando il dialogo dei due professori e conoscendo il range del problema, riesce a dedurre quali sono i numeri s, p e trovare di conseguenza x, y.
Seguiamo ancora una volta il dialogo.
Prof. Prodotto: "Non posso determinare i due
numeri."
Questa frase ci permette di dedurre che il prof.
Prodotto ha un numero P-ambiguo.
Nel range [2-100] i numeri P-ambigui sono 3157. Evito di
elencarli qui sotto, ma possono essere trovati con molta
pazienza o con un semplice programma.
Prof. Somma: "Io lo sapevo che tu non potevi
determinare i due numeri."
Questa frase ci permette di dedurre che il prof.
Somma ha un numero SP-ambiguo.
Nel range [2-100] i numeri SP-ambigui sono 10 e per la
precisione: 11, 17, 23, 27, 29, 35, 37, 41, 47, 53
Anche questi possono essere trovati con molta pazienza o con
un semplice programma.
Prof. Prodotto: "Ora posso determinare i due
numeri."
Questa frase ci permette di dedurre che il prof.
Prodotto ha un numero P-ambiguo, p, a cui corrisponde UNO e
UNO SOLO numero SP-ambiguo.
Ebbene, nel range [2-100], esistono 86 numeri di questo tipo.
Riporto l'elenco, che è indispensabile per concludere il
problema.
I numeri che può avere il prof. Prodotto sono quelli della
terza colonna.
x= 4 - y= 7 - p= 28 - s= 11
x= 3 - y= 8 - p= 24 - s= 11
x= 2 - y= 9 - p= 18 - s= 11
x= 4 - y= 13 - p= 52 - s= 17
x= 10 - y= 13 - p= 130 - s= 23
x= 7 - y= 16 - p= 112 - s= 23
x= 4 - y= 19 - p= 76 - s= 23
x= 13 - y= 14 - p= 182 - s= 27
x= 11 - y= 16 - p= 176 - s= 27
x= 10 - y= 17 - p= 170 - s= 27
x= 9 - y= 18 - p= 162 - s= 27
x= 8 - y= 19 - p= 152 - s= 27
x= 7 - y= 20 - p= 140 - s= 27
x= 5 - y= 22 - p= 110 - s= 27
x= 4 - y= 23 - p= 92 - s= 27
x= 2 - y= 25 - p= 50 - s= 27
x= 13 - y= 16 - p= 208 - s= 29
x= 12 - y= 17 - p= 204 - s= 29
x= 11 - y= 18 - p= 198 - s= 29
x= 10 - y= 19 - p= 190 - s= 29
x= 8 - y= 21 - p= 168 - s= 29
x= 7 - y= 22 - p= 154 - s= 29
x= 6 - y= 23 - p= 138 - s= 29
x= 4 - y= 25 - p= 100 - s= 29
x= 2 - y= 27 - p= 54 - s= 29
x= 17 - y= 18 - p= 306 - s= 35
x= 16 - y= 19 - p= 304 - s= 35
x= 14 - y= 21 - p= 294 - s= 35
x= 12 - y= 23 - p= 276 - s= 35
x= 10 - y= 25 - p= 250 - s= 35
x= 9 - y= 26 - p= 234 - s= 35
x= 8 - y= 27 - p= 216 - s= 35
x= 6 - y= 29 - p= 174 - s= 35
x= 4 - y= 31 - p= 124 - s= 35
x= 3 - y= 32 - p= 96 - s= 35
x= 17 - y= 20 - p= 340 - s= 37
x= 16 - y= 21 - p= 336 - s= 37
x= 10 - y= 27 - p= 270 - s= 37
x= 9 - y= 28 - p= 252 - s= 37
x= 8 - y= 29 - p= 232 - s= 37
x= 6 - y= 31 - p= 186 - s= 37
x= 5 - y= 32 - p= 160 - s= 37
x= 19 - y= 22 - p= 418 - s= 41
x= 18 - y= 23 - p= 414 - s= 41
x= 17 - y= 24 - p= 408 - s= 41
x= 16 - y= 25 - p= 400 - s= 41
x= 15 - y= 26 - p= 390 - s= 41
x= 14 - y= 27 - p= 378 - s= 41
x= 13 - y= 28 - p= 364 - s= 41
x= 12 - y= 29 - p= 348 - s= 41
x= 10 - y= 31 - p= 310 - s= 41
x= 9 - y= 32 - p= 288 - s= 41
x= 7 - y= 34 - p= 238 - s= 41
x= 4 - y= 37 - p= 148 - s= 41
x= 3 - y= 38 - p= 114 - s= 41
x= 23 - y= 24 - p= 552 - s= 47
x= 22 - y= 25 - p= 550 - s= 47
x= 20 - y= 27 - p= 540 - s= 47
x= 19 - y= 28 - p= 532 - s= 47
x= 18 - y= 29 - p= 522 - s= 47
x= 17 - y= 30 - p= 510 - s= 47
x= 16 - y= 31 - p= 496 - s= 47
x= 15 - y= 32 - p= 480 - s= 47
x= 13 - y= 34 - p= 442 - s= 47
x= 10 - y= 37 - p= 370 - s= 47
x= 7 - y= 40 - p= 280 - s= 47
x= 6 - y= 41 - p= 246 - s= 47
x= 4 - y= 43 - p= 172 - s= 47
x= 26 - y= 27 - p= 702 - s= 53
x= 25 - y= 28 - p= 700 - s= 53
x= 24 - y= 29 - p= 696 - s= 53
x= 23 - y= 30 - p= 690 - s= 53
x= 22 - y= 31 - p= 682 - s= 53
x= 21 - y= 32 - p= 672 - s= 53
x= 20 - y= 33 - p= 660 - s= 53
x= 19 - y= 34 - p= 646 - s= 53
x= 18 - y= 35 - p= 630 - s= 53
x= 17 - y= 36 - p= 612 - s= 53
x= 16 - y= 37 - p= 592 - s= 53
x= 15 - y= 38 - p= 570 - s= 53
x= 13 - y= 40 - p= 520 - s= 53
x= 12 - y= 41 - p= 492 - s= 53
x= 10 - y= 43 - p= 430 - s= 53
x= 8 - y= 45 - p= 360 - s= 53
x= 6 - y= 47 - p= 282 - s= 53
x= 5 - y= 48 - p= 240 - s= 53
Prof. Somma: "In questo caso, anch'io posso
determinare i due numeri."
I numeri che può avere il prof. Somma sono quelli
della quarta colonna dell'elenco precedente.
Ebbene, se il prof. Somma è in grado di pronunciare quella
frase, è perché ha il numero 17.
Infatti il 17 è l'unico numero SP-ambiguo a cui corrisponde
uno e uno solo numero P-ambiguo.
Se, ad esempio il prof. Somma avesse il numero 23 non
potrebbe decidere quale dei numeri 130, 112, 76 avrebbe il
prof. Prodotto. Stesso discorso per gli altri numeri: 11, 27,
29, 35, e così via.
Il numero P-ambiguo cercato è quindi il 52, mentre il numero SP-ambiguo è il 17.
Da ciò si deduce finalmente:
s = 17
p = 52
x = 4
y = 13
4. Dimostrazione che s = 17, p = 52, x = 13, y = 4 NON sono una soluzione nel range [2-20]. Questo fatto può sembrare strano perché in effetti x, y appartengono al range.
Seguiamo ancora una volta il dialogo.
Prof. Prodotto: "Non posso determinare i due
numeri."
Questa frase ci permette di dedurre che il prof.
Prodotto ha un numero P-ambiguo.
Nel range [2-20] i numeri P-ambigui sono 80. Evito di
elencarli qui sotto, ma possono essere trovati con molta
pazienza o con un semplice programma.
NOTA BENE: 52, in questo caso, NON è un numero P-ambiguo
perchè:
52 = 26*2 = 13*4.
Siccome 26 è fuori del range, il prof. Prodotto potrebbe
determinare SUBITO la coppia di numeri (13,4).
Prof. Somma: "Io lo sapevo che tu non potevi
determinare i due numeri."
Questa frase ci permette di dedurre che il prof.
Somma ha un numero SP-ambiguo.
Nel range [2-20] c'è un solo numero SP-ambiguo, che è 11.
Ed ecco il punto: NEL RANGE [2-20], il numero 17 NON E' SP-ambiguo.
Vediamo perché:
17 = 15+2 = 14+3 = 13+4 = 12+5 = 11+6 = 10+7 = 9+8
Calcolando i prodotti, si ottiene:
15*2 = 30 = 10*3 = 6*5
14*3 = 42 = 7*6
13*4 = 52 = 26*2
12*5 = 60 = 6*10 = 4*15 = 3*20 = 2*30
11*6 = 66 = 22*3 = 33*2
10*7 = 70 = 5*14 = 2*35
9*8 = 72 = 6*12 = 4*18 = 3*24 = 2*36
Ebbene, NON E' VERO CHE CIASCUNO dei numeri dell'elenco: 30,
42, 52, 60, 66, 70, 72 è P-ambiguo, cioè è scomponibile in
due fattori in più di un modo.
Ecco due esempi contrari:
52 = 13*4 (la scomposizione 26*2 non è accettabile perché
fuori del range)
66 = 11*6 (le scomposizioni 22*3 e 33*2 non sono accettabili)
Prof. Prodotto: "Ora posso determinare i due
numeri."
Questa frase ci permette di dedurre che il prof.
Prodotto ha un numero P-ambiguo, p, a cui corrisponde UNO e
UNO SOLO numero SP-ambiguo.
Ebbene, nel range [2-20], esistono 4 numeri di questo tipo.
Riporto l'elenco, che è indispensabile per concludere il
problema.
I numeri che può avere il prof. Prodotto sono quelli della
terza colonna.
x = 5 - y = 6 - P = 30 - S = 11
x = 4 - y = 7 - P = 28 - S = 11
x = 3 - y = 8 - P = 24 - S = 11
x = 2 - y = 9 - P = 18 - S = 11
Prof. Somma: "In questo caso, anch'io posso
determinare i due numeri."
I numeri che può avere il prof. Somma sono quelli
della quarta colonna dell'elenco precedente.
Ebbene, il prof. Somma, per essere in grado di pronunciare
quella frase, dovrebbe avere un numero tale che:
sia l'unico numero SP-ambiguo a cui corrisponde uno e uno
solo numero P-ambiguo.
Purtroppo, nella nostra situazione, il prof. Somma può avere
soltanto il numero SP-ambiguo 11 a cui corrispondono ben 4
numeri P-ambigui.
Perciò non può determinare i due numeri x e y.
Nota storica
"David J.
Sprows, 1976
P & S are given the product and sum of two integers
greater than one, but the sum is <100. P says he doesn't
know the numbers. S says she knew that. P replies that he now
knows the values and S responds that so does she. The unique
answer is 4, 13."
"Martin
Gardner, 1979
The impossible problem. Gives a version of Sprows'
problem and says the problem was sent by Mel Stover and had
been circulating for a year or two. This version assumes the
numbers are greater than 1 but at most 20, which gives the
unique solution 4, 13. However Gardner asserts that the
solution remains the same if the bound is increased to 100 (N.
d. R. 1000 ?) but I think there are further answers, e.g. 4,
61, see the discussion below.
Stover says a computer program has checked and found no
further solutions up to 2,000,000 and it may be that there is
no further solution when the upper bound is removed, this is
a mistake of some sort.
Further, Kiltinen & Young say they had a letter from
Gardner conjecturing that there are infinitely many solutions."
Un particolare ringraziamento al prof. David Singmaster, da cui ho tratto le precedenti note.
Daniel Gutkin
segnala che la soluzione data da Martin Gardner è valida nel
range [2-1000] e non [2-100]
"In fact you have to replace 100 by 1000, and I do
confirm your second solution x=4, y=61 associated with the SP-amb
S=65. Moreover I tested there are no others solutions
than S=65 (x=4,y=61) and S=17 (x=4,y=13) in [2,1000]"
5. Presentazione di un programma in BASIC che risolve il problema dopo aver chiesto il range.
DEFINT A-Z
CLS
'Definizione dell'intervallo in cui si trovano i due
numeri i,j
INPUT "Min"; min
INPUT "Max"; max
'Minimo e massimo dei possibili prodotti dei due numeri
longmax = INT((max * max) / 2)
longmin = min * min
'Numeri x e y
DIM p1(longmax, 2)
'Prodotti
DIM p1pr(longmax)
'Numero ripetitizioni prodotti
DIM p1nv(longmax)
'Somme
DIM p1sm(longmax)
'insieme P1 dei PRODOTTI non scomponibili univocamente
'numero di tali P
np = 0
'insieme S1 delle SOMME che soddisfano la 2
DIM s1(longmax)
'numero di tali somme
ns = 0
'**********
'(1) Non posso determinare il prodotto
'Quali sono i prodotti che soddisfano la (1)?
'Quelli che sono scomponibili in piu' di un modo, a meno
dell'ordine dei fattori
'Chiamo P1 tale insieme
'**********
'Calcolo prodotti e costruzione di P1
m = 0 'Contatore dei prodotti possibili
FOR i = min TO max
FOR j = i TO max
m = m + 1
p = i * j
p1(m, 1) = i
p1(m, 2) = j
p1pr(m) = p
p1nv(m) = 1
'Conta quanti elementi ci sono uguali a ciascun p
ripetizione = 0
FOR n = 1 TO m - 1
IF p1pr(n) = p THEN
p1nv(n) = p1nv(n) + 1
ripetizione = 1
cont = p1nv(n)
END IF
NEXT n
IF ripetizione = 1 THEN p1nv(m) = cont
NEXT j
PRINT i 'Stampa i per mostrare a che punto e'
NEXT i
'Formazione dell'insieme P1
k = 0 'Contatore degli elementi di P1
FOR i = 1 TO m
IF p1nv(i) > 1 THEN
k = k + 1
p1(k, 1) = p1(i, 1)
p1(k, 2) = p1(i, 2)
p1pr(k) = p1pr(i)
p1nv(k) = p1nv(i)
p1sm(k) = p1(i, 1) + p1(i, 2)
END IF
NEXT i
np = k 'Numero dei prodotti che soddisfano la (1)
PRINT
"--------------------------------------------------"
PRINT "(1) Non posso determinare il prodotto."
PRINT "Num.prodotti che soddisfano la 1)"; np
INPUT "Insieme dei numeri P-ambigui. Vuoi vederli tutti?
s/n"; r$
IF r$ = "s" THEN
'Stampo l'insieme P1
PRINT "Elenco di tutti i prodotti che soddisfano la (1)"
PRINT "a", "b", "a*b", "nø
rip.", "a+b"
FOR k = 1 TO np
PRINT p1(k, 1), p1(k, 2), p1pr(k), p1nv(k), p1sm(k)
NEXT k
END IF
'**********
'(2) Io lo sapevo gia'
'Quali sono le somme che soddisfano la 2?
'Quelle delle quali tutte le fattorizzazioni appartengono a P1
'Chiamo S1 tale insieme
'**********
'Costruzione insieme S1 delle somme che soddisfano la 2
'Cioe' le somme delle quali tutte le fattorizzazioni
'appartengono a P1
conts1 = 0 'Contatore delle somme
flagapp = 0 'Soddisfa la 2? 0/1
longpmin = min + min 'Somma minima
longpmax = max + max 'Somma massima
'Data una qualunque somma i, essa e' scomponibile in j + (j-i)
FOR i = longpmin TO longpmax
flagapp = 1
sup = INT(i / 2)
'Ciclo calcolo tutti i possibili prodotti
FOR j = min TO sup
p = j * (i - j)
'Per ogni prodotto verifico l'appartenenza a P1
flaglocal = 0
FOR k = 1 TO np
IF p = p1pr(k) THEN
flaglocal = 1
EXIT FOR
END IF
NEXT k
'Se non appartiene esco dal ciclo j
IF flaglocal = 0 THEN
flagapp = 0
EXIT FOR
END IF
NEXT j
'Se appartiene lo aggiungo all'insieme S1
IF flagapp = 1 THEN
conts1 = conts1 + 1
s1(conts1) = i
END IF
NEXT i
ns = conts1 'Numero di somme accettabili
PRINT
"--------------------------------------------------"
PRINT "(2) Io lo sapevo gia'."
PRINT "Num. di somme che soddisfano la 2)"; ns
INPUT "Numeri SP-ambigui. Vuoi vederli tutti? s/n";
r$
IF r$ = "s" THEN
'Stampo l'insieme S1
FOR k = 1 TO ns
PRINT s1(k)
NEXT k
END IF
'**********
'(3) Allora io posso determinare i due numeri
'Quali sono i prodotti che soddisfano la 3?
'Quei P che hanno UNA SOLA fattorizzazione in DUE fattori la
cui somma
'appartenente all'insieme delle somme accettabili
'Ottengo tale insieme selezionando gli elementi da P1 e
riscrivendoli in P1
'**********
'Trovare quei P che hanno una sola fattorizzazione
'appartenente all'insieme delle somme accettabili
'Prima trovo quelli che ne hanno ALMENO una
k = 0
FOR i = 1 TO np
flagapp = 0
FOR j = 1 TO ns
IF p1sm(i) = s1(j) THEN
k = k + 1
p1(k, 1) = p1(i, 1)
p1(k, 2) = p1(i, 2)
p1pr(k) = p1pr(i)
p1nv(k) = p1nv(i)
p1sm(k) = p1sm(i)
END IF
NEXT j
NEXT i
np2 = k
PRINT "Ho trovato"; np2; "prodotti"
PRINT " Che hanno ALMENO una fattorizzazione in DUE
fattori"
PRINT "la cui somma appartiene a S1"
INPUT "Vuoi vederli tutti? s/n"; r$
IF r$ = "s" THEN
PRINT "fatt1", "fatt2", "prodotto",
"somma"
FOR k = 1 TO np2
PRINT p1(k, 1), p1(k, 2), p1pr(k), p1sm(k)
NEXT
END IF
'Ora devo eliminare i doppioni di P
'Perché il doppione ha piu' di una fattorizzazione
'Definisco P2 l'insieme delle coppie accettabili p2(a+b, a*b)
DIM p2(longmax, 2)
DIM p2pr(longmax)
DIM p2sm(longmax)
nca = 0 'Numero coppie accettabili
FOR i = 1 TO np2
doppio = 0
FOR j = i + 1 TO np2
IF p1pr(i) = p1pr(j) AND p1pr(i) <> 0 THEN
doppio = 1
p1pr(j) = 0
END IF
NEXT j
IF doppio = 0 AND p1pr(i) <> 0 THEN
nca = nca + 1
p2pr(nca) = p1pr(i)
p2sm(nca) = p1sm(i)
p2(nca, 1) = p1(i, 1)
p2(nca, 2) = p1(i, 2)
END IF
NEXT i
'Ordino per somme
FOR i = 1 TO nca
FOR j = 1 TO i
IF p2sm(j) >= p2sm(i) THEN
SWAP p2sm(j), p2sm(i)
SWAP p2pr(j), p2pr(i)
SWAP p2(j, 1), p2(i, 1)
SWAP p2(j, 2), p2(i, 2)
END IF
NEXT j
NEXT i
PRINT
"--------------------------------------------------"
PRINT "(3) Allora io posso determinare i due numeri."
PRINT "Esistono ESATTAMENTE"; nca; "prodotti"
PRINT "che hanno UNA E UNA SOLA fattorizzazione in DUE
fattori"
PRINT "la cui somma appartiene a S1"
INPUT "Numeri P-ambigui che corrispondono ad un solo
numero SP-ambiguo. Vuoi vederli tutti? s/n"; r$
IF r$ = "s" THEN
'Stampo le coppie accettabili
PRINT "fatt1", "fatt2", "prodotto", "somma"
FOR k = 1 TO nca
PRINT "x="; p2(k, 1), "y="; p2(k, 2),
"p="; p2pr(k), "s="; p2sm(k)
NEXT k
END IF
'Ultima fase
'**********
'(4) Allora anch'io posso determinare i due numeri
'Quali sono le somme che soddisfano la 4?
'Sono i numeri SP-ambigui a cui corrisponde uno e uno solo
numero P-ambiguo
'**********
'Trovo tali somme
DIM risultato(10, 2)
DIM a(10)
DIM b(10)
nris = 0
FOR i = 1 TO nca
singolo = 1
FOR j = i + 1 TO nca
IF p2sm(i) = p2sm(j) AND p2sm(i) <> 0 THEN
singolo = 0
p2sm(j) = 0
END IF
NEXT j
IF singolo = 1 AND p2sm(i) <> 0 THEN
nris = nris + 1
risultato(nris, 1) = p2pr(i)
risultato(nris, 2) = p2sm(i)
a(nris) = p2(i, 1)
b(nris) = p2(i, 2)
END IF
NEXT i
'Stampa dei risultati
PRINT
"--------------------------------------------------"
PRINT "(4) Allora anch'io posso determinare i due numeri."
PRINT
"--------------------------------------------------"
PRINT "Ci sono"; nris; "risultati."
FOR i = 1 TO nris
PRINT "x="; a(i); "y="; b(i)
PRINT "Prodotto ="; risultato(i, 1); "Somma
="; risultato(i, 2)
NEXT i
'--------------------------------------
'Onore e gloria a John Kemeny e Thomas Kurtz
'inventori del linguaggio B.A.S.I.C.
'--------------------------------------
'by Gianfranco Bo
Un sentito ringraziamento a Daniel Gutkin che ha inviato un programma in Maple V5 che risolve il "Problema impossibile"
Daniel Gutkin
gutkin@math.univ-paris13.fr
#Le probleme impossible (Maple
V5)
#On donne à "P" le produit P de 2 entiers entre 2
et 100 et à "S" leur somme S.
#1) "P" dit: je ne peux trouver
(=> P P-ambigu)
#2) "S" dit: je le savais
(=> S SP-ambigu)
#3) "P" dit: alors je peux trouver (=>car "P"
peut alors connaitre le nombre SP-ambigu S de "S"
et donc S=x+y)
#4) "S" dit: alors moi aussi (car SEUL un S
SP-ambigu(S=17) a permis à "P" de trouver le
P(P=52) .En d'autre termes, 17 est le SEUL nombre
SP-ambigu, à figurer SEUL, dans la liste #des SP-amb
associes aux produits P.
> restart;
> with(numtheory):
#Recherche des SP- ambigus et creation d'une liste SP: un
entier n est SP-amb pour un intervalle si pour tout couple
x,y tq n=x+y, xy est P-amb, ie admet plus d'une factorisation
(x et y #dans l'intervalle considere)
> mini:=2:maxi:=100:
#intervalle de recherche [mini,maxi]
> minis:=2*mini:maxis:=2*maxi:
#intervalle des sommes
> SP:=[]:
#creation en vue de la liste des SP
> for n from minis to maxis
#pour chaque somme possible...
> do
> B:=true;
#creation du booleen de decision pour les SP
> for x from mini to n/2
> do
> y:=n-x;
> divp:=
divisors(x*y) minus {1,x*y} ;
#ensemble des div propres de x*y
> divp:=[ op(divp)
]; # transformation
en liste
> divpp:=[];
#creation en vue de la liste finale de diviseurs
> for j from 1
to nops(divp)
#comptage des diviseurs de x*y dans l'intervalle
> do
>
if divp[j]<=maxi and x*y/divp[j]<=maxi then divpp:=[op(divpp),divp[j]
] fi; #on ne garde que les
couples de diviseurs de l'intervalle [2,maxi]
> od;
>
#printf("%d %d %d %d %A %A
\n",n,x,y,x*y,ifactor(x*y),divpp); #aff des details
> B:=B and nops(divpp)>=3;
# TEST : un nombre est SP ambigu s'il reste dans la liste
divpp plus de 3 diviseurs
> od;
> if B=true then SP:=[op(SP),n]
fi; # creation de la liste des
SP-amb
>
> od:
> SP;
#affichage de la liste des SP-amb pour l'intervalle considéré
>
[11, 17, 23, 27, 29, 35, 37, 41, 47, 53]
#Le pb a donc une sol si il existe une
ligne UNIQUE ou apparait un SP-amb UNIQUE: -->
c'est le cas de P=52.
#Voici la solution:
> minip:=mini**2:maxip:=3000: #intervalle des
produits. on peut se contenter de maxip=702=26x27 car 53=26+27
est le plus grans SP-amb (sur [2,100])
> LSORT:=[]:
> printf("INTERVALLE [%d,%d]",mini,maxi);
> for n from minip to maxip
> do
> LSP[n]:=[]:
#pour chaque n on cree la liste des SP-amb associes a n
> SOM[n]:=[]:
# idem pour les decompositions x+y associees
>
> if tau(n)>4
# on enleve les n premiers ou produits de 2 nbres premiers
(ie qui ont moins de 4 diviseurs (non propres))
> then
>
#printf("\n %d= %20A ",n,ifactor(n))
: # affichage des details de la
decomposition en facteurs premiers
> for x in
divisors(n)
> do
>
if (x<>1 and x<>n and x^2<=n and x>=mini
and x<=maxi)
#pour chaque diviseur propre x de n dans l'intervalle
>
then
>
y:=n/x; s:=x+y;
#on calcule l'autre y, et la somme s=x+y
>
if member(s,SP)
#si s est SP-amb on la range dans la liste des SP-amb
associee à n
>
then LSP[n]:=[op(LSP[n]),s];
>
SOM[n]:=[op(SOM[n]),[x,y]]; #on range aussi
les decompositions x+y pour chaque n
>
fi
>
fi
> od;
>
# printf("\n %d= %20A %15A
%A",n,ifactor(n),LSP[n],SOM[n]);
# affichage detaille du/des sommes SP-ambigues associees
> if nops(LSP[n])=1
then printf("\n %d= %20A %A",n,ifactor(n),LSP[n]);
LSORT:=[op(LSORT),op(LSPn])] fi;
#on n'affiche que les produits n associes à UN SEUL SP-amb
et on cree une liste triee des SP associes
> fi:
> od:
> printf("%A ",sort(LSORT));
#liste triee des SP-amb faisant apparaitre la/les solutions
INTERVALLE [2,100]
18=
(2)*(3)^2 [11]
24=
(2)^3*(3) [11]
28=
(2)^2*(7) [11]
50=
(2)*(5)^2 [27]
52=
(2)^2*(13) [17]
54=
(2)*(3)^3 [29]
76=
(2)^2*(19) [23]
92=
(2)^2*(23) [27]
96=
(2)^5*(3) [35]
100=
(2)^2*(5)^2 [29]
110=
(2)*(5)*(11) [27]
112=
(2)^4*(7) [23]
114=
(2)*(3)*(19) [41]
124=
(2)^2*(31) [35]
130=
(2)*(5)*(13) [23]
138=
(2)*(3)*(23) [29]
140= (2)^2*(5)*(7)
[27]
148=
(2)^2*(37) [41]
152=
(2)^3*(19) [27]
154=
(2)*(7)*(11) [29]
160=
(2)^5*(5) [37]
162=
(2)*(3)^4 [27]
168= (2)^3*(3)*(7)
[29]
170=
(2)*(5)*(17) [27]
172=
(2)^2*(43) [47]
174=
(2)*(3)*(29) [35]
176=
(2)^4*(11) [27]
182=
(2)*(7)*(13) [27]
186=
(2)*(3)*(31) [37]
190=
(2)*(5)*(19) [29]
198= (2)*(3)^2*(11)
[29]
204= (2)^2*(3)*(17)
[29]
208=
(2)^4*(13) [29]
216=
(2)^3*(3)^3 [35]
232=
(2)^3*(29) [37]
234= (2)*(3)^2*(13)
[35]
238=
(2)*(7)*(17) [41]
240= (2)^4*(3)*(5)
[53]
246=
(2)*(3)*(41) [47]
250=
(2)*(5)^3 [35]
252= (2)^2*(3)^2*(7)
[37]
270= (2)*(3)^3*(5)
[37]
276= (2)^2*(3)*(23)
[35]
280= (2)^3*(5)*(7)
[47]
282=
(2)*(3)*(47) [53]
288=
(2)^5*(3)^2 [41]
294= (2)*(3)*(7)^2
[35]
304=
(2)^4*(19) [35]
306= (2)*(3)^2*(17)
[35]
310=
(2)*(5)*(31) [41]
336= (2)^4*(3)*(7)
[37]
340= (2)^2*(5)*(17)
[37]
348= (2)^2*(3)*(29)
[41]
360= (2)^3*(3)^2*(5)
[53]
364= (2)^2*(7)*(13)
[41]
370=
(2)*(5)*(37) [47]
378= (2)*(3)^3*(7)
[41]
390= (2)*(3)*(5)*(13)
[41]
400=
(2)^4*(5)^2 [41]
408= (2)^3*(3)*(17)
[41]
414= (2)*(3)^2*(23)
[41]
418= (2)*(11)*(19)
[41]
430=
(2)*(5)*(43) [53]
442= (2)*(13)*(17)
[47]
480= (2)^5*(3)*(5)
[47]
492= (2)^2*(3)*(41)
[53]
496=
(2)^4*(31) [47]
510= (2)*(3)*(5)*(17)
[47]
520= (2)^3*(5)*(13)
[53]
522= (2)*(3)^2*(29)
[47]
532= (2)^2*(7)*(19)
[47]
540= (2)^2*(3)^3*(5)
[47]
550= (2)*(5)^2*(11)
[47]
552= (2)^3*(3)*(23)
[47]
570= (2)*(3)*(5)*(19)
[53]
592=
(2)^4*(37) [53]
612= (2)^2*(3)^2*(17)
[53]
630= (2)*(3)^2*(5)*(7)
[53]
646= (2)*(17)*(19)
[53]
660= (2)^2*(3)*(5)*(11)
[53]
672= (2)^5*(3)*(7)
[53]
682= (2)*(11)*(31)
[53]
690= (2)*(3)*(5)*(23)
[53]
696= (2)^3*(3)*(29)
[53]
700= (2)^2*(5)^2*(7)
[53]
702= (2)*(3)^3*(13)
[53]
[11, 11, 11, 17, 23, 23, 23, 27, 27, 27, 27, 27, 27, 27, 27,
27, 29, 29, 29, 29, 29, 29, 29, 29, 29, 35, 35, 35, 35, 35,
35, 35, 35, 35, 35, 37, 37, 37, 37, 37, 37, 37, 41, 41, 41,
41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 47, 47, 47, 47, 47,
47, 47, 47, 47, 47, 47, 47, 47, 53, 53, 53, 53, 53, 53, 53,
53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53]
Daniel Gutkin
Sito Web realizzato da Gianfranco Bo