Apendice: Solución problema Samuel y Predro

3009353 Introducción al Programa de MatemáticasApendice: solución al problema de Samuel y Pedro

Juan D Vélez

Universidad Nacional

Marzo 11 2013

(Universidad Nacional) Marzo 11 2013 1 / 16

Solución al problema de Samuel y Pedro

Empecemos por extraer la información oculta o codi�cada en lasecuencia de llamadas telefónicas.

Sean A y B los números desconocidos. En la primera llamada Samuela�rma que Pedro, conociendo sólo el valor del producto AB no tieneelementos su�cientes para averiguar los números. Pero esto sólo esposible si Samuel está seguro de que ni A ni B son primos. En otrostérminos, la llamada de Samuel implica que la suma que tiene en supoder no puede descomponerse en suma de dos primos.

Empecemos por extraer la información oculta o codi�cada en lasecuencia de llamadas telefónicas.

Sean A y B los números desconocidos. En la primera llamada Samuela�rma que Pedro, conociendo sólo el valor del producto AB no tieneelementos su�cientes para averiguar los números. Pero esto sólo esposible si Samuel está seguro de que ni A ni B son primos. En otrostérminos, la llamada de Samuel implica que la suma que tiene en supoder no puede descomponerse en suma de dos primos.

En particular, dicha suma no puede ser un número par, ya que todonúmero par menor que 100 puede descomponerse en suma de dosnúmeros primos (la conjetura de Goldbach a�rma lo anterior, peropara todos los enteros pares superiores a 2).

Aclaremos el razonamiento anterior con un ejemplo. Si Samuelhubiese recibido como suma el número 20, demos por caso, no habríapodido hacer la a�rmación de la primera llamada, pues debería haberrazonado de la siguiente manera: como existe la posibilidad de quelos números sean 13 y 7 (primos con suma igual a 20), Pedro en esecaso habría recibido 91 como producto, de lo cual habría concluidoelementalmente que los factores eran 7 y 13, pues es la únicadescomposición posible de 91 como producto de dos factores entre 2y 99. Además, la llamada de Pedro a Samuel anunciando la respuestatampoco se habría hecho esperar.

En particular, dicha suma no puede ser un número par, ya que todonúmero par menor que 100 puede descomponerse en suma de dosnúmeros primos (la conjetura de Goldbach a�rma lo anterior, peropara todos los enteros pares superiores a 2).

Aclaremos el razonamiento anterior con un ejemplo. Si Samuelhubiese recibido como suma el número 20, demos por caso, no habríapodido hacer la a�rmación de la primera llamada, pues debería haberrazonado de la siguiente manera: como existe la posibilidad de quelos números sean 13 y 7 (primos con suma igual a 20), Pedro en esecaso habría recibido 91 como producto, de lo cual habría concluidoelementalmente que los factores eran 7 y 13, pues es la únicadescomposición posible de 91 como producto de dos factores entre 2y 99. Además, la llamada de Pedro a Samuel anunciando la respuestatampoco se habría hecho esperar.

El razonamiento anterior nos permite descartar como sumas posiblestodos los números pares menores que 100 y todos los impares que sepuedan descomponer en la forma 2+ p, con p un primo impar(también son suma de dos primos). Con el �n de facilitar la operaciónde descarte, resulta conveniente enumerar todos los primos entre 3 y100, que son:

3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89y 97.

Si les sumamos dos unidades a cada uno de ellos, obtenemos lasiguiente lista:

5, 7, 9, 13, 15, 19, 21, 25, 31, 33, 39, 43, 45, 49, 53, 55, 61, 63, 69, 73, 75, 81, 85, 91y 99.

3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89y 97.

5, 7, 9, 13, 15, 19, 21, 25, 31, 33, 39, 43, 45, 49, 53, 55, 61, 63, 69, 73, 75, 81, 85, 91y 99.

3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89y 97.

5, 7, 9, 13, 15, 19, 21, 25, 31, 33, 39, 43, 45, 49, 53, 55, 61, 63, 69, 73, 75, 81, 85, 91y 99.

3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89y 97.

5, 7, 9, 13, 15, 19, 21, 25, 31, 33, 39, 43, 45, 49, 53, 55, 61, 63, 69, 73, 75, 81, 85, 91y 99.

Después de eliminar los pares y los números de la lista anterior,concluimos que Samuel pudo haber recibido como suma sólo uno delos siguientes números:

11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95y 97 (el 3 se elimina ya que sólo puede ser suma de 2 y 1, pero el 1está excluido de las posibilidades).

Después de eliminar los pares y los números de la lista anterior,concluimos que Samuel pudo haber recibido como suma sólo uno delos siguientes números:

11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95y 97 (el 3 se elimina ya que sólo puede ser suma de 2 y 1, pero el 1está excluido de las posibilidades).

Después de la llamada de Pedro anunciando su éxito, Samuel debehaber re�exionado así: mi llamada pesimista le ha indicado al astutoPedro que mi suma no puede descomponerse en suma de dos primos;en particular, que no es par, y esta información, junto con el productode los dos números, le ha permitido conocerlos. Una manera, entreotras, como esto podría ocurrir -debió razonar Samuel-, sería, porejemplo, si los números fueran, uno de ellos una potencia de dos, 2n,y el otro un primo p. En tal caso, Pedro, disponiendo además delproducto, p � 2n, y sabiendo que la suma no puede ser par, habríaconcluido que los números tenían que ser p y 2n, ya que cualquierotra partición posible de dicho producto en dos factores tendrá laforma 2n�k y p � 2k (con k > 0), cuya suma sería par y, enconsecuencia, descartable.

Ahora, nosotros sabemos que Samuel ha descubierto los númerosdespués de hacer la re�exión anterior. Esto nos permite concluir quela suma de Samuel es un número que no puede expresarse de dosmaneras distintas como suma de una potencia de 2 y un primo, ya quesi este fuera el caso, Samuel no hubiera podido decidir si los númeroseran 2n y p ó 2m y q, con p y q primos. Por ejemplo, el 11 se descartacomo una de las sumas posibles ya que 11 = 22 + 7 = 23 + 3. En talcaso, Samuel se hubiera dicho a sí mismo: una posibilidad es que losnúmeros sean 22 y 7; Pedro entonces conocería el producto,22 � 7 = 28, lo cual le llevaría a concluir que los números eran o bien2 y 2� 7 (2 y 14) o 22 y 7 (4 y 7).

Pero como después de mi primera llamada -continúa Samuel-, Pedrosabía que la suma no podía ser par, y en tal caso hubiese descartadola primera de las posibilidades y habría concluido que los númeroseran 4 y 7; de ahí que me hubiese llamado a�rmando conocer losnúmeros. Otra posibilidad -piensa Samuel- es que los dos númerosfuesen 23 y 3 (8 y 3), en este caso como en el anterior, Pedro habríapodido conocer el valor de ambos números y también me habríallamado. De todo lo anterior se deduce que si la suma fuese 11,Samuel no habría podido hallar los números y no habría ocurridonunca la última llamada.

Descartemos ahora, de la lista de sumas posibles, todos aquellosnúmeros que sean expresables de dos formas distintas como suma deuna potencia de 2 y un primo. Estos son:11, 23, 27, 35, 37, 47, 51, 57, 67, 71, 77, 79, 83, 87, 93 y 95.

En efecto,

11 = 22 + 7 = 23 + 3; 23 = 22 + 19 = 24 + 7;

27 = 22 + 23 = 23 + 19; 35 = 22 + 31 = 25 + 3;

37 = 25 + 5 = 23 + 29; 47 = 22 + 43 = 24 + 31;

51 = 22 + 47 = 23 + 43; 57 = 22 + 53 = 23 + 49;

67 = 26 + 3 = 23 + 59; 71 = 22 + 67 = 26 + 7;

77 = 22 + 73 = 26 + 13; 79 = 25 + 47 = 23 + 71;

83 = 22 + 79 = 26 + 19; 87 = 22 + 83 = 23 + 79;

93 = 22 + 89 = 25 + 61; 95 = 26 + 31 = 24 + 79.

En efecto,

11 = 22 + 7 = 23 + 3; 23 = 22 + 19 = 24 + 7;

27 = 22 + 23 = 23 + 19; 35 = 22 + 31 = 25 + 3;

37 = 25 + 5 = 23 + 29; 47 = 22 + 43 = 24 + 31;

51 = 22 + 47 = 23 + 43; 57 = 22 + 53 = 23 + 49;

67 = 26 + 3 = 23 + 59; 71 = 22 + 67 = 26 + 7;

77 = 22 + 73 = 26 + 13; 79 = 25 + 47 = 23 + 71;

83 = 22 + 79 = 26 + 19; 87 = 22 + 83 = 23 + 79;

93 = 22 + 89 = 25 + 61; 95 = 26 + 31 = 24 + 79.

En efecto,

11 = 22 + 7 = 23 + 3; 23 = 22 + 19 = 24 + 7;

27 = 22 + 23 = 23 + 19; 35 = 22 + 31 = 25 + 3;

37 = 25 + 5 = 23 + 29; 47 = 22 + 43 = 24 + 31;

51 = 22 + 47 = 23 + 43; 57 = 22 + 53 = 23 + 49;

67 = 26 + 3 = 23 + 59; 71 = 22 + 67 = 26 + 7;

77 = 22 + 73 = 26 + 13; 79 = 25 + 47 = 23 + 71;

83 = 22 + 79 = 26 + 19; 87 = 22 + 83 = 23 + 79;

93 = 22 + 89 = 25 + 61; 95 = 26 + 31 = 24 + 79.

En efecto,

11 = 22 + 7 = 23 + 3; 23 = 22 + 19 = 24 + 7;

27 = 22 + 23 = 23 + 19; 35 = 22 + 31 = 25 + 3;

37 = 25 + 5 = 23 + 29; 47 = 22 + 43 = 24 + 31;

51 = 22 + 47 = 23 + 43; 57 = 22 + 53 = 23 + 49;

67 = 26 + 3 = 23 + 59; 71 = 22 + 67 = 26 + 7;

77 = 22 + 73 = 26 + 13; 79 = 25 + 47 = 23 + 71;

83 = 22 + 79 = 26 + 19; 87 = 22 + 83 = 23 + 79;

93 = 22 + 89 = 25 + 61; 95 = 26 + 31 = 24 + 79.

En efecto,

11 = 22 + 7 = 23 + 3; 23 = 22 + 19 = 24 + 7;

27 = 22 + 23 = 23 + 19; 35 = 22 + 31 = 25 + 3;

37 = 25 + 5 = 23 + 29; 47 = 22 + 43 = 24 + 31;

51 = 22 + 47 = 23 + 43; 57 = 22 + 53 = 23 + 49;

67 = 26 + 3 = 23 + 59; 71 = 22 + 67 = 26 + 7;

77 = 22 + 73 = 26 + 13; 79 = 25 + 47 = 23 + 71;

83 = 22 + 79 = 26 + 19; 87 = 22 + 83 = 23 + 79;

93 = 22 + 89 = 25 + 61; 95 = 26 + 31 = 24 + 79.

En efecto,

11 = 22 + 7 = 23 + 3; 23 = 22 + 19 = 24 + 7;

27 = 22 + 23 = 23 + 19; 35 = 22 + 31 = 25 + 3;

37 = 25 + 5 = 23 + 29; 47 = 22 + 43 = 24 + 31;

51 = 22 + 47 = 23 + 43; 57 = 22 + 53 = 23 + 49;

67 = 26 + 3 = 23 + 59; 71 = 22 + 67 = 26 + 7;

77 = 22 + 73 = 26 + 13; 79 = 25 + 47 = 23 + 71;

83 = 22 + 79 = 26 + 19; 87 = 22 + 83 = 23 + 79;

93 = 22 + 89 = 25 + 61; 95 = 26 + 31 = 24 + 79.

En efecto,

11 = 22 + 7 = 23 + 3; 23 = 22 + 19 = 24 + 7;

27 = 22 + 23 = 23 + 19; 35 = 22 + 31 = 25 + 3;

37 = 25 + 5 = 23 + 29; 47 = 22 + 43 = 24 + 31;

51 = 22 + 47 = 23 + 43; 57 = 22 + 53 = 23 + 49;

67 = 26 + 3 = 23 + 59; 71 = 22 + 67 = 26 + 7;

77 = 22 + 73 = 26 + 13; 79 = 25 + 47 = 23 + 71;

83 = 22 + 79 = 26 + 19; 87 = 22 + 83 = 23 + 79;

93 = 22 + 89 = 25 + 61; 95 = 26 + 31 = 24 + 79.

En efecto,

11 = 22 + 7 = 23 + 3; 23 = 22 + 19 = 24 + 7;

27 = 22 + 23 = 23 + 19; 35 = 22 + 31 = 25 + 3;

37 = 25 + 5 = 23 + 29; 47 = 22 + 43 = 24 + 31;

51 = 22 + 47 = 23 + 43; 57 = 22 + 53 = 23 + 49;

67 = 26 + 3 = 23 + 59; 71 = 22 + 67 = 26 + 7;

77 = 22 + 73 = 26 + 13; 79 = 25 + 47 = 23 + 71;

83 = 22 + 79 = 26 + 19; 87 = 22 + 83 = 23 + 79;

93 = 22 + 89 = 25 + 61; 95 = 26 + 31 = 24 + 79.

En efecto,

11 = 22 + 7 = 23 + 3; 23 = 22 + 19 = 24 + 7;

27 = 22 + 23 = 23 + 19; 35 = 22 + 31 = 25 + 3;

37 = 25 + 5 = 23 + 29; 47 = 22 + 43 = 24 + 31;

51 = 22 + 47 = 23 + 43; 57 = 22 + 53 = 23 + 49;

67 = 26 + 3 = 23 + 59; 71 = 22 + 67 = 26 + 7;

77 = 22 + 73 = 26 + 13; 79 = 25 + 47 = 23 + 71;

83 = 22 + 79 = 26 + 19; 87 = 22 + 83 = 23 + 79;

93 = 22 + 89 = 25 + 61; 95 = 26 + 31 = 24 + 79.

Después de descartar las sumas anteriores, quedan sólo los números17, 29, 41, 53, 59, 65, 89 y 97. Veamos ahora que, salvo el 17, losdemás valores pueden también descartarse. En primer lugar, la sumano puede ser 29, pues si tal fuese el caso, Samuel habría razonado así:una posibilidad es que los números sean 13 y 16 = 24. En este caso,Pedro, sabiendo que la suma no es par, hubiese podido determinarlos(como ya se analizó en el párrafo anterior).

Otra posibilidad es que los números sean 25 = 52 y 4 = 22. En talsituación, Pedro, que ya sabe que la suma no puede descomponerseen suma de dos primos, habría considerado sólo dos posibilidades: quelos números fuesen 25 y 4 o 5 y 20 = 22 � 5. Pero esta segundaposibilidad también la hubiese descartado, ya que la suma en estecaso es 25, que es igual a 23+ 2, suma de dos primos. Por tanto,Samuel no hubiese podido saber si los números eran 16 y 13 o 25 y 4y, en consecuencia, la última llamada no se habría realizado.

De forma similar podemos descartar como suma los números41, 53, 59, 65, 89 y 97. En cada caso Samuel habría tenido más de unapareja de números como candidata a la solución y no hubiese podido hacerla última llamada. A manera de ejemplo, si la suma fuese 65, sepresentaría ambigüedad entre las parejas 4 y 61 y 8 y 57. Con la primerade ellas, Pedro hubiese recibido 22 � 61 como producto, lo cual le hubieseindicado que los números eran 22 y 61, ya que otra posible descomposicióndaría una suma par. Para la segunda pareja el producto es 23 � 3� 19,que admite como descomposición en dos sumandos, con suma impar, lasparejas (23 � 3; 19), (23 � 19; 3) y (23; 19� 3).

Para la primera pareja la suma es 43, que puede descomponerse en 41+ 2,suma de un primo más 2, lo cual hace que Pedro la descarte. La segundapareja tiene por suma 115, que se descarta ya que todas las sumas sonmenores que 100. De allí que Pedro, de haber recibido el producto23 � 19� 3 hubiese concluido que los números eran 23 y 19� 3 = 57.Luego Samuel no hubiese podido escoger entre las parejas (4; 61) y (8; 57).

Procediendo de manera similar, para 41 como suma se presentaambigüedad entre las parejas (4; 37) y (16; 25); para 53 hay ambigüedadentre las parejas (16; 37) y (40; 13); para 59 hay ambigüedad entre lasparejas (16; 43) y (4; 55); para 89 hay ambigüedad entre las parejas(16; 73) y (52; 37); �nalmente, para 97 hay ambigüedad entre las parejas(8; 89) y (14; 83).Por tanto, la única suma posible es 17, que puede descomponerse comosuma de dos números en las formas siguientes:15+ 2, 14+ 3, 13+ 4, 12+ 5, 11+ 6, 10+ 7 y 9+ 8.

En el primer caso, el producto es 15� 2 = 3� 5� 2, que puede serdescompuesto por Pedro en sumandos como 2+ 3� 5, 2� 3+ 5 y2� 5+ 3 (únicas sumas impares). La última descomposición se descartaya que es igual a 11+ 2 (un primo más 2), lo cual no ocurre con las dosprimeras. De aquí que Pedro hubiese tenido como candidatos posibles sólolas parejas (2; 15) y (6; 5) y no habría podido saber cuál escoger.Igualmente, para la descomposición 14+ 3, Pedro se enfrentaría a unaambigüedad con las parejas (14; 3) y (2; 21). Y para todas las otrasdescomposiciones distintas de 13+ 4 hay siempre una ambigüedad.

La pareja (12; 5) tiene como producto 30, que se analiza igual que en elcaso de la pareja (15; 2). Para la pareja (11; 6), su producto 36 es igual2� 3� 11, que permite la descomposición (11; 6) y (2; 33), ambasposibilidades válidas para Pedro. Para la pareja (10; 7), el producto 70 es7� 2� 5, que permite descomponerse en (2� 7; 5) y (7� 5; 2), ambasposibilidades válidas. Finalmente, la pareja (9; 8) tiene como producto23� 32, que le imposibilita a Pedro escoger entre las parejas (9; 8) y(24; 3).En resumen, la única pareja posible es 4 y 13, que se convierte en lasolución del problema.

Apendice: Solución problema Samuel y Predro

Documents

Transcript of Apendice: Solución problema Samuel y Predro