Os traigo hoy miércoles el problema de esta semana. Ahí va el enunciado:
Demostrar que en toda fiesta con
personas hay al menos dos de ellas que poseen la misma cantidad de amigos.
(Aclaraciones: Se entiende que estamos hablando de relaciones de amistad entre los asistentes a la fiesta y se asume que ninguna persona se cuenta a sí misma como amigo.)
Que se os dé bien.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.
Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.
Y si los símbolos < y > te dan problemas al escribir en LaTeX, te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.
Tienes un 20% de descuento y envío gratis en toda la web de La Tostadora con al menos dos artículos. Usa el código GAUSSIANOS entrando con el enlace de la imagen.
Y usando el código REBAJAS tienes un 30% de descuento hasta el 8 de agosto con al menos 3 artículos.
Si quieres recibir los artículos de Gaussianos en tu mail haz click en la imagen.
Únete a la iniciativa Yo construí el poliedro de Császár. Haz click en la imagen para conocer todo los detalles.
Y visita este set de Flickr para ver las construcciones de los lectores de Gaussianos.
¿Es una variación de la paradoja del cumpleaños?
Pues creo que ya lo he resuelto … ¿Se manda a algún sitio?
Para n = 2 está claro. O son amigos o no lo son y en los dos casos coinciden su número de amigos. Supongamos que es cierto para n, vamos a ver que es cierto para n+1. El caso mas desfavorable es que para n tuvieramos solo parejas de personas con el mismo número de amigos (sino, siempre se resuelve, pues si había tres o mas personas con el mismo número de amigos, al añadir el n+1 no puede romper en 3 o mas cantidades distintas el nº de amigos del grupo). Para romper los grupos de parejas deberá ser… Lee más »
Esto se resuelve muy facilmente por el principio del palomar
Basta aplicar el principio del palomar: si f es una aplicación que va del conjunto {1,…,n} (número de personas) al conjunto {1,…n-1} (número posible de amigos de cada persona), es claro que no puede ser inyectiva por ser el cardinal del primer conjunto mayor que el cardinal del segundo
Frikilosers
Se postea en directo y no importa si no es completo (siempre ayuda a todos)
Sólamente están restringidos los comentarios cuando se trata de concursos como el que había la semana pasada de El Pais, Desafíos Matemáticos en El País – Desafío Extraordinario de Navidad: Números bonitos, números feos, o los de los GaussianosyGuijarro – Desafío nº 9: “Una sucesión muy particular” …
¿Se puede poner aquí la solución? Abrazos
(Entiendo que puedo ponerlo) A ver si no he metido la pata y disculpad el lenguaje informal PARTIENDO DE 1) Se considera que hay N personas 2) Cada persona puede tener desde 0 a N-1 amigos 3) Cada persona tiene un número de amigos distinto ENTONCES 4) Cada persona tiene uno de los casos de 0 a N-1 amigos, y como hay el mismo número de casos que de personas todos estarán «cogidos» 5) Pero si tomamos el caso de la persona que tenga N-1 observamos que es imposible ya que solo podrá ser amigo de N-2 casos (hay una… Lee más »
Todos los números de amigos tienen que ser distintos luego los números de amigos deben ser todos los enteros entre 0 y n-1 ambos inclusive.
Si hay uno que tiene 0 amigos el que más tenga, descontando a sí mismo y al de 0 amigos puede, como máximo tener n-2 amigos. Comop alguien tendría que tener n-1 es imposible.
Aunque hemos hecho lo mismo, vuestras soluciones se entienden mucho mas fácilmente que la mía
Hola Juanjo, ahora miro tu solución, pero bueno ya te aviso que no soy matemático y me doy cuenta al leeros a muchos que me falta «background». Ahora estaba mirando que es eso del Principio del Palomar 🙂
Descubrí esta web gracias al concurso de El País, y me he animado a leeros, la verdad he estado ojeando los problemas, y algunas entradas es que no sabría por donde pillarlas (otras creo que si).
En fin que aprovecho para decir que me parece estupenda la web.
[…] problema lo han presentado en el blog gaussianos. Lo copio aquí, para que lo […]
Información Bitacoras.com…
Valora en Bitacoras.com: Os traigo hoy miércoles el problema de esta semana. Ahí va el enunciado: Demostrar que en toda fiesta con personas hay al menos dos de ellas que poseen la misma cantidad de amigos. (Aclaraciones: Se entiende que estamos hab……
Se que parece tonto pero… ¿que implica ser amigo de alguien? ¿es lo mismo que tener un amigo? es decir, eres amigo de alguien si el te considera amigo y tienes un amigo si tu le consideras como tal
Otra variante:
Asignar a cada persona el número de amigos que tiene en la fiesta, que será un número entre 0 y
. Sin embargo, las asignaciones 0 y 
no pueden aparecer simultáneamente en una misma fiesta con 
participantes. Luego, deben haber dos personas con igual número de amigos.
M, no creo que has dado con la forma más simple de aplicar el Principio del Palomar en este problema. Muy buena respuesta.
Vaya, veo que puse esencialmente la misma respuesta que JJGJJG. Siento no haber leído con calma todos los comentarios. Felices fiestas.
Una demostración sin utilizar el principio del palomar: Si n=2 la propiedad es claramente cierta. Supongamos que la propiedad es cierta si el número de personas está entre 2 y n. Llega una nueva que conoce a j personas, tenemos tres posibilidades: 1ª: j=0. El nº de amigos de cada miembro del grupo inicial no cambia y la propiedad se verifica. 2ª: j=n. El nº de amigos de cada miembro del grupo inicial se incrementa en una unidad y la propiedad se sigue verificando. 3ª: 1 <= j <n. Excluimos a las que no conoce y formamos un nuevo grupo… Lee más »
jjjbbb,
creo que esa demostración no es válida. Que la propiedad se cumpla para el grupo restringido no implica que se tenga que cumplir para el grupo total.
La mejor la de JJGJJG.
golvano, tienes razón, mi demostración es incorrecta.
Agradezco mucho tu observación.
Saludos.
Facilísimo, me lo planteé por cuenta propia a los 19 años cuando veía la materia de Geometría Euclideana… Principio de las Casillas… (Por cierto, ojalá y Mou no siga poniendo de portero a Adan 🙂 ) La cantidad de amigos de cada kien en la fiesta es un número del conjunto {0,1,2,…,n-1} teniéndose n personas en la fiesta. Supongamos, peor de los casos, que cada uno tenga una cantidad distinta de amigos. Entonces uno tiene 0 amigos y otro tiene n amigos. CONTRADICCIÓN, porque la amistad es «bidireccional». Si pepe (sin perdida de la generalidad no es amigo de nadie),… Lee más »
Cuál es paradoja del cumpleaños?
En una reunión de más de 366 personas, al menos dos coinciden en su día de cumpleaños. Pero esto probabilístico está más interesante http://www.youtube.com/watch?v=p_SWxgyeb-s
Ahora mismo, en una ciudad «suficientemente grande» usted encontrará dos personas con la misma cantidad de cabello (Cantidad de cabello ocupable en el cuero cabelludo relacionado con tamaño de población)
Contraintuitivo!? Ah caramba, por qué dicen esa palabra en Matemática!!
Las respuestas a los problemas de la semana siempre se publican aki mismo en los comentarios no?
Sí, Sinuhé.
Perfecto, listo, gracias.
Respondido (parece que todo el mundo ve la misma solución 🙂 y el principio del palomar aquí lo llamamos principio de las casillas) y enviadas varias anécdotas
Saludos gaussianos, gracias por repsonder.
Ahí va mi intento: Si numeramos a cada una de las personas en la fiesta del 1 al , el número de amigos que tiene cada una de ellas se puede definir como una función . Ahora bien, existe una restricción: si existe un tal que , entonces nadie puede tener amigos, y viceversa. Para el primer caso, entonces, la imagen de la función es el conjunto , para el segundo caso la imagen es el conjunto , y cuando ninguno de los dos casos se presenta, la imagen es el conjunto . En cualquier caso, el conjunto imagen tiene… Lee más »