100 tarjetas en blanco, minimizar el EV

Question

Te doy un centenar de tarjetas en blanco, y usted puede escribir un único entero positivo en cada tarjeta. Miro las cartas cuando haya terminado, entonces yo baraja el mazo. Supongo que la carta superior de la baraja, y si estoy en lo cierto, puedo hacer que el dólar que está escrito en la tarjeta. ¿Qué números hay que escribir en las tarjetas para minimizar la rentabilidad esperada de la mina?

Intento: por Lo que este problema me parece bastante difícil. Si pongo un 1 en la tarjeta, entonces el valor Esperado es de 1. si pongo dos 2s, y el resto 1-99, el valor Esperado es 99/100.

Siento que el mínimo ocurre cuando i es un entero en al menos una de las tarjetas, donde $ip_{i} = jp_{j}$ para cada i,j es casi satisfecho, de lo contrario podrían minimizar aún más. De modo que p1=2p2 = 3p3 =...=npn

Así que si usted utiliza sólo 1 y 2, entonces podría conseguir EV cerca de 2/3.

Así que para resolver este siento que me necesitan trabajar con el mínimo de G tales que,

p1 ≈ p2 ≈ p3 ≈ .. ≈ pn ≈ G

donde no se puede reorganizar las cartas, para hacer una aproximación más cercana.

Answer 1

Para resolver esta cuestión, se trata de hallar el número de $1$s debemos utilizar, definido como:$x$. A continuación, podemos asignar $\lfloor\frac{x}{2}\rfloor$ $2$s, $\lfloor\frac{x}{3}\rfloor$ $3$s y así sucesivamente. Ahora debemos minimizar $x$, dado que la suma total debe ser mayor que o igual a $100$:

$$min(x): \sum_{i=1}^{100}\lfloor\frac{x}{i}\rfloor \ge 100$$

El menor entero $x$ para que esto sea cierto es $28$, resultando en una suma total de $101$. El valor esperado es igual a $0.28$ cuando la persona que adivine $1$, e $0.28$ o menor para cada número.

Answer 2

Sí, usted tiene la idea correcta: Con $p_i$ la probabilidad de sacar una tarjeta con número de $i$, el valor esperado de la elección de $i$$p_i \cdot i$, y desea que esta aproximadamente igual a la de cualquier $i$. O, para ser más exactos: usted quiere encontrar un valor de $E$, de modo que $p_i \cdot i$ es siempre menor o igual a $E$ todos los $i$.

Solo por jugar de todo un poco, he encontrado que se puede conseguir siempre $p_i \cdot i$ en o por debajo de $0.28$:

$28$ tarjetas con el número de $1$

$14$ tarjetas con el número de $2$

$9$ tarjetas con el número de $3$

$7$ tarjetas con número $4$

$5$ tarjetas con número $5$

$4$ tarjetas de cada uno de los números de $6$ $7$

$3$ tarjetas de cada uno de los números de $8$ $9$

$2$ tarjetas de cada uno de los números de $10$ a través de $14$

$1$ tarjetas de cada uno de los números de $15$ a través de $27$

Para un total de $28+14+9+7+5+2\cdot 4+2\cdot 3 + 5 \cdot 2 + 13=100$ tarjetas, y lo mejor que la persona puede hacer aquí es conseguir un valor esperado de $0.28$ mediante la selección de cualquiera de los números $1$,$2$,$4$,$7$, o $14$.

También, es claro que este es el mejor que usted puede hacer: hacer mejor, usted tendría que obtener $27$ tarjetas de $1$, $13$ con $2$ ... y ya que iba a necesitar una tarjeta con $29$. Así que, lo mejor que puedes hacer es escribir los números como se señala anteriormente.