Construye un muro con tres tipos de ladrillos. Cuál es la longitud máxima de muro inferior a 1000 cm que no podrás colocar?

Question

Tienes que construir un muro de longitud no superior a $1000$ cm. Se pueden utilizar ladrillos de tres tamaños: $23$ cm, $27$ cm o $36$ cm, y no se permite cortar ladrillos.

¿Cuál es la longitud máxima que no podrá colocar?

Por ejemplo, se puede colocar una pared de ladrillos de 469 cm de longitud, porque $11\cdot 23 + 6 \cdot 36 = 469$ .

He podido comprobar que la respuesta es 229 con un sencillo algoritmo de programación dinámica. Eso resuelve el problema, pero me encantaría saber si hay una forma más "matemática" de abordarlo.

Intenté jugar con algo de aritmética de módulos en la ecuación $23a+27b+36c=n$ pero eso no me llevó muy lejos.

Se agradecería cualquier tipo de ayuda.

Answer 1

Aparte de tener un límite superior de 1000, creo que esto es básicamente lo que se conoce como el problema de Frobenius, del sello de correos o del McNugget de pollo. Según https://brilliant.org/wiki/postage-stamp-problem-chicken-mcnugget-theorem/ :

El Problema de Frobenius (o el problema del Chicken McNugget) es, dadas las monedas que valen $a_1, a_2, \ldots, a_n$ unidades, para encontrar la mayor $N$ tal que ninguna combinación de las monedas vale exactamente $N$ unidades. Este valor $N = g\left( a_1, a_2, \ldots, a_n \right)$ se llama Número de Frobenius de la $a_i$ .

El problema se plantea en muchos contextos del mundo real y, a pesar de ser bastante elemental, no se conoce su solución general. La solución se entiende completamente para $n = 2$ pero incluso para $n = 3$ no existe una fórmula general de forma cerrada para el número de Frobenius.

Así, aparte de que el resultado no es mayor que su máximo permitido, esto demuestra que incluso para su ejemplo con $3$ variables, no existe una solución general. No conozco ninguna forma de restringir el resultado dentro de un máximo especificado, lo que probablemente dificulte aún más la solución del problema, pero tal vez alguien más pueda responder a esto o sugerir algo.