Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » Math Topics » Snark

Topic: [Snark] Uno del principio del palomar
Replies: 15   Last Post: Jun 12, 2014 1:05 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Jos

Posts: 448
Registered: 1/30/05
Re: [Snark] Uno del principio del palomar
Posted: Jun 2, 2014 10:59 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply
att1.html (4.4 K)

Efectivamente puede haber un número en cada caja, por ejemplo si pones un
1, 49 doses, un 3, y 49 doses, en ese orden.

Pero el argumento funciona si ordenamos los 100 números colocando primero
todos los impares. Si hay 2k impares (debe ser una cantidad par, pues la
suma total es par)
entonces las sumas a_1, a_1+a_2, a_1+a_2+a_3,... son alternadamente
impares y pares,
es decir que hay k impares y k pares, y todas las que siguen son pares.
Como la mitad de las cajas son impares, la única manera de que vaya una
suma a cada caja es que k=50, es decir que todos los números sean impares.
Sea u la cantidad de unos. Los 100-u restantes son al menos 3, luego
200 >= u + 3(100-u), de donde se sigue u >= 50.
Es claro u<100 (de hecho u<=98). Sean b_1, b_2,..., b_j los a_i mayores que
1.
Como b_1 <= 100 y b_1 + b_2 +...+ b_j = 200-u > 100,
debe haber un h tal que

b_1 + b_2 +...+ b_h <= 100 < b1 + b_2 +...+ b_{h+1}.

Si b_1 + b_2 +...+ b_h >= 50, agregando unos se llega a 100.
Si b_1 + b_2 +...+ b_h < 50, entonces b_{h+1}>50, y agregando unos a
b_{h+1} se llega a 100.

El resultado se puede generalizar: dados a_1, a_2,..., a_n, con *n par*,
1<=a_i<=n y
a_1+a_2+...+a_n = 2n, existen uno o más a_i's cuya suma es n.
Pero no es cierto si n es impar.

Saludos,

José Nieto


El 1 de junio de 2014, 14:42, Antonio Torrecillas <atorreci@xtec.cat>
escribió:

> El 29 de mayo de 2014, 23:33, Antonio Torrecillas <atorreci@xtec.cat>
> escribió:
>
> Me lo pregunta un alumno que está haciendo problemas olímpicos y no he

>> sabido ayudarle.
>>
>> ...
>>
>> Tenemos a1,a2,?,a100 números naturales todos entre 1 y 100 y tales que su
>> suma es 200.
>>
>> Demuestra que entre estos números siempre podemos escoger unos cuantos
>> que su suma sea 100.
>>
>> ---
>> Si permitimos que un número sea 101 o mayor esto no es cierto. Ejemplo:
>> 99 veces 1 y una vez 101
>>

>
> Decía que tiene toda la pinta de problema que se resuelve con el principio
> del palomar (o de Dirichlet)
> http://es.wikipedia.org/wiki/Principio_del_palomar
>
> Si creo la secuencia a1, a1+a2, a1+a2+a3, ...
>
> Obtengo 100 números entre 1 y 200.
>
> Si hago 100 cajas (una con los números 1, 1001, otra con 2,102, otra con
> 3, 103...) no veo la razón de que no pueda haber un número en cada caja y
> por tanto no haber dos en ninguna de ellas o lo que es lo mismo no obtener
> un subconjunto de números de suma 100.
>
> --
> Saludos cordiales
> Antonio Torrecillas
>
> _______________________________________
> Snark
> Más información en http://www.snarkianos.com
> http://mailman.uba.ar/mailman/listinfo/snark
>
>
>

_______________________________________
Snark
Más información en http://www.snarkianos.com
http://mailman.uba.ar/mailman/listinfo/snark




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.