No sé si se puede

[makinavaja]

hola a todos!!!
En un programa de television, no recuerdo el nombre, habia un juego en el cual habia un rectangulo con 21 divisiones (3 de ancho y 7 de largo). El concursante señalaba 7 de los cuadrados pero tenia que señalar uno por fila, despues le daba a un pulsador y le decia cuantos aciertos habia conseguido. Tenia que conseguir un total de siete. La dificultad es que el concursante elegia sus cuadrados y le daba al pulsador y tenia 4 aciertos. Podia volver a cambiarlos todos pero siempre uno por fila.
¿Pero de qué forma cambiarlos subiendo el número de aciertos?

o O o
O o o
O o o
o o O           sirvase este ejemplo representando las "o" minusculas
o O o           lo no elegido, y las "O" mayusculas lo elegido
O o o
o o O

Creo que no se puede saber, pero lo dejo en manos de los expertos.
Un saludo y gracias anticipadas         

[makinavaja]

las casillas no se corresponden, me parece que eran 4x4, pero no creo que sea un dato relevante.

[Jabato]

El criterio más eficaz consiste en suponer siempre una solución compatible con los resultados anteriores.

Es decir que si el concursante ha realizado ya un número determinado de pruebas, n, y no ha acertado, debe plantear una nueva solución, n + 1, que sea compatible con las respuestas que obtuvo en las n  primeras tiradas. No tengo la demostración de que esa sea la mejor opción pero el sentido común en este caso nos dice que siempre será mejor una combinación que cumpla esta condición que una que no la cumpla, ya que es imposible que una que no la cumpla sea la solución correcta.

A medida que el concursante va realizando pruebas fallidas, va obteniendo cada vez más información sobre cual es la solución correcta. Utilizar esta información adecuadamente provoca que el número de opciones se reduzca drasticamente con cada fallo.
 
Saludos, Jabato.

[el_manco]

Hola

 No estoy seguro de que ser refiere Jabato con una solución "compatible con las anteriores".

 Desde luego en una sola jugada es imposible diseñar una estrategia que te aumente el número de aciertos. En todo caso, a corto plazo, habría que hacer un estudio de probabístico de que estragegia aumenta las probabilidades de tener más aciertos.

 Por supongamos que tienes n filas, 3 opciones por fila y k aciertos. Y que modificas 1 casilla.

 Las probabilidades de aumentar los aciertos son:



 Las probabilidades de dejar igual el número de aciertos es:



 Las probabilidad de disminuir:



 De manera qu si teníamos menos de la mitad cambiando una al azar los más probable es no empeorar (lo cual es razonable...)

 Se podría seguir por este camino... puede verse que con dos cambios pasa algo parecido. No ese si se llega a algo manejable generalizando esto.

Saludos.

[Jabato]

Pues explico que significa "compatible con la anteriores.

Supongamos que se ha realizado ya una tirada y la respuesta ha sido 4 aciertos. El jugador tiene ahora la opción de cambiar todas las filas y seleccionar una nueva combinación, pero la nueva combinación, en caso de ser la correcta, debería reproducir 4 aciertos con la primera tirada, puesto que esa fué la respuesta que obtuvo el jugador. No todas las combinaciones que puede elegir presentan esa característica, de forma que el número de opciones se reduce.

Si vuelve a fallar obteniendo ahora 5 aciertos, entonces podrá volver a elegir una nueva combinación, y suponiendo que esa sea la correcta, dicha combinación debería reproducir 4 aciertos con la primera tirada y 5 aciertos con la segunda, lo que reduce ya de forma drástica el número de posibilidades a la hora de elegirla, puesto que cualquier combinación que no reproduzca las mismas respuestas en las dos tiradas anteriores debe ser descartada, ya que es imposible que sea la correcta.

Un nuevo fallo le permitirá volver a aplicar el método eligiendo siempre una nueva combinación que sea compatible con las respuestas obtenidas en las anteriores tiradas.

El método resulta ser muy efectivo ya que conduce rapidamente a la solución al descartar un elevado número de posibilidades en muy pocas tiradas.

Sinceramente creo que será difícil encontrar un algoritmo más eficaz que éste, ya que éste utiliza toda la información que recibe el jugador, aunque no parece fácil demostrar tal extremo.

Saludos, Jabato.

[el_manco]

Hola

 Sigo sin entenderte. Fíjate que el problema fundamental es que le dicen el número de aciertos pero NO donde están (bueno yo al menos lo entiende así porque vi algún concurso parecido - maldita teleadicción  ). Entonces no tiene forma de saber en la segunda jugada que cambiar y que conservar. No se si tu lo has considerado así.

Saludos.

[Jabato]

Claro, veamos un ejemplo con una versión sencilla del juego, supongamos dos filas y dos columnas. Y en la primera tirada el jugador elige la primera columna en ambas filas (1, 1) y como respuesta recibe 1 acierto.

Debe elegir ahora una nueva combinación y las posibilidades son:

a) (1, 2)
b) (2, 1)
c) (2, 2)

Si la correcta fuera la primera, en la primera tirada hubiera tenido 1 acierto.
Si la correcta fuera la segunda, en la primera tirada hubiera tenido 1 acierto.
Si la correcta fuera la tercera, en la primera tirada hubiera tenido 0 aciertos.

Por lo tanto debe quedar descartada la opción c) ya que no es compatible con la respuesta que obtuvo en la primera tirada. Debe elegir por tanto alguna de las otras dos que si son compatibles con la respuesta que obtuvo en la primera tirada.

¿Quedó más claro ahora?

Saludos, Jabato.

[el_manco]

Hola

 Ya entiendo. Desde luego es el método más seguro... pero un ¿poco lento no?. Si por ejemplo tiene 4 aciertos de siete como en el ejemplo, lo único que descarta el método es cambiar todas. Por lo demás cambiar 6 cualesquiera sería compatible, pudiendo emperorar mucho la cosa.

 Yo planteo más la cosa desde un punto probabilístico porque no tienes tanto intentos como para diseñar un método que te lleve a la soluciñon segura. Pienso que incluso el óptimo es demasiado lento.

Saludos.

[Jabato]

No, no es lento, más bien al contrario, piensa que si se eligen adecuadamente las combinacione el número de posibilidades se reduce muy rapidamente, en cualquier caso calificar a este algoritmo como lento supondría la existencia de otros más rápidos, y ya opiné sobre tal cuestión.

El truco está en darse cuenta de que cuando el jugador recibe una respuesta hay combinaciones que se descartan, lo que no ocurre con el método del cálculo de probabilidades. Además este método resulta más sencillo de aplicar en una práctica efectiva del juego, ya que con algo de práctica no necesita de herramientas de cálculo, se puede hacer de cabeza, y lo sé porque hubo una época en que jugué a un juego similar, utilizando fichas de colores (con 5 fichas) y en la que las respuestas informaban del número de colores acertados así como del número de colores acertados en el sitio correcto, que es un juego similar a éste solo que algo más complejo. Y puedo asegurarte que el método funciona. Conduce "rapidamente" a la solución.

Piensa que el número de combinaciones con 5 fichas y 7 colores es , y en el ejemplo que nos puso makinavaja el número de opciones es de , ambos números muy grandes. Este método, en el caso de las 5 fichas de colores, conduce a la solución habitualmente en no más de 10 jugadas (dato deducido de la práctica que tengo de jugarlo) lo que nos daría una eficiencia enorme, ya que supone adivinar una combinación de entre posibilidades probando solo 10 veces. Decir que el método es lento resulta un poco atrevido.

¿Alguien se atreve a mejorar una eficiencia como esa, ?

Saludos, Jabato.

[ameram]

Creo que teneis razon los dos pero......

Jabato: lo que no entiendo y hay esta el problema es que como se que tengo que descartar la opcion "C". No existe ninguna opcion empirica que diga que tengo que descartar "C"


Esto no es del todo correcto:
Si la correcta fuera la primera, en la primera tirada hubiera tenido 1 acierto o 2 aciertos.
Si la correcta fuera la segunda, en la primera tirada hubiera tenido 1 acierto o 2 aciertos.
Si la correcta fuera la tercera, en la primera tirada hubiera tenido 0 aciertos.

Con lo que tenemos que en la primera tirada teniamos
 - 33% de acertar 2 aciertos.
 - 33% de acertar 1 aciertos.
 - 33% de acertar 0 aciertos.

En la segunda tirada, sabiendo que tenemos 1 acierto
 - 33% de acertar 2 aciertos.
 - 33% de acertar 1 aciertos.
 - 33% de acertar 0 aciertos.


Eso significa que aun sabiendo un resultado en la siguiente tirada se resetean las opciones y no se acumulan la probabilidades.

El problema de todo esto radica en que sabemos los aciertos pero no sabemos la situacion en la matriz de esos aciertos.

un saludo


 

[ameram]

Jabato. Podrias explicar un poco mas el juego del que hablas en el que partiendo de 5 fichas y una posicion inicial dabas pronto con la combinacion correcta. Con algun ejemplo.

Un saludo

[Jabato]

Creo que no captaste la cosa ameram:

Esto no es del todo correcto:
Si la correcta fuera la primera, en la primera tirada hubiera tenido 1 acierto o 2 aciertos.
Si la correcta fuera la segunda, en la primera tirada hubiera tenido 1 acierto o 2 aciertos.
Si la correcta fuera la tercera, en la primera tirada hubiera tenido 0 aciertos.

No es ciero lo que dices.

Si la combinación correcta, la que está oculta, fuera (1, 2), es decir la primera de las tres que le quedan por probar, cuando propuso la pregunta (1, 1) en la primera tirada la respuesta que hubiera recibido sería de 1 acierto.

Si la combinación correcta, la que está oculta, fuera (2, 1), es decir la segunda de las tres que le quedan por probar, cuando propuso la pregunta (1, 1) en la primera tirada la respuesta que hubiera recibido sería de 1 acierto.

Si la combinación correcta, la que está oculta, fuera (2, 2), es decir la tercera de las tres que le quedan por probar, cuando propuso la pregunta (1, 1) en la primera tirada la respuesta que hubiera recibido sería de 0 aciertos.

Como la respuesta que verdaderamente se produjo fué la de 1 acierto, entonces la tercera posibilidad debe descartarse. Mi razonamiento es correcto en este caso y no hay error. La tercera opción queda descartada por que la primera pregunta obtuvo como respuesta 1 solo acierto.

Pero fijaros que si al plantear la primera pregunta hubiera obtenido como respuesta 0 aciertos, entonces hubiera podido descartar las dos primeras opciones directamente, la opción a) y la b) acertando de lleno en la nueva propuesta al plantear como solución correcta la única que le queda, es decir la (2, 2). Por lo tanto está claro que cada respuesta aumenta la información del jugador y utilizar esa información, toda la que recibe, es la opción más eficaz, sin duda. No puede haber otra mejor.


Saludos, Jabato.

[Jabato]

Pues sí, no hay inconveniente. No recuerdo el nombre del juego, lo siento, pero es un juego comercial, que se hizo bastante popular aquí en España hace ya bastantes años. El juego era muy sencillo, y es para dos jugadores. Uno plantea una combinación de 5 fichas de colores (creo que eran 7 colores), combinación que queda oculta, y el otro debe tratar de adivinarla.

Cada vez que el jugador que está adivinando plantea una combinación, la coloca en un tablero adecuado a tal extremo, y a su lado el otro jugador coloca las respuestas formada por varias fichas blancas y negras, una blanca por cada acierto del color pero no de la posición de la ficha, y una negra cuando son correctos el color y la posición.

De forma tal que a medida que avanza el juego, en el tablero queda una muestra de cada pregunta y cada respuesta. El tablero venía preparado para un máximo de 12 preguntas, creo, con sus respuestas correspondientes, y no recuerdo jamás haber rebasado ese límite, y jugué bastantes veces siendo un chaval, utilizando el método que expliqué claro, es decir, buscando que cada nueva combinación propuesta fuera compatible con las respuestas a las anteriores combinaciones.

Saludos, Jabato.

[Jabato]

Veamos algún ejemplo de como se procedería con el modelo del juego que nos aportó makinavaja. Ese modelo es equivalente a adivinar un número de 7 dígitos expresado en base 3, cada dígito se corresponderá con una fila, y el valor que toma el dígito con la columna correspondiente (0, 1, 2)

Así pues supongamos que la combinación oculta sea 1201022 y elijamos una combinación al azar como primera tirada ya que no tenemos de momento información:

0000000    la respuesta en este caso será 2 aciertos

La siguiente propuesta deberá ser necesariamente un número que tenga dos ceros y solo dos ceros, quedan descartadas ya por lo tanto un montón de combinaciones. Probemos otra vez:

0011111    la respuesta en este caso será 1 acierto

y ahora el problema es elegir una combinación compatible con ambas respuestas. Creo que la idea está clara y quizás merecería la pena ver cuantas posibilidades han desaparecido con solo estas dos respuestas.

Emitamos una hipótesis, los dos ceros que debe contener el número están entre los 5 últimos dígitos y el acierto de la segunda tirada se corresponde con el tercer dígito, que es un 1, y veamos que pasa:

2210022   la respuesta en este caso será 4 aciertos

Vemos que el número de aciertos aumenta considerablemente aún a pesar de que la hipótesis emitida es falsa. El volumen de información recibida en solo tres jugadas es muy grande ya.


El desarrollo del juego hasta el final demostraría que el número de opciones se reduce de forma muy drástica y que resulta relativamente sencillo llegar a la solución con unas pocas tiradas más.

La dificultad estriba en encontrar cada vez la combinación compatible con las anteriores, pero con un poco de práctica no resulta difícil.

Saludos, Jabato.

[el_manco]

