Chicos y chicas resolviendo problemas

Vamos con el problema semanal, cuyo enunciado a su vez trata de resolver problemas. Ahí va:

Veintiún chicos y veintiún chicas participan en una competición de resolución de problemas matemáticos. Analizando los resultados se observa que cada participante ha resuelto como mucho 6 problemas y también que si tomamos cualquier pareja chico-chica hay al menos un problema que fue resuelto por los dos.

La cuestión consiste en demostrar que hay un problema que fue resuelto por al menos tres chicos y tres chicas.

A por él.

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.

23 Comentarios

  1. No soy matemático, asique disculpen los fallos de formalidad, pero creo que sé mas o menos como puede ir el tema:
    Del comentario “también que si tomamos cualquier pareja chico-chica hay al menos un problema que fue resuelto por los dos” creo que podemos sacar la información de que todos han resuelto como mínimo un problema, por tanto cada uno a resuelto de 1 a 6 problemas y que si encontramos 3 chic@s que hayan resuelto el mismo problema entonces podremos asegurar que hay 3 chic@s que han resuelto el mismo problema.
    Asique el problema queda reducido a demostrar que al menos 3 chic@s han resuelto el mismo problema.

    Sabiendo esto, podemos decir que para poder aplicar el principio del palomar necesitamos un mínimo de 7 personas intentando resolverlo.
    Al tener 21 chic@s 7×3, podemos decir que por lo menos 3 de esos 21 resolvieron el mismo problema, por tanto: hay un problema que fue resuelto por al menos tres chicos y tres chicas.

    Publica una respuesta
  2. Creo que hay algún fallo en mi razonamiento porque no me casan los números, pero no soy capaz de encontrarlo.
    Cojamos al primero de los chicos, que habrá resulto x problemas con 1 <= x <= 6. Cogemos también a la primera de las chicas, que sabemos que tiene al menos un problema en común con el chico, y fijamos ese problema.
    Ahora bien, cualquier chica que cojamos tiene al menos un problema en común con el chico, luego si cogemos otras x chicas tendremos al menos dos que hayan resuelto el problema en cuestión, y si cogemos 2x tendremos al menos tres. Como 2 <= 2x <= 12 podemos asegurar que hay al menos un chico y tres chicas que han resuelto ese problema.
    Pero si usamos un razonamiento análogo, la primera de las tres chicas habrá resuelto y problemas (incluyendo el nuestro) con 1 <= y <= 6, así que si tomamos y + 1 chicos distintos del primero habrá al menos dos que también lo hayan resuelto, y demostramos así que hay al menos tres chicos y tres chicas que lo han resuelto.
    Digo que no me casan los números porque según este razonamiento se podría demostrar que al menos cuatro chicos y chicas lo han resuelto (3 <= 3x <= 18).
    Saludos.

    Publica una respuesta
  3. Daniel, tu demostración creo que no es correcta o no la entendí bien.

    Dices “si encontramos 3 chic@s que hayan resuelto el mismo problema entonces podremos asegurar que hay 3 chic@s que han resuelto el mismo problema.”

    Pero creo que eso lo afirmas muy precipitadamente sin dar ninguna prueba.

    Por ejemplo, supongamos que el problema fuesen 4 chicos (A, B, C, D) y 4 chicas (e, f, g, h) … y nos dicen que cada par tiene al menos un problema que han resuelto ambos.

    A = “0011” = {1, 2}
    B = “0101” = {1, 4}
    C = “1010” = {2, 8}
    D = “1001” = {1, 8}

    e = “1110” = {2, 4, 8}
    f = “1110” = {2, 4, 8}
    g = “1110” = {2, 4, 8}
    h = “1110” = {2, 4, 8}

    En este ejemplo se puede ver que cada pareja chico chica tiene al menos un problema coincidente. (en este caso las chicas han resuelto los mismos, {2, 4, 8} y para cada chico le basta tener uno de esos para coincidir con cada una de las chicas)

    Sin embargo, el problema 1 hay 2 chicos que lo han resuelto pero no hay 2 chicas que lo hayan resuelto, de hecho ninguna resolvió el problema 1.

    Es decir, que haya chicos que resuelvan un mismo problema no significa que ESE problema sea uno de los que tienen que compartir cada uno con una chica.

    Respecto al principio del palomar tampoco creo que se aplique bien.
    Para asegurar que haya 2 chicos que han resuelto el mismo problema debería haber 6 problemas en total y entonces sí necesitarías 7 chicos para asegurarlo. Pero el número de problemas no nos dicen cuál es, pueden ser 7 problemas ó 42 o cualquier otro número… y si son más de 6 puede haber 7 chicos que hayan resuelto cada uno un problema diferente sin compartir ninguno. Si son 21 problemas diferentes cada chico puede haber resuelto sólo 1 (mayor o igual que 1 y menor que 6) pero que no haya siquiera dos que hayan resuelto el mismo.

    Lo que dice _cronos2 me convence más.

    Publica una respuesta
  4. Acido, lo que comentas en el último párrafo no es del todo cierto… Si cogemos 7 chicos y 1 chica, dado que la chica ha resuelto como mucho 6 problemas y comparte al menos un problema con cada uno los 7 chicos, tenemos (por el principio del Palomar) que al menos dos chicos habrán resuelto el mismo problema…

    Publica una respuesta
  5. Marco,
    tú sí que lo has explicado… pero mi crítica a Daniel es que no nombró a las chicas. Dijo que quiere demostrar que al menos 3 chicos han resuelto el mismo problema y nombra el principio del palomar y el número 7 pero no dice por qué. Y luego dice 7 * 3 = 21 y se queda tan ancho xD Es decir, no digo que el principio del palomar no se pueda aplicar… lo que digo es que falta explicar por qué se aplica, como tú lo explicaste.

    Publica una respuesta
  6. Buenas Ácido, gracias por corregirme, esta claro que he abordado el problema de una forma precipitada.

    _cronos2, hay algo que no entiendo del todo, dices que hay 3 chicos que resuelven el mismo problema que 1 chica y que hay 3 chicas que resuelven el mismo problema que un chico, pero esto implicaría que 3 chicos resolvieran el mismo problema que 3 chicas?

    Publica una respuesta
  7. No estoy seguro de que sea correcto pero para empezar trataría determinar el número máximo de preguntas diferentes que puede haber.
    Para ello supongamos que un alumno (A) responde 6 diferentes. Esto hace que una alumna (B) tenga que coincidir en (como mínimo) una de las preguntas con A lo cual hace que haya como máximo 10 preguntas diferentes. Si seguimos así vemos que a partir de la alumna 6 todas sus preguntas respondidas están condicionas por las preguntas respondidas por los 6 alumnos anteriores. En definitiva tenemos que las preguntas libres máximas haciendo que coincidan el mínimo de respuestas es 6^2=36 (Se ve mucho más claro con un diagrama en el que se van anotando las dependencias de las soluciones.)

    Una vez sabido este dato puedo dividir el grupo de 21 alumnos en tres subgrupos e igual con las alumnas haciendo que cada grupo tenga los suficientes alumnos como para que tengan entre ellos todas las respuestas posibles (Por ejemplo tres grupos con 6,6,9 alumnos o alumnas. Todos ellos tienen 36 o más respuestas diferentes).

    Se puede ver (De nuevo, con un buen diagrama es mucho más claro) que cogiendo alumnos de diferentes grupos, pero al menos tres de los chicos y tres de las chicas, todas las respuestas diferentes quedan abarcadas por los seis chicos escogidos.

    Publica una respuesta
  8. “(Por ejemplo tres grupos con 6,6,9 alumnos o alumnas. Todos ellos tienen 36 o más respuestas diferentes)” Perdón, quería decir que todos ellos tienen las 36 respuestas diferentes o ya repetidas

    Publica una respuesta
  9. Parece claro que, una vez aceptado que solo puede haber 36 problemas distintos como máximo, con 18 alumnos y 18 alumnas ya se cumple que hay al menos uno resueltopor tres de cada sexo.

    Publica una respuesta
  10. Un sujeto hizo dos récord en el mismo día, lo cual constituyó un récord, pero ahora tiene tres récords, lo cual a su vez constituye un récord. ¿Cuántos récord en total tiene el sujeto en un mismo día?

    Publica una respuesta
  11. No sé si es cosa mía, pero a mí no me parece que esté claro ese límite de 36 respuestas, ni que de ahí se deduzca lo que se pide demostrar.

    Publica una respuesta
  12. Me explico mejor, a ver si me he equivocado en algo:
    Lo que sucede es que, si hubiera más preguntas, podríamos encontrar parejas de alumnos y alumnas que no coincidieran en ninguna pregunta y sin embargo sabemos que eso no sucede. Puede que haya menos, en cuyo caso juego a favor de lo que pretendo demostrar, pero no puede haber más.

    Para verlo mejor voy a expresar a los chicos como el grupo A y las chicas como el B. Al lado de cada uno, dentro del paréntesis escribo (Número de preguntas que han salido en otros concursantes (Dependientes), número de preguntas que son nuevas(Independientes)).

    A1 (0,6)
    B1 (1,5)

    A2 (1,5)
    B2 (2,4)

    A3 (2,4)
    B3 (3,3)

    A4 (3,3)
    B4 (4,2)

    Y así hasta que los B6 y A7 tienen (6,0). El computo de preguntas “diferentes” viene dado por el número de la derecha mientras que el de la izquierda no aporta porque son todos repeticiones. Al final queda un sumatorio de 1 hasta 5 y otro de 1 hasta 6 (Chicas y chicos respectivamente) que si resolvemos mediante la famosa formulita de gauss s=[n(n+1)/2] +[(n-1)n/2] donde n=6 queda s=n^2=36.

    En conclusión, si todos hubieran respondido 6 preguntas el máximo sería 36 pero como puede haber alumnos que hayan respondido menos diremos que el número máximo de preguntas es menor o igual a 36.

    Publica una respuesta
  13. El número máximo de problemas es 36, una forma de verlo es la siguiente:
    Sean los chicos A_1,A_2,…,A_21, las chicas B_1,B_2,…B_21 y los problemas P_1,P_2,…, Para establecer el número máximo de problemas supongamos que todos los chicos y chichas han resuelto 6 problemas (el máximo posible). Podemos escoger que los seis primeros chicos A_1,…,A_6 hayan resuelto todos problemas distintos (no podemos suponer esto para 7 o más chicos como expliqué en mi comentario anterior). Entonces:
    – A_1 ha resuelto los problemas P_1,…P_6
    – A_2 ha resuelto los problemas P_7,…P_12
    – A_3 ha resuelto los problemas P_13,…P_18
    – A_4 ha resuelto los problemas P_19,…P_24
    – A_5 ha resuelto los problemas P_25,…P_30
    – A_6 ha resuelto los problemas P_31,…P_36
    Ahora, está claro que como cada chica B_i ha de tener al menos un problema en común con cada uno de los chicos A_1,…,A_6, entonces los problemas resueltos por cada chica B_i pertenecen al conjunto de problemas P_1,…P_36. Razonando de forma similar, los problemas resueltos por el resto de los chicos A_7,…,A_21 también han de pertenecer a P_1,…P_36. Entonces se han resuelto como máximo 36 problemas distintos.

    Publica una respuesta
  14. Sobre a cómo de ahí se deduce lo que se pretende demostrar cogeremos el caso más extravagante, el de los A1, B1, A2, B2, A3, B3, que se corresponden con los de la lista anterior. Sumando el número de preguntas diferentes que pueden tener vemos que da 6+5+5+4+4+3=27 y el resto de respuestas (9) serán dependientes. Bien pues en este caso no hay una, sino 27 preguntas que fueron respondidas por al menos 3 A y 3 B. Claro, podría haber menos de seis respuestas por alumno. En ese caso el número máximo de preguntas formuladas sería menor lo que juega a mi favor.

    Publica una respuesta
  15. Si lo que decís es simplemente esto:

    – No puede haber más de 36 problemas y que se cumpla que todas las parejas chico-chica han resuelto alguno en común.

    Eso claramente no es así. Por ejemplo, puede pasar que todos (chicos y chicas) hayan resuelto el problema 1 y luego cada participante haya resuelto 5 problemas más que sólo ha resuelto él. Entonces tenemos 211 problemas distintos.

    A lo mejor estáis descartando este caso y otros similares por no ser relevantes para el problema, por algún motivo, pero en ese caso deberíais explicarlo. Yo, en las explicaciones que estáis dando, no lo veo.

    El caso en que hay 6 chicos que no tienen ningún problema en común, es un caso concreto, que no cubre todas las posibilidades.

    Publica una respuesta
  16. Golvano, el ejemplo que pones no altera la solución del problema puesto que hay un problema, el 1, ha sido resuelto por tres o más chocos y chicas.
    La solución propuesta busca las condiciones más desfavorables para evitar que se de el caso solución.

    Publica una respuesta
  17. Si quieres, busca un contraejemplo, con más de 36 problemas, en el que no haya solución.

    Publica una respuesta
  18. Toma claro, si nos piden demostrar algo, será cierto. Yo no estoy diciendo que el enunciado esté mal. Lo que estoy diciendo es que la demostración que estáis dando no es válida.

    Es como si yo propongo la solución: “como dos y dos son cuatro, y cuatro y dos son seis, entonces queda demostrado” y cuando me decís que no es válida os digo: pues buscadme un contraejemplo.

    Si estáis descartando el resto de casos, porque son más desfavorables, tendréis que decir por qué. Así sin más, no queda claro que lo sean, teniendo en cuenta que hay más problemas en los que repartir a los participantes.

    Además, tampoco está claro que el límite de 36 implique lo que se pide.

    Publica una respuesta
  19. Dejando de lado la cantidad de problemas, puesto que para cada pareja chico-chica hay al menos un problema resuelto por los dos, planteo lo siguiente:

    Total de parejas chico-chica: 21 x 21 = 441

    Cada chica tiene 21 “compañeros”, que debe distribuir en 6 problemas como máximo. Luego entonces, por lo menos 11 de esos compañeros están agrupados en “colecciones” de tres o más, es decir:
    5 problemas de 2 chicos: 5 x 2 = 10; 21-10= 11 chicos.

    Para otras distribuciones habrá mas grupos de 3 o más chicos y por ende más de 11 chicos agrupados en “colecciones” de tres o más.

    Así, para las 21 chicas habrá 21 x 11 = 231 parejas que han resuelto un problema donde por lo menos tres CHICOS pueden acreditarse la solución.

    Procediendo de igual forma para los chicos, habrá 21 x 11 = 231 parejas que han resuelto un problema donde por lo menos tres CHICAS pueden acreditarse la solución.

    Habiendo un total de 21 x 21 = 441 parejas chico-chica:

    441 < 231 + 231 = 462

    Luego entonces, debe haber problemas resueltos por al menos tres chicos y tres chicas.

    Publica una respuesta
  20. Muy bien Elchen, esa es la respuesta.
    En efecto, el problema debe verse en una tabla de 21 * 21, Tomamos a un chico en una fila y vamos señalando casillas de dos modos.

    (+) si coincide con tres o más chicas y (-) si ocurre lo contrario.

    A cada chica le haremos lo mismo, en columnas. Se trata en definitiva de encontrar al menos una casilla con dos signos (+).

    Ahí entra en juego el comentario de Elchen. En el peor de los casos, al menos 11 individuos quedan en grupos de 3 ó más (signos +), y eso ocurre en cada fila o columna; porque lo máximo sería que 5 preguntas fueran acertadas por dos personas.
    El recuento total de casillas, y el de signos (+), nos hará ver que hay más signos positivos que casillas, en cuyo caso hay celdas con (++) que implica la demostración del enunciado.

    Publica una respuesta
  21. n chicos y n chicas participan en una competición de resolución de problemas matemáticos. Analizando los resultados se observa que cada participante ha resuelto como mucho p problemas y también que si tomamos cualquier pareja chico-chica hay al menos un problema que fue resuelto por los dos.
    Se cumple siempre que n sea igual o mayor que 4*p-3.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Vamos con el problema semanal, cuyo enunciado a su vez trata de resolver problemas.…

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 *