somma e prodotto

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.