mente intelligenza gioco logica test quiz enigmi passatempo stimolo cervello parola rompicapo

HomePage Gli autori Bibliografia Download Recensioni Link
......intelliGiochi...... ......intelliGenteMente...... ......intelliLibri......
 Sezione Giochi " difficili "  Pagina difficili  ritorno al gioco
 Gruppo  difficili
 Titolo  Il problema impossibile
 Autore  intelligiochi
 Data inserimento  01 gennaio 2001
 Livello di difficolta'  difficile

Soluzione

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?"

· Prof. Prodotto: "Non sono in grado di determinarli."

· Prof. Somma: "Io lo sapevo che tu non eri in grado di determinarli."

· Prof. Prodotto: "Beh, se dici così allora io so che numeri sono!"

· Prof. Somma: "Ora lo so anchio!"

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?

Analisi

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 = 2360 = 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 = 1772 = 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 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.

[soluzioneFine]