Amigos en una fiesta

Os traigo hoy miércoles el problema de esta semana. Ahí va el enunciado:

Demostrar que en toda fiesta con n \geq 2 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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

29 Comentarios

  1. 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 amigo de uno de la pareja y no del otro de tal manera que el grupo de n quedará con valor del nº de amigos 0,1,2, … , n-1.

    Dado que ha roto como mínimo un grupo, el nº de amigos del n+1 no puede ser mayor que n-1 (n es el máximo y por lo menos no es amigo de uno), por lo que su nº de amigos coincidirá con alguno de los n iniciales

    Publica una respuesta
  2. Esto se resuelve muy facilmente por el principio del palomar

    Publica una respuesta
  3. 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

    Publica una respuesta
  4. 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” …

    Publica una respuesta
  5. (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 persona que no tiene amigos)
    CONCLUSIÓN
    6) Es imposible que exista al mismo tiempo el caso de 0 amigos y el caso de n-1 amigos por lo tanto el conjunto de posibles casos de amistad en el mejor de los casos será de N-1 distintos con lo que necesariamente dos se repiten

    Publica una respuesta
  6. 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.

    Publica una respuesta
  7. Aunque hemos hecho lo mismo, vuestras soluciones se entienden mucho mas fácilmente que la mía

    Publica una respuesta
  8. 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.

    Publica una respuesta
  9. 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

    Publica una respuesta
  10. Otra variante:

    Asignar a cada persona el número de amigos que tiene en la fiesta, que será un número entre 0 y n-1. Sin embargo, las asignaciones 0 y n-1 no pueden aparecer simultáneamente en una misma fiesta con n participantes. Luego, deben haber dos personas con igual número de amigos.

    Publica una respuesta
  11. M, no creo que has dado con la forma más simple de aplicar el Principio del Palomar en este problema. Muy buena respuesta.

    Publica una respuesta
  12. Vaya, veo que puse esencialmente la misma respuesta que JJGJJG. Siento no haber leído con calma todos los comentarios. Felices fiestas.

    Publica una respuesta
  13. 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 con las j personas a las que si conoce, al que añadimos la recién llegada. Este grupo tendrá entre 2 y n personas y, por hipótesis de inducción, verificará la propiedad.

    Saludos

    Publica una respuesta
  14. 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.

    Publica una respuesta
  15. golvano, tienes razón, mi demostración es incorrecta.
    Agradezco mucho tu observación.
    Saludos.

    Publica una respuesta
  16. 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), cómo va a ser juan amigo de todos los demás (recuérdese no se considera la amistad recursiva (hacia uno mismo!), por eso el conjunto de 0 a n-1)?

    Luego tiene que haber coincidencias en la función que asigna a cada elemento de la fiesta su número de amigos en ella dado a, f(a) en el conjunto de 0 a (n-1), o sea, al menos dos personas con la misma cantidad de amigos, listo!

    Feliz Navidad! Saludos a todos.
    Venezuela, Caracas, 27/12/2012
    Hora de acá:3:33pm

    Publica una respuesta
  17. 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)

    Publica una respuesta
  18. Contraintuitivo!? Ah caramba, por qué dicen esa palabra en Matemática!!

    Publica una respuesta
  19. Las respuestas a los problemas de la semana siempre se publican aki mismo en los comentarios no?

    Publica una respuesta
  20. 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

    Publica una respuesta
  21. Ahí va mi intento:

    Si numeramos a cada una de las n personas en la fiesta del 1 al n, el número de amigos que tiene cada una de ellas se puede definir como una función f:\{1,…,n\}\to\{0,…,n-1\}. Ahora bien, existe una restricción: si existe un n_0 tal que f(n_0)=0, entonces nadie puede tener n-1 amigos, y viceversa. Para el primer caso, entonces, la imagen de la función es el conjunto \{0,…,n-2\}, para el segundo caso la imagen es el conjunto \{1,…,n-1\}, y cuando ninguno de los dos casos se presenta, la imagen es el conjunto \{1,…,n-2\}. En cualquier caso, el conjunto imagen tiene menos elementos que el dominio. Esto implica que f no puede ser invectiva, por lo que deben existir n_1 y n_2 en el dominio tales que f(n_1)=f(n_2).

    Publica una respuesta

Trackbacks/Pingbacks

  1. Las mates, el boli y el papel | Tele Transporte - [...] problema lo han presentado en el blog gaussianos. Lo copio aquí, para que lo [...]
  2. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Os traigo hoy miércoles el problema de esta semana. Ahí va el enunciado: Demostrar…

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.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *