Rincón Matemático

Matemática => Matemática Aplicada => Teoría de Juegos => Mensaje iniciado por: Carlei en 20 Agosto, 2020, 07:48 pm

Título: Detectar barra falsa con menos pesadas
Publicado por: Carlei en 20 Agosto, 2020, 07:48 pm
hola, queria saber si me pueden ayudar con esto
Se tienen barritas de metal todas de apariencia igual, pero hay una falsa, que no pesa lo mismo de las demás.
Si tenemos una balanza y [texx] n [/texx] barritas, cuantas veces debemos ocuparla para encontrar la falsa.
Saludos
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: manooooh en 20 Agosto, 2020, 10:58 pm
Hola

hola, queria saber si me pueden ayudar con esto
Se tienen barritas de metal todas de apariencia igual, pero hay una falsa, que no pesa lo mismo de las demás.
Si tenemos una balanza y [texx] n [/texx] barritas, cuantas veces debemos ocuparla para encontrar la falsa.
Saludos

¿Qué has intentado?

El enunciado no se explicaría si no se usa el cálculo de probabilidades.

Puedes empezar con algún caso particular y ver si puedes generalizarlo.

Por ejemplo, con \( n=5 \) barritas de metal, habrá \( n-1=4 \) "verdaderas" y \( 1 \) falsa. La probabilidad de pesar en una balanza una barrita y que sea verdadera es: \( P(V)=4/5 \). Por ende la probabilidad para que salga falsa es \( P(F)=1-P(V)=1-4/5=1/5 \).

Generalizando, la probabilidad de que salga la falsa es \( P(F)=1-P(V)=1-(n-1)/n=1/n \).

Saludos
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: martiniano en 20 Agosto, 2020, 11:48 pm
Hola.

hola, queria saber si me pueden ayudar con esto
Se tienen barritas de metal todas de apariencia igual, pero hay una falsa, que no pesa lo mismo de las demás.
Si tenemos una balanza y [texx] n [/texx] barritas, cuantas veces debemos ocuparla para encontrar la falsa.

Recuerdo que el caso particular de este problema con \( n=12 \) me lo propusieron a mí en la época en que le empezaba a coger el gustillo a las matemáticas. La solución para este caso es 3 y tengo la respuesta en un manuscrito, por si te interesa. Pero ni idea de cómo generalizarla.

Un saludo.

Pd. Manooooh, es que el enunciado debería decir que se trata de una balanza de dos brazos.
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: martiniano en 21 Agosto, 2020, 04:50 pm
Hola.

Wikipedia dice esto (https://es.wikipedia.org/wiki/Problema_de_las_doce_monedas).

Un saludo.
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: Luis Fuentes en 23 Agosto, 2020, 12:52 pm
Hola

 Te puede interesar el problema parecido (ojo, pero no igual):

https://foro.rinconmatematico.com/index.php?topic=2368.msg9381#msg9381

 También la versión inglesa del enlace que puso martiniano, que en mi opinión está un poco mejor que la versión española:

https://en.wikipedia.org/wiki/Balance_puzzle

Saludos.
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: martiniano en 25 Agosto, 2020, 09:15 am
Hola.

También la versión inglesa del enlace que puso martiniano, que en mi opinión está un poco mejor que la versión española:

https://en.wikipedia.org/wiki/Balance_puzzle

Pues sí, la verdad es que tiene mejor pinta. Le he estado dando vueltas estos días a la parte en la que el enlace en castellano demuestra que el algoritmo que describe encuentra la moneda falsa en el menor número de pesadas posible. Sin embargo, me da la impresión que da por triviales cosas que no lo son tanto...

Parece que, efectivamente, en el enlace en inglés se razona todo con más detalle.

No estoy acostumbrado a hacer búsquedas en inglés, pero la verdad es que me estoy dando cuenta de que suele ser recomendable hacerlo.

Un saludo y gracias.
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: CarlosMD en 10 Julio, 2022, 10:31 pm
(si lo que quieres es aislarla y descubrir ademas si es mas pesada o mas liviana) si las monedas son 3 y una es falsa tomas dos: si da igual la falsa es la que quedo afuera (necesitas una segunda pesada para saber si es mas liviana o mas pesada a las verdaderas) si da diferente ahi necesitaras una segunda pesada la falsa esta en uno de los dos platos pero no sabes si es falsa y pesa menos o si es falsa y pesa mas para ello y sabiendo que la que te quedo afuera es verdadera intercambias esa con una de las dos: si te da lo mismo que en la primera pesada es por que intercambiaste dos monedas verdaderas y la que quedo en el otro plato esa es la falsa ( y de acuerdo a lo que te dio la primera pesada determinas si es falsa pesada o falsa y mas liviana) si la balanza se equilibra intercambiaste la verdadera que estaba fuera con la falsa y listo eso para 3 monedas tenes DOS PESADAS , si no sabes si la falsa es mas liviana o mas pesada en la segunda pesada siempre formaras 3 grupos de monedas eso es comun a cualquier numero de monedas si n=6 tomas 2 y 2 y las otras dos afuera: si da igual una de las dos que quedaron afuera es la falsa en la segunda pesada haces una de las dos que quedo fuera y una de las 4 verdaderas de la 1º pesada si da diferente es por que intercambiaste 1 verdadera y una falsa y si da igual intercambiaste dos verdaderas ; la falsa es la otra que sobro afuera necesitaras una tercera pesada para saber si es falsa liviana o falsa pesada YA SON 3 PESADAS las necesarias. Si n=12 aqui es mas complicado haces 3 grupos de 4 monedas ; o da igual o da diferente si da igual la 1º es una de 4 que quedaron afuera en 2º tomas 3 de las 8 verdaderas de la 1º con 3 de 4 que quedaron fuera  entonces o da igual o da diferente si da igual la que sobro afuera es la falsa y necesitas una tercer pesada para saber si es falsa liviana o falsa pesada si da diferente es una de las tres que estan en el otro plato donde pusistes las 3 verdaderas y de acuerdo para donde este desequilibrada la balanza te das cuenta si es falsa y liviana y falsa y pesada y necesitas una 3º pesada para determinar cual es de las 3 donde separas 2 y la otra la dejas afuera o te da igual o diferente si da diferente y es una de las dos que tienes en la 3º pesada y con la informacion de la 2º pesada ya sabias que la falsa tenia q ser o mas liviana o mas pesada ya lo tienes usaste 3 PESADAS. Hasta aqui tengo:

n=3                -------->           2 P
n=6                -------->           3 P
n=12              -------->           3 P

Habria que probar con mas casos por ejemplo n=18 y n= 27 y n=36 y ver si se puede generalizar una formula para cualquier numero de monedas
Siguiendo el mismo razonamiento para n=18 son 3 pesadas.
Para n=27 son 4 pesadas o sea

n=3               --------->           2P
n=6               --------->           3P
n=12             --------->           3P
n=18             --------->           3P
n=27             --------->           4P

No estoy seguro de si esto esta bien por ahora lo dejare.
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: Richard R Richard en 10 Julio, 2022, 11:56 pm
El procedimiento es el siguiente para cualquier n se divide en tres grupos las piezas  hay tres casos posibles , tres grupos de igual cantidad de piezas, y dos grupos de igual cantidad y el tercero uno con una mas o  bien con una  de menos.


Se pesan los grupos de igual cantidad, si hay igualdad , la mala esta en el tercer grupo...
Si no la hay, el tercer grupo tiene solo buenas, (para saber si pesa mas o menos, se intercambia una del tercer grupo por cualquiera del primero o del segundo y en función del resultado de la pesadas previa y la intercambiada, se puede saber si pesa mas o de menos) es una análisis lógico de casos posibles, es decir averiguar si es mas o menos pesada que el resto lleva una única pesada extra.
Spoiler
sean a,b y c los grupos


si a>b y se intercambia una de a por una de c si la pesada resulta a'>b la pieza esta en b y pesa menos
si a>b y se intercambia una de a por una de c si la pesada resulta a'=b la pieza extraida de a es la defectuosa y pesa mas

si a>b y se intercambia una de b por una de c si la pesada resulta a>b' la pieza esta en a y pesa mas
si a>b y se intercambia una de b por una de c si la pesada resulta a=b' la pieza extraida de b es la defectuosa y pesa menos



si a<b y se intercambia una de a por una de c si la pesada resulta a'>b la pieza esta en b y pesa mas
si a<b y se intercambia una de a por una de c si la pesada resulta a'=b la pieza extraida de a es la defectuosa y pesa menos

si a<b y se intercambia una de b por una de c si la pesada resulta a>b' la pieza esta en a y pesa menos
si a<b y se intercambia una de b por una de c si la pesada resulta a=b' la pieza extraída de b es la defectuosa y pesa mas


si a=b=c se compara c con a y si  la pesada resulta a>c la pieza esta en c y pesa menos
si a=b=c se compara c con a y si  la pesada resulta a<c la pieza esta en c y pesa mas

si a=b se iguala el numero de piezas de c en un platillo con piezas de a y b ( se pone una de mas o se quita una, todas son buenas) , se compara con c y si  la pesada resulta (ab)'>c la pieza esta en c y pesa menos
si a=b se iguala el numero de piezas de c en un platillo con piezas de a y b ( se pone una de mas o se quita una, todas son buenas) , se compara con c y si la pesada resulta (ab)'<c la pieza esta en c y pesa mas


[cerrar]

se reitera el procedimiento con el grupo donde  esta la pieza defectuosa, pusto que ya hemos descubierto si pesa mas o menos y en que grupo está.


El caso mas desfavorable en el que si aumenta una unidad n se necesita si o si un número de pesadas  adicional, esto sucede cuanto en todas nuestras particiones en tres grupos la pieza se ubique en el grupo c y  siempre con una piezas extra respecto de a y b ,es decir cuando sucede \( n=x^3+1 \) siendo \( x \) el número de pesadas necesarias  al que se le agrega una mas para también dilucidar si pesa mas o de menos,


Por otro lado el numero mínimo de pesadas para identificarla  con seguridad es siempre 2 teniendo la máxima suerte de intercambiarla en la segunda pesada dejándola separada del grupo la que se extrae de la primer pesada.


En definitiva el numero de pesadas máximo necesario para dilucidar cual pieza se trata y si pesa mas o menos \( x=entero(\sqrt[3]{n-1})+2 \)


ej  para 28 si siempre esta en c    tres grupos 9,9,10 pesada 1 nos quedan 10
pesada 2 determinamos si es mas o menos pesada pero no la identificamos
reiteramos con 3,3,4 en pesada 3 nos quedan 4
nuevamente en 1,1,2 en pesada 4 nos quedan 2
y con la pesada 5 de 1y1 sabremos cual es .


Saludos
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: Luis Fuentes en 11 Julio, 2022, 09:54 am
Hola

En definitiva el numero de pesadas máximo necesario para dilucidar cual pieza se trata y si pesa mas o menos \( x=entero(\sqrt[3]{n-1})+2 \)

La fórmula NO es correcta. Ahora no tengo tiempo de detallar al asunto. Pero puedes echar un vistazo a los enlaces que se propusieron previamente en el hilo.

Saludos.
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: Richard R Richard en 11 Julio, 2022, 12:11 pm
Bueno , cuando tengas tiempo puedes postear un contraejemplo dónde mi fórmula falle, no es por lanzarte un desafío , sino que wikipedia no propone el límite como lo hago yo ,pero sin embargo el número de monedas máximo es el mismo para cada pesada \( n=3^x \), con una moneda más, ya tienes que agregar una nueva pesada hasta el siguiente número de monedas que sea un cubo perfecto. Además no tienen en cuenta la pesada adicional para dilucidar si es o no más liviana o pesada, y yo sí.


Saludos
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: Richard R Richard en 12 Julio, 2022, 01:10 am




Creo que cumple con las espectativas,
\( \begin{pmatrix}{n\,monedas}&{Pesadas\, x=[\sqrt[3]{n-1}]+2}\\
{3}&{2}\\
{4}&{3}\\
\vdots &\vdots\\
{9}&{3}\\
{10}&{4}\\
\vdots &\vdots\\
{27}&{4}\\
{28}&{5}\\
\vdots &\vdots\\
{81}&{5}\\
{82}&{6}\\
\vdots &\vdots\\
{243}&{6}\\
{244}&{7}\\
{...}&{...}\\
\end{pmatrix} \)

Título: Re: Detectar barra falsa con menos pesadas
Publicado por: Luis Fuentes en 12 Julio, 2022, 09:11 am
Hola

 Por ejemplo según tu fórmula para \( 12 \) monedas dices que el número óptimo de pesadas es \( 4 \), pero en realidad lo puedes hacer en \( 3 \).

  1) Divide en tres grupos de \( 4 \) la monedas.
 
  2) PESADA UNO. Pesa dos de ellos.

     2.1) Si pesan lo mismo, de las \( 4 \) monedas restantes (el tercer grupo) compramos dos de ellas en una
   plato de la balanza frente a otra y una de las ocho iniciales (que sabemos normales) en el segundo plato, dejando
   una cuarta moneda separada. PESADA DOS.

        2.1.1) Si pesan lo mismo, la moneda falsa es la que dejamos al margen y la comparamos con una normal para
      ver si es más o menos pesada. PESADA TRES. FIN.

        2.1.2) Si pesa más (respectivamente menos) el plato donde están las dos monedas del tercer grupo de cuatro,
      comparamos una con la otra (PESADA TRES):
              2.1.2.1) Si pesan igual, la falsa era la moneda que habíamos puesto en el paso 2.1 en el otro plato con la
            moneda normal y además es menos (respectivamente más) pesada que las normales. FIN. 
              2.1.2.2) Si pesan más (respectivamente menos) una que otra la falsa es la que pesa más (respectivamente
            menos) FIN.

     2.2) Si pesan distinto, tenemos un grupo de cuatro que pesó más y otras cuatro que pesaron menos. Hacemos una PESADA DOS, poniendo en cada plato de la balanza dos monedas del grupo ligero y una del pesado; dejando fuera dos del pesado.

        2.2.1) Si pesan lo mismo, la moneda falsa es la una de las dos que dejamos al margen; dado que dejamos las más pesadas. Es la que más pesa de ambas y eso se comprueba en una PESADA TRES. FIN.

        2.2.2) Si pesan distinto, la moneda falsa es o bien una de las monedas ligeras del plato que pesó menos o bien la pesada del plato que pesó más. Tomamos la dos ligeras y las comparamos. PESADA TRES:
              2.2.2.1) Si pesan igual, la falsa era la moneda pesada del plato que pesó más. FIN. 
              2.2.2.2) Si pesan distinto, la falsa es la que menos pesa de las dos. FIN.

 En general se puede demostrar que:

- Si sólo queremos encontrar la moneda falsa pero sin saber si es más o menos pesada, el número necesario de pesadas para \( n \) monedas es \( \lceil log_3(2n+1)\rceil  \).

- Si queremos encontrar la moneda falsa pero además saber si es más o menos pesada, el número necesario de pesadas para \( n \) monedas es \( \lceil log_3(2n+3) \rceil \).
 
 Por ejemplo, para \( 13 \) monedas se puede en tres pesadas encontrar la falsa (prácticamente como hicimos antes dejando una moneda al margen; si el método que usamos no encuentra la falsa es que era la dejada al margen); pero no se puede saber si la falsa es más o menos pesada que las normales.

Saludos.

P.D. Puedes leer aquí sobre esto:

https://aprende.olimpiada-informatica.org/algoritmia-introduccion-1-eficiencia 
Título: Re: Detectar barra falsa con menos pesadas
Publicado por: Richard R Richard en 13 Julio, 2022, 02:04 am
Pues la formula no fallaba , lo que fallaba era mi lógica deductiva. Gracias. Saludos.