Hola

 Un ejemplo donde se ve que hay estrategias mucho más rápidas.

 Supongamos que tenemos filas con 2 opciones cada una.

 Supongamos que hacemos una combinación donde hemos acertado todas menos una. Si sabemos donde está el fallo problema resuelto.

 Con tu sistema se trataría de ir probando modificando nuestra elección inicial en una opción solo, hasta acertar. En el peor de los casos intentos.

 Sin embargo se pude acertar con seguridad en sólo n+1 pasos. La clave está en cambiar de nuestras elecciones. Si el número de aciertos disminuye en el fallo estaba en las que no cambiamos sino en las que hemos cambiado. Ahora reiteramos el critero para los casillas donde hemos detectado el fallo. En n+1 pasos: solución encontrada. Fíajte que por enmedio probamos con soluciones deliberadamente peores que la incial pero que aportan mucha más información.

 Por otro lado conozco el juego a que te referías: el Master Mind. . Yo también he jugado mucho.  . Pero allí una estrategía muy utilizada era lanzar jugadas que deliberadamente eran peores que las anteriores para obtner información. Por ejemplo usar sólo uno o dos colores para descartarlos, o cosas así. O utilizar colores que ya sabemos que no están combinados con otros dudosos para obtener información útil sobre estos.

 El Master Mind.... !!!estaba chulo!!!

Saludos.

[Jabato]

Si, se llamaba Master Mind, sí, pasé horas jugando y tratando de establecer estrategias que condujeran a la solución de la manera más rápida.

Me resulta difícl creer que usando fichas de dos colores cada una se pueda llegar a una solución en solo n+1 tiradas, es decir, que con 8 fichas de dos posibles colores cada una se pueda llegar a la solución con cuatro tiradas solamente. Creo que eso necesita una demostración ó una verificación. Aunque la cosa se complicaría un poco más si aumentamos el número de colores, aunque solo sea a tres.

¿Como aplicarías tu criterio con tres ó más colores?

Saludos, Jabato.

[ameram]

Pues teneis razon los dos. Son muy buenos razonamientos.

Me permitis una variante de este intrigante juego.

tenemos una matriz .  (0,1,2)

-Sabemos que la combinacion (00000000000000) = 7 aciertos.
-Sabemos que la combinacion oculta contiene 2 unos pero no sabemos sus posiciones.
-Sabemos que la combinacion oculta contiene 5 doses pero no sabemos sus posiciones.

Se podria subir los aciertos sin saber la combinacion y con una sola tirada?

un saludo

[Jabato]

No es posible que pueda darse tal combinación, puesto que la solución debería tener 7 ceros, 2 unos y 5 doses, ya me dirás como metes 14 dígitos en una matriz de 3x4 = 12 posiciones.

De todas formas creo que la respuesta a tu pregunta debe ser no, porque aunque conozcas todos los dígitos que forman la solución y sin saber la posición de ninguno, siempre podrías elegir una nueva combinación que no tuviera ningún dígito en el lugar correcto, lo que te lleva a una respuesta de 0 aciertos, y no tienes datos suficientes para evitar elegir precisamente esa. En este caso no se puede garantizar que el número de aciertos mejore.

Saludos, Jabato.

[ameram]

hola.
era 3^14 que lo queria poner con formula y no me ha salido.
Creo que tienes razon.
los parametros que doy son insuficientes pero os queria preguntar por si acaso se me escapaba algo a mi.
En una sola tirarda es imposible asegurar mas aciertos con esos datos.

saludo

[el_manco]

Hola

Me resulta difícil creer que usando fichas de dos colores cada una se pueda llegar a una solución en solo n+1 tiradas, es decir, que con 8 fichas de dos posibles colores cada una se pueda llegar a la solución con cuatro tiradas solamente.

 ¿Has seguido el ejemplo concreto que puse? Supongamos que hay 8 casillas con dos posiblidades. La combinación correcta es 0000100.

  Supongamos que comenzamos poniendo 00000000.

  - Tenemos 7 aciertos. Nos queda conocer donde está el 1.

  - Entonces ponemos la combinación 11110000.

  -- Si nos dicen que ahora hay 3 aciertos, el uno está en las cuatro últimas posiciones, sin os dicen que hay 4 el uno está en las cuatro primeras.

  -- En nuestro ejemplo nos dirán que hay 3 aciertos. Seguimos poniendo 11111100. Si hay dos aciertos el 1 está en la 5 o 6 sino en la 7 ó 8.

  -- Nos dirán en este caso que hay 2 aciertos luego el 1 está en la 5 ó 6. Finalmente con un intento más distingujimos entre ambas y conocemos la solución.

 En definitiva en cada caso dividimos por 2 las posibilidades para encontrar nuestro 1 perdido.

 No pretendo presentar esto como un método que funcione siempre, porque obviamente es una caso muy particular. Pero es sólo para hacer ver, que a veces se obtiene más información si uno emperora deliberadamente los intentos previos. No tengo claro como se podría generalizar, aunque la idea podría estar en ir ramificando el problema.

Saludos.