El rey de un país oriental tiene un gobernador en cada una de sus provincias que anualmente llevan su tributo, consiste en un saco con un número indeterminado de monedas de oro de p gramos. Varios de los gobernadores hace trampa: todas sus monedas pesan un gramo de menos sin variar forma y tamaño (tienen una burbuja de aire en su interior). Con una balanza de dos platillos y un juego de pesas apto para pesar cualquier cantidad el rey tiene que averiguar en ¡una única pesada! cual es el gobernador que pretende engañarle. No es necesario saber cuántos gobernadores hay ni cuál es el tributo que paga cada uno.
La solución está tras el enlace.
SOLUCIÓN: La respuesta es colocar los sacos de cada gobernador en fila y tomar 2^0 monedas del primero, 2^1 del segundo, 2^2 del tercero,..., 2^(k-1),..., y así sucesivamente hasta terminar los sacos.
La cantidad que deben pesar es
m=p·(1+2+2^2+...+2^s)=p·(2^(s+1)-1)
donde s representa el número de sacos (provincias). Se pesan todas las monedas y luego la diferencia d entre el peso m que debería dar si todas las monedas pesasen igual pasamos ese número a sistema binario y en aquellas posiciones en las que haya un 0, habrá un gobernador mentiroso.
No hay comentarios:
Publicar un comentario