Tienda Chocolates puzzle

Question

Estaba tratando de resolver un rompecabezas, pero no fue capaz de encontrar ninguna solución si alguien sabe las soluciones por favor, compartir.

"Tienes una tienda de bombones. Quiere dar el número exacto de bombones (digamos para pedidos de hasta 1.000 bombones) a los clientes sin contarlos en el momento de la entrega. Puede rellenar previamente los bombones en bolsas contándolos por adelantado y dar las bolsas adecuadas (una o muchas) para cumplir el pedido. ¿Cuál es el número mínimo de bolsas que necesitará para satisfacer su primer pedido? (Recuerde que no sabe cuál es el pedido por adelantado)".

Answer 1

La respuesta es utilizar bolsas de tamaño $1, 2, 4, 8, 16, 32, 64, 128, 256, 512$ . Por representación binaria, podemos satisfacer cualquier orden con estas bolsas (hasta $1023$ no sólo hasta $1000$ ). Esto es $10$ bolsas.

Supongamos que sólo tuviéramos $9$ (o menos) bolsas. Entonces el número de maneras en que podríamos repartir algún subconjunto de estas bolsas sería $2^9$ (o menos). Pero hay $1000$ distintos pedidos posibles que necesitamos poder satisfacer, y sólo podemos hacer como máximo $2^9 = 512$ diferentes pedidos utilizando un subconjunto de las bolsas que preparamos. Así, $10$ bolsas es el número mínimo posible.