Alice, Bob y su triunfo de 1956

Question

Alice desafíos Bob con un rompecabezas y Bob acepta incluso antes de que Alice le dijo específicamente de qué se trata :)

Él debe secretamente escribir en una lista (lista a), de 20 de los números racionales positivos, no son necesariamente diferentes de unos a otros y poner la lista en un sobre sellado. Luego, Bob debe dar a Alice una lista (lista B) de números diferentes, cada uno de los cuales puede ser uno de los números en su lista a, o la suma de más de uno de los números en la lista A., a Continuación, Alice debe tratar de encontrar los números de la lista A. Si ella se las arregla para encontrar 2 o más conjuntos de 20 números (a partir de los números de la lista B), por el cual ella puede adivinar los números de la lista a, entonces Bob debe donar su inestimable 1956 Triumph TR3. Si, sin embargo, por los números en la lista B, sólo hay una manera de adivinar el 20 números en la lista a, entonces Bob pagará Alice un dólar para cada uno de los números en la lista B. ¿Cuál es el número mínimo que Bob debe pagar a Alice (para salvar su Triunfo)?

Esto fue dado a mí como un reto de un amigo. Estoy obsesionada con las matemáticas y la combinatoria, pero, por desgracia, con este no puedo ni siquiera pensar por dónde empezar! (y ni siquiera estoy seguro de qué categoría a asignar a!! Elegí "combinatoria" sólo por la intuición!!)

Answer 1

(esencialmente, se trata de la solución de @Vepir comentario, ligeramente modificado para hacer la prueba más simple)

Si $x \in B$, a continuación, algunos de número de $[\frac{x}{20}, x]$ es de $A$ (de la que no tenemos $x$ mediante el uso de números de mayor a $x$, o por el uso en la mayoría de las $20$ números más pequeños, a continuación, $\frac{x}{20}$). Así que la idea es el uso de $20$ números de $B$ hacer $20$ no superposición de los intervalos para los elementos de $x$ (asegurando así que cada intervalo contiene exactamente un elemento de $A$) y, a continuación, añadir un elemento más para garantizar que todos los números son de la derecha de la frontera de los intervalos correspondientes.

Para hacerlo, vamos a $A = \{1, 10^2, 10^4, \ldots, 10^{38})$ e $B = A \cup \{1010\ldots1\}$. Deje $A'$ ser cualquier lista s.t. todos los números de $B$ pueden ser sumas de ella. Del argumento anterior, $A'$ contiene un número de $[\frac{1}{20}; 1]$, de $[5, 100]$, de $[500, 10000]$, etc. Como este son los intervalos no solapados, contiene exactamente un número de cada intervalo. Si contiene cualquier número que no es un derecho frontera de algunos de estos intervalos, entonces la suma de incluso todos los elementos de $A'$ es de menos de $1 + 100 + \ldots + 10^{38}$ - lo $B$ contiene el número que no es la suma de los elementos de $A'$. Por lo $A$ contiene sólo el derecho de las fronteras de esta intervalos, por lo $A' = A$.