Autor Tema: Problema de los caballos

0 Usuarios y 1 Visitante están viendo este tema.

31 Julio, 2018, 02:31 pm
Leído 5749 veces

Rectilíneo

  • Aprendiz
  • Mensajes: 417
  • Karma: +0/-0
  • Sexo: Masculino
  • Don't go to the bathroom, Vincent
Hola,

disponemos de 25 caballos mecánicos y un solo circuito de carreras. Cada caballo completa el circuito en un cierto tiempo preprogramado (todos diferentes, no hay posibilidad de empate). Puedes hacer carreras de hasta 5 caballos a la vez. Cuando una carrera acaba obtienes una lista con los resultados (el caballo A ha acabado primero, el caballo D ha acabado segundo, etc.) pero nunca conoces el tiempo que ha tardado cada uno.

a) ¿Cuál es el número mínimo de carreras para saber cuales son los 3 caballos más rápidos?


Quiero ver vuestras soluciones del problema, mi respuesta al primer apartado es 7 carreras.

01 Agosto, 2018, 05:11 am
Respuesta #1

delmar

  • Moderador Global
  • Mensajes: 2,155
  • País: pe
  • Karma: +0/-0
  • Sexo: Masculino
Hola Rectilíneo

Mi respuesta también es 7 carreras.

Spoiler
Supongamos los caballos numerados del 1 al 25, este número los identifica, cada caballo tiene  una velocidad, esta velocidad como función del número identificador es inyectiva (hay 25 velocidades todas diferentes), entonces se tiene \( v_1,v_2, ...v_{25} \) en donde \( v_i \) es la velocidad del caballo i.Todos los caballos tienen que correr en al menos una carrera y a mayor número de competidores por carrera, menor número de carreras. Dividamos los 25 caballos en grupos de 5, podemos usar sus velocidades como identificadores de los caballos, por ejemplo :

\( A=\left\{{v_1,v_2,v_3,v_4,v_5} \right\} \), \( B=\left\{{v_6,v_7,v_8,v_9,v_{10}} \right\} \), ... , \( E=\left\{{v_{21},v_{22},v_{23},v_{24},v_{25}} \right\} \)

Después de formados los grupos se realizan las carreras de los distintos grupos, A,B,C,D,E, en total 5 carreras y se seleccionan, los ganadores de cada grupo. Denominemos al grupo de los ganadores  \( G=\left\{{v_a,v_b,v_c,v_d,v_e}\right\} \) donde \( v_a,v_b,v_c,v_d,v_e \) son los ganadores de los grupos A,B,C,D,E respectivamente.

Se hace una nueva carrera con los caballos del grupo G, supongamos que el resultado es \( (v_c,v_d,v_a,v_b,v_e) \), el caballo c es el más rápido de los 25, los caballos d y a, son los únicos que tienen la esperanza de ser el segundo y tercero más rápidos de los 25. Para averiguarlo, se ha de efectuar una última carrera, carrera 7, en donde los caballos d y a competirán con aquellos con los que no han competido y que tampoco se puede deducir si son más rapidos, es decir con los 2 que le siguen al caballo c en su grupo C denominando x y z, se tiene que el nuevo grupo es : \( H=\left\{{d,a,x,z}\right\} \) acá se tienen las siguientes alternativas :

1)\( v_a>v_x \) implica que los tres más rápidos son  : \( (c,d,a) \) en ese orden.

2)\( v_z<v_a<v_x \) hay dos alternativas adicionales :

   2.1) \( v_d>v_x \) implica que los tres más rápidos son : \( (c,d,x) \)

   2.2) \( v_d<v_x \) implica que los tres más rápidos son : \( (c,x,d) \)

3) \( v_a<v_z \) hay  alternativas adicionales :
    3.1)\( v_d<v_z \) implica que los tres más rápidos son : \( (c,x,z) \)
    3.2)\( v_z<v_d<v_x \)  implica que los tres más rápidos son : \( (c,x,d) \)
    3.3)\( v_x<v_d \) implica que los tres más rápidos son : \( (c,d,x) \)

Es decir en todas las alternativas que pueden resultar de la carrera 7, se llega a conocer a los tres más rápidos de los 25
[cerrar]

Saludos

01 Agosto, 2018, 01:58 pm
Respuesta #2

martiniano

  • Héroe
  • Mensajes: 1,219
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Hola.
los caballos d y a, son los únicos que tienen la esperanza de ser el segundo y tercero más rápidos de los 25. Para averiguarlo, se ha de efectuar una última carrera, carrera 7, en donde los caballos d y a competirán con aquellos con los que no han competido y que tampoco se puede deducir si son más rapidos, es decir con los 2 que le siguen al caballo c en su grupo C

¿Cómo sabes, delmar que en el grupo B, por ejemplo, no hay nadie más rápido que el segundo o tercero del grupo C?

Saludos.

01 Agosto, 2018, 08:29 pm
Respuesta #3

delmar

  • Moderador Global
  • Mensajes: 2,155
  • País: pe
  • Karma: +0/-0
  • Sexo: Masculino
Hola.
los caballos d y a, son los únicos que tienen la esperanza de ser el segundo y tercero más rápidos de los 25. Para averiguarlo, se ha de efectuar una última carrera, carrera 7, en donde los caballos d y a competirán con aquellos con los que no han competido y que tampoco se puede deducir si son más rapidos, es decir con los 2 que le siguen al caballo c en su grupo C

¿Cómo sabes, delmar que en el grupo B, por ejemplo, no hay nadie más rápido que el segundo o tercero del grupo C?

Saludos.



Eso es otro problema, con lo que he descrito esta indeterminado, se tendría que estudiar. Lo que si es cierto, es  que ningún caballo del grupo B, tiene esperanza de ser uno de los tres más rápidos de los 25 (en realidad de ser el segundo o tercero por que el primero es el caballo c). La razón esta en los resultados de la carrera 6, la que efectúan los ganadores de las primeras 5 carreras grupo \( G=\left\{{v_a,v_b,v_c,v_d,v_e}\right\} \), el resultado es la 5-plus ordenada \( (v_c,v_d,v_a,v_b,v_e) \), ahí  vemos  que el más rápido del grupo B, caballo b, con velocidad \( v_b \), esta en cuarto lugar. Cualquier otro caballo del grupo B, estará en un lugar menor. No hay necesidad de hacer competir a alguno de los caballos del grupo B, con el segundo o tercero del C, para conocer a los tres más rápidos de los 25.

Saludos

01 Agosto, 2018, 09:13 pm
Respuesta #4

Rectilíneo

  • Aprendiz
  • Mensajes: 417
  • Karma: +0/-0
  • Sexo: Masculino
  • Don't go to the bathroom, Vincent
Hola Rectilíneo

Mi respuesta también es 7 carreras.

Spoiler
Supongamos los caballos numerados del 1 al 25, este número los identifica, cada caballo tiene  una velocidad, esta velocidad como función del número identificador es inyectiva (hay 25 velocidades todas diferentes), entonces se tiene \( v_1,v_2, ...v_{25} \) en donde \( v_i \) es la velocidad del caballo i.Todos los caballos tienen que correr en al menos una carrera y a mayor número de competidores por carrera, menor número de carreras. Dividamos los 25 caballos en grupos de 5, podemos usar sus velocidades como identificadores de los caballos, por ejemplo :

\( A=\left\{{v_1,v_2,v_3,v_4,v_5} \right\} \), \( B=\left\{{v_6,v_7,v_8,v_9,v_{10}} \right\} \), ... , \( E=\left\{{v_{21},v_{22},v_{23},v_{24},v_{25}} \right\} \)

Después de formados los grupos se realizan las carreras de los distintos grupos, A,B,C,D,E, en total 5 carreras y se seleccionan, los ganadores de cada grupo. Denominemos al grupo de los ganadores  \( G=\left\{{v_a,v_b,v_c,v_d,v_e}\right\} \) donde \( v_a,v_b,v_c,v_d,v_e \) son los ganadores de los grupos A,B,C,D,E respectivamente.

Se hace una nueva carrera con los caballos del grupo G, supongamos que el resultado es \( (v_c,v_d,v_a,v_b,v_e) \), el caballo c es el más rápido de los 25, los caballos d y a, son los únicos que tienen la esperanza de ser el segundo y tercero más rápidos de los 25. Para averiguarlo, se ha de efectuar una última carrera, carrera 7, en donde los caballos d y a competirán con aquellos con los que no han competido y que tampoco se puede deducir si son más rapidos, es decir con los 2 que le siguen al caballo c en su grupo C denominando x y z, se tiene que el nuevo grupo es : \( H=\left\{{d,a,x,z}\right\} \) acá se tienen las siguientes alternativas :

1)\( v_a>v_x \) implica que los tres más rápidos son  : \( (c,d,a) \) en ese orden.

2)\( v_z<v_a<v_x \) hay dos alternativas adicionales :

   2.1) \( v_d>v_x \) implica que los tres más rápidos son : \( (c,d,x) \)

   2.2) \( v_d<v_x \) implica que los tres más rápidos son : \( (c,x,d) \)

3) \( v_a<v_z \) hay  alternativas adicionales :
    3.1)\( v_d<v_z \) implica que los tres más rápidos son : \( (c,x,z) \)
    3.2)\( v_z<v_d<v_x \)  implica que los tres más rápidos son : \( (c,x,d) \)
    3.3)\( v_x<v_d \) implica que los tres más rápidos son : \( (c,d,x) \)

Es decir en todas las alternativas que pueden resultar de la carrera 7, se llega a conocer a los tres más rápidos de los 25
[cerrar]

Saludos

Hola delmar

Estoy de acuerdo con tu razonamiento, he tenido que adaptarme a tu notación pero lo he acabado entendiendo. No obstante creo que te has dejado un posible caballo TOP3 en la última carrera:

Para averiguarlo, se ha de efectuar una última carrera, carrera 7, en donde los caballos d y a competirán con aquellos con los que no han competido y que tampoco se puede deducir si son más rapidos, es decir con los 2 que le siguen al caballo c en su grupo C denominando x y z, se tiene que el nuevo grupo es : \( H=\left\{{d,a,x,z}\right\} \)

El grupo \( H \) también debería incluir al segundo caballo más rápido del grupo \( D \), llamémosle y. Los únicos dos caballos más rápidos que éste (al finalizar la carrera 6) son el ganador c y el primero de su carrera inicial d. Puede que y sea más rápido que x, z y a, ya que todavía no ha habido enfrentamiento directo entre ellos.

Por tanto \( H=\left\{{d,a,x,z,y}\right\} \) y surgen más alternativas que las que has planteado. Lo que está claro es que son necesarias 7 carreras como mínimo para conocer cuáles son los 3 caballos más rápidos.

Saludos.

01 Agosto, 2018, 09:26 pm
Respuesta #5

martiniano

  • Héroe
  • Mensajes: 1,219
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Hola.
los caballos d y a, son los únicos que tienen la esperanza de ser el segundo y tercero más rápidos de los 25. Para averiguarlo, se ha de efectuar una última carrera, carrera 7, en donde los caballos d y a competirán con aquellos con los que no han competido y que tampoco se puede deducir si son más rapidos, es decir con los 2 que le siguen al caballo c en su grupo C

¿Cómo sabes, delmar que en el grupo B, por ejemplo, no hay nadie más rápido que el segundo o tercero del grupo C?

Saludos.



Eso es otro problema, con lo que he descrito esta indeterminado, se tendría que estudiar. Lo que si es cierto, es  que ningún caballo del grupo B, tiene esperanza de ser uno de los tres más rápidos de los 25 (en realidad de ser el segundo o tercero por que el primero es el caballo c). La razón esta en los resultados de la carrera 6, la que efectúan los ganadores de las primeras 5 carreras grupo \( G=\left\{{v_a,v_b,v_c,v_d,v_e}\right\} \), el resultado es la 5-plus ordenada \( (v_c,v_d,v_a,v_b,v_e) \), ahí  vemos  que el más rápido del grupo B, caballo b, con velocidad \( v_b \), esta en cuarto lugar. Cualquier otro caballo del grupo B, estará en un lugar menor. No hay necesidad de hacer competir a alguno de los caballos del grupo B, con el segundo o tercero del C, para conocer a los tres más rápidos de los 25.


Tienes toda la razón. Mi crítica era inadecuada.

Saludos y gracias  ;)

02 Agosto, 2018, 12:27 am
Respuesta #6

delmar

  • Moderador Global
  • Mensajes: 2,155
  • País: pe
  • Karma: +0/-0
  • Sexo: Masculino




Estoy de acuerdo con tu razonamiento, he tenido que adaptarme a tu notación pero lo he acabado entendiendo. No obstante creo que te has dejado un posible caballo TOP3 en la última carrera:

Para averiguarlo, se ha de efectuar una última carrera, carrera 7, en donde los caballos d y a competirán con aquellos con los que no han competido y que tampoco se puede deducir si son más rapidos, es decir con los 2 que le siguen al caballo c en su grupo C denominando x y z, se tiene que el nuevo grupo es : \( H=\left\{{d,a,x,z}\right\} \)

El grupo \( H \) también debería incluir al segundo caballo más rápido del grupo \( D \), llamémosle y. Los únicos dos caballos más rápidos que éste (al finalizar la carrera 6) son el ganador c y el primero de su carrera inicial d. Puede que y sea más rápido que x, z y a, ya que todavía no ha habido enfrentamiento directo entre ellos.

Por tanto \( H=\left\{{d,a,x,z,y}\right\} \) y surgen más alternativas que las que has planteado. Lo que está claro es que son necesarias 7 carreras como mínimo para conocer cuáles son los 3 caballos más rápidos.

Saludos.

Es correcto lo que dices Rectilíneo, ya me parecía raro que en la carrera 7, solamente compitan 4 caballos, hay que incluir al segundo del grupo D, en la última carrera.

Saludos

02 Agosto, 2018, 08:23 am
Respuesta #7

martiniano

  • Héroe
  • Mensajes: 1,219
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Hola

Por tanto \( H=\left\{{d,a,x,z,y}\right\} \) y surgen más alternativas que las que has planteado. Lo que está claro es que son necesarias 7 carreras como mínimo para conocer cuáles son los 3 caballos más rápidos.

Pero al final bastaría quedarse con los dos primeros del grupo H y el primero del grupo G, ¿no? ¿O me he vuelto a despistar?

Saludos.

02 Agosto, 2018, 04:11 pm
Respuesta #8

Rectilíneo

  • Aprendiz
  • Mensajes: 417
  • Karma: +0/-0
  • Sexo: Masculino
  • Don't go to the bathroom, Vincent
Pero al final bastaría quedarse con los dos primeros del grupo H y el primero del grupo G, ¿no? ¿O me he vuelto a despistar?

Exactamente, el caballo más rápido es el primero del grupo G y el segundo y tercer caballo más rápidos son los que han quedado primero y segundo del grupo H.

Ahora viene el siguiente apartado:
b) ¿Cuál es el número mínimo de carreras para saber cuales son los 4 caballos más rápidos?

No tengo clara la respuesta. Espero ver vuestros razonamientos.

Saludos.

19 Agosto, 2018, 02:33 pm
Respuesta #9

Rectilíneo

  • Aprendiz
  • Mensajes: 417
  • Karma: +0/-0
  • Sexo: Masculino
  • Don't go to the bathroom, Vincent

19 Agosto, 2018, 03:08 pm
Respuesta #10

martiniano

  • Héroe
  • Mensajes: 1,219
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Venga, anímate a subir algo tú, para romper el hielo  :)


19 Agosto, 2018, 09:21 pm
Respuesta #11

Rectilíneo

  • Aprendiz
  • Mensajes: 417
  • Karma: +0/-0
  • Sexo: Masculino
  • Don't go to the bathroom, Vincent
Voy a usar una notación diferente a la de delmar.

Tenemos 25 caballos y hacemos 5 grupos de 5. Se hará una carrera por cada grupo de caballos. Con los ganadores de cada una de ellas se hará otra carrera (llevamos un total de 6). Las posiciones quedan tal que así:

\begin{bmatrix} a_{5} & a_{4} & a_{3} & a_{2} & a_{1} \\ b_{5} & b_{4} & b_{3} & b_{2} & b_{1} \\ c_{5} & c_{4} & c_{3} & c_{2} & c_{1} \\ d_{5} & d_{4} & d_{3} & d_{2} & d_{1} \\ e_{5} & e_{4} & e_{3} & e_{2} & e_{1}\end{bmatrix}

donde en las primeras 5 carreras se han decidido las posiciones de cada fila de la matriz y en la última carrera se ha decidido las posiciones de las filas.

En este punto ya sabemos cuál es el caballo más rápido: \( a_{1} \). Los candidatos al 2o, 3r y 4o puesto son: \( a_{2-4} \), \( b_{1-3} \), \( c_{1-2} \) y \( d_{1} \), un total de \( 3+3+2+1=9 \) caballos.
Ahora la pregunta ha pasado a ser: ¿cuántas carreras son necesarias para saber cuales son los 3 caballos más rápidos de un grupo de 9? ¿Os parece bien encaminada mi resolución de momento?

Saludos.

20 Agosto, 2018, 01:45 am
Respuesta #12

martiniano

  • Héroe
  • Mensajes: 1,219
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Hola.

Sí, justo a esta situación he llegado yo también y es en la que considero que me he acercado más. No obstante, creo que a partir de aquí hacen falta tres carreras con las condiciones del enunciado para resolver, pero me mosquea que si en una carrera pudieras hacer competir a cuatro caballos y en otra a seis, se podría resolver en sólo dos carreras más. Haciendo competir en la siguiente carrera a \( a_4,\,b_3,\,c_2 \) y \( d_1 \) y en la última a los seis candidatos a segundo, tercero o cuarto puesto (acabe como acabe la penúltima carrera siempre salen seis).

Me parece muy complicado demostrar que no existe una estrategia que te permita decidir qué caballos son los 4 más rápidos con sólo 8 carreras, tampoco parece fácil encontrar una estrategia concluyente que utilice 8 carreras. Sin embargo, creo que con tiempo se podría programar un código que arrojase la respuesta, ya que no parecen tantas combinaciones para un ordenador (si las máquinas de los 90 ganaron al ajedrez a Kasparov, yo creo que las actuales con esto pueden).  :D

Saludos.

21 Agosto, 2018, 01:53 pm
Respuesta #13

Rectilíneo

  • Aprendiz
  • Mensajes: 417
  • Karma: +0/-0
  • Sexo: Masculino
  • Don't go to the bathroom, Vincent
Hola,

Sí, justo a esta situación he llegado yo también y es en la que considero que me he acercado más. No obstante, creo que a partir de aquí hacen falta tres carreras con las condiciones del enunciado para resolver, pero me mosquea que si en una carrera pudieras hacer competir a cuatro caballos y en otra a seis, se podría resolver en sólo dos carreras más. Haciendo competir en la siguiente carrera a \( a_4,\,b_3,\,c_2 \) y \( d_1 \) y en la última a los seis candidatos a segundo, tercero o cuarto puesto (acabe como acabe la penúltima carrera siempre salen seis).

No entiendo por qué solo hacen falta 9 carreras en total. Si no te he entendido mal:

- Haces una carrera con los candidatos a cuarto puesto: \( a_4,\,b_3,\,c_2 \) y \( d_1 \). Suponemos que gana \( c_2 \).
- Ahora tenemos 6 caballos: \( \left\{{a_2,\,a_3,\,b_1,\,b_2,\,c_1,\,c_2}\right\} \)

¿Cómo decides el segundo, tercer y cuarto puesto en solo 2 carreras más?

Me parece muy complicado demostrar que no existe una estrategia que te permita decidir qué caballos son los 4 más rápidos con sólo 8 carreras, tampoco parece fácil encontrar una estrategia concluyente que utilice 8 carreras. Sin embargo, creo que con tiempo se podría programar un código que arrojase la respuesta, ya que no parecen tantas combinaciones para un ordenador (si las máquinas de los 90 ganaron al ajedrez a Kasparov, yo creo que las actuales con esto pueden).  :D

Con 8 carreras creo que es imposible. Eso sí, este problema seguro que es programable y que un ordenador te puede dar la respuesta en muy poco tiempo.

Saludos.

21 Agosto, 2018, 03:15 pm
Respuesta #14

martiniano

  • Héroe
  • Mensajes: 1,219
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Hola

- Ahora tenemos 6 caballos: \( \left\{{a_2,\,a_3,\,b_1,\,b_2,\,c_1,\,c_2}\right\} \)

¿Cómo decides el segundo, tercer y cuarto puesto en solo 2 carreras más?

Quizás me esté equivocando, pero haciendo competir a 5 de ellos en una carrera y luego a los cuatro últimos de esta con el que faltaba. Lo que el enunciado sólo te pide distinguir a los cuatro primeros, ¿no? no que los ordenes...

Saludos.

21 Agosto, 2018, 04:37 pm
Respuesta #15

Rectilíneo

  • Aprendiz
  • Mensajes: 417
  • Karma: +0/-0
  • Sexo: Masculino
  • Don't go to the bathroom, Vincent
Quizás me esté equivocando, pero haciendo competir a 5 de ellos en una carrera y luego a los cuatro últimos de esta con el que faltaba. Lo que el enunciado sólo te pide distinguir a los cuatro primeros, ¿no? no que los ordenes...

Cierto. En el caso de los 3 primeros sí que quedaban ordenados pero no es algo que te pida el enunciado. Entonces son 9 las carreras necesarias para saber cuáles son los 4 caballos más rápidos. Siguiente apartado:

c) ¿Cuál es el número mínimo de carreras para saber cuales son los \( n \) caballos más rápidos? Siendo \( {1}\leq{n}<{25} \).

Si no hay que ordenarlos hay simetría en las soluciones: se necesitan las mismas carreras para hallar el caballo más rápido como para hallar los 24 caballos más rápidos (que equivale a saber cuál es el más lento). Por tanto solo hay que preocuparse de \( {1}\leq{n}<{13} \).
Hay que intentar encontrar un patrón en las soluciones y escribir la fórmula que nos proporciona el número de carreras necesarias en función de \( n \).

Este apartado es más complicado :-\

Saludos.

21 Agosto, 2018, 07:09 pm
Respuesta #16

martiniano

  • Héroe
  • Mensajes: 1,219
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
Hola

Siguiente apartado:

c) ¿Cuál es el número mínimo de carreras para saber cuales son los \( n \) caballos más rápidos? Siendo \( {1}\leq{n}<{25} \).

Esta pregunta me deja petrificado  :o. Yo que pensaba que no era factible demostrar con certeza que para el apartado b) se necesitan más de 8 carreras y ahora esto, jajaja... Pues no sé, debe haber algo que estamos pasando por alto...

Si no hay que ordenarlos hay simetría en las soluciones: se necesitan las mismas carreras para hallar el caballo más rápido como para hallar los 24 caballos más rápidos (que equivale a saber cuál es el más lento). Por tanto solo hay que preocuparse de \( {1}\leq{n}<{13} \).

Interesante, desde luego. Pero aún así tela marinera...

Hay que intentar encontrar un patrón en las soluciones y escribir la fórmula que nos proporciona el número de carreras necesarias en función de \( n \).

Sí, y luego demostrar que el patrón es correcto...

Este apartado es más complicado :-\

Estoy de acuerdo   :)

Saludos.

21 Agosto, 2018, 07:27 pm
Respuesta #17

Rectilíneo

  • Aprendiz
  • Mensajes: 417
  • Karma: +0/-0
  • Sexo: Masculino
  • Don't go to the bathroom, Vincent
A ver si algún genio nos ilumina martiniano :laugh:

Yo estaré trabajando en ello en mis ratos libres. No hay mejor pasatiempo que un buen problema matemático.

Saludos!

21 Agosto, 2018, 07:29 pm
Respuesta #18

martiniano

  • Héroe
  • Mensajes: 1,219
  • País: es
  • Karma: +2/-0
  • Sexo: Masculino
A ver si algún genio nos ilumina martiniano :laugh:

A ver, a ver...

Yo estaré trabajando en ello en mis ratos libres. No hay mejor pasatiempo que un buen problema matemático.

Desde luego que sí.  :)

Saludos.