Torneo de las Ciudades - Octubre 2019 - NJ P6

[Joacoini]

Pedro tiene varios billetes de $100$ pesos y no tiene más que ese dinero. Él comienza a comprar libros; cada libro cuesta una cantidad entera de pesos, y él recibe el vuelto en monedas de un peso. Siempre que Pedro compra un libro caro, de $100$ pesos o más, solo usa para pagar billetes de $100$ pesos, y además utiliza la menor cantidad posible de estos billetes. Siempre que compra un libro barato (de menos de $100$ pesos), él usa sus monedas, si tiene suficientes, y si no paga, con $100$ y recibe su vuelto. Cuando ya no tiene más billetes de $100$ pesos, Pedro ha gastado exactamente la mitad de su dinero. ¿Es posible que haya gastado $5000$ o más?

[Fran5]

Está medio desordenado... creo que entendí mal el problema porque me pareció hiper facil para ser un P6

Spoiler: mostrar

Escribamos $g_i =100b_i - v_i$ el valor de un libro grande, con $b_i$ la cantidad de billetes de $100$ que gastó y $v_i$ el vuelto que obtuvo.
También sea $p_i$ el valor de un libro pequeño. Digamos que compro $k$ grandes y $l$ pequeños. Supongamos además que no existen libros grandes de $100$ pesos, pues eso es equivalente a eliminar uno o más billetes de $100$, de modo que $b_i \geq 2$ y $v_i < 100$. Para ello, llamémoslos medianos, y digamos que compró $m$ libros medianos.

Digamos que gastó $S$ pesos en total. Como no tiene billetes de $100$, tiene $S$ monedas de $1$ peso.

Como sólo obtiene monedas al comprar libros grande, y encima las pierde cuando compra libros chiquitos, tenemos que $$S = \sum_{i=1}^{k} v_i - \sum_{j=1}^l p_j = \text{gastado} = \sum_{i=1}^k (100b_i - v_i) + \sum_{j=1}^l p_j + 100m$$
Acomodando todo y pasando lo que resta al otro lado, tenemos $$\sum_{i=1}^{k} 2v_i = \sum_{i=1}^k 100b_i + 2\sum_{j=1}^l p_j +100m = 100Q + 2\sum_{j=1}^l p_j$$ Recordando que $v_i \leq 99$ y que $b_i \geq 2$, $m \geq 0$, tenemos que $$198k \geq \sum_{i=1}^{k} 2v_i = \sum_{i=1}^k 100b_i + 2\sum_{j=1}^l p_j +100m \geq 200k + 2\sum_{j=1}^l p_j \geq 200k.$$ ABSURDO!.

Luego es imposible que pedro haya gastado $5000$ o más. Más aún, es imposible que haya gastado la mitad de su dinero sólo con billetes de $100$