Sumando subconjuntos – Un problema

Un breve problema para romper el largo intervalo sin posts:

En el siguiente conjunto de 70 números hay dos subconjuntos (distintos!) con igual suma.


5213588008354709077 9011219417469017946
9115813602317594993 1796745334760975384
2375118318707634486 3579709154995762145
2312952310307873817 3627590721354606439
5941472576423725122 4317696052329054505
5763055694478716846 5226146329630268999
2730952213106576953 6235647640047602135
5014371167157923471 4868653895375087301
9737387704190733086 9262565481673300485
5968266991171521006 6752113930489992229
5917882775011418152 5866436908055159779
9233099989955257688 9376338948688351159
3772194655144630358 9029836747496103755
3318990262990089104 9205546877037990475
9498032114812022495 9990105869964955299
9849598364470384044 2664344232060524242
1376783969573792128 1108556560089425769
7820574110347009988 1603454130529647419
6951628222196921724 9889945707884382295
4776591302180789869 7652184907611215542
3982809542974920136 8082643935949870308
1233783467857668500 4271233363607031147
7999940522596325715 1509145775275864006
6415171202616583365 4143260390225524497
6393762352694839041 2290598705560799669
7835010686462271800 8505865989334316749
7547888419188030222 4408107167048106771
8998470433081591390 9131522681668251869
9096632376298092495 7481066850797885510
5295758362772474604 1796212605533609345
5953431042043343946 3151838989804308537
6445353832659195698 9929081270845451034
6422250272800292361 8643312627450063997
7207546018039041794 3624820335477016277
3782849199070331143 6012991563467874119

Como podemos estar seguros de ello? Espero sus respuestas en los comentarios y daré la mía en el próximo post.

Advertisements

4 thoughts on “Sumando subconjuntos – Un problema

  1. Guille says:

    Hola Mariano,

    En rta al problema, en 1er lugar puede verse que cada nro tiene 19 cifras con lo cual está acotado superiormente por 1E19. Eso equivale a decir que la suma de un subconjunto cualquiera de los 70 nros estará acotada en forma superior por S= 7E20.
    Por otro lado, la cantidad de subconjuntos posibles es igual a T= C(70,0) + C(70,1) + … + C(70,70) = 2^70. Esto es fácilmente verificable recurriendo a la fórmula general del desarrollo del binomio de Newton (a + b)^n, donde a = b = 1.
    Ahora bien, como T>S, esto significa que la cantidad de subconjuntos posibles es mayor a la cantidad de posibles valores que pueden tomar esos subconjuntos. Por esta razón, y aplicando el principio del palomar podemos concluir que existen al menos 2 conjuntos distintos (pues tomamos combinaciones y no permutaciones) cuya suma es la misma.
    Es fácilmente verificable que T > S, planteamos 2^70 = K * 7E20, donde K es una constante a determinar. Aplicando logaritmos y sus propiedades, se despeja y obtiene que K ~ 1.69 > 1, con lo cual T > S

    Un comentario que me parece pertinente es que T es más grande que S y que ni siquiera hubo que acotar la suma inferiormente (en este caso S, es siempre mayor que 1E18) lo cual implica que los nros podrían estar comprendidos entre 1 y 1E19.

    Saludos y muy bueno el programa, lo veo siempre jaja

    • mchouza says:

      Muy buena la respuesta, es esencialmente idéntica a la que había encontrado. En el próximo post voy a discutir algunas cosas adicionales sobre este problema, como la factibilidad de encontrar una solución explícita a este problema.

  2. […] es la misma que Guillermo presentó en un comentario del post anterior, solo difiere en la forma de acotar […]

  3. […] a previous post (and in a comment from Guille [ɡiˈʒe] ) we have seen how the pigeonhole principle implies that a set of 70 numbers in the […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s