Build a wall with three types of bricks. What is the max length of wall less than 1000 cm you won't be able to lay?

Question

You need to build a wall of length no longer than $1000$ cm. You can use bricks of three sizes: $23$ cm, $27$ cm or $36$ cm, and you are not allowed to cut bricks.

What is the maximum length which you won't be able to lay?

For example, you can lay a brick wall of length 469 cm, because $11\cdot 23 + 6 \cdot 36 = 469$.

I was able to find that the answer is 229 with a simple dynamic programming algorithm. That does solve the problem, but I'd love to know if there's a more "mathematical" way to approach it.

I tried playing with some modulo arithmetic on the equation $23a+27b+36c=n$, but that didn't get me too far.

Any kind of help would be appreciated.

Answer 1

Apart from having an upper limit of 1000, I believe this is basically what is known as the Frobenius, Postage Stamp or Chicken McNugget problem. According to https://brilliant.org/wiki/postage-stamp-problem-chicken-mcnugget-theorem/ :

The Frobenius problem (or Chicken McNugget problem) is, given coins worth $a_1, a_2, \ldots, a_n$ units, to find the largest $N$ such that no combination of the coins is worth exactly $N$ units. This value $N = g\left( a_1, a_2, \ldots, a_n \right)$ is called the Frobenius number of the $a_i$.

The problem comes up in many real-world contexts, and despite being quite elementary, its general solution is not known. The solution is completely understood for $n = 2$, but even for $n = 3$, there is no general closed-form formula for the Frobenius number.

Thus, apart from the result being no larger than your maximum allowed, this shows that for even your example with $3$ variables, there is no general solution. I don't know of any way to handle restricting the result to within a specified maximum as well, with this likely making the problem even more difficult to solve, but perhaps somebody else can answer this or suggest something.