Goal: Maximize the sum of all the numbers in the box.
Rules:
I. Every square has to contain a single number.
II. Only the numbers from 1 through to 4 can be used.
III.
- 1 can be placed anywhere.
- 2 must be placed next to 1.
- 3 must be placed next to 1 AND 2.
- 4 must be placed next to 1 AND 2 AND 3.
"Next to" in this context means horizontally OR vertically. Not diagonally.
IV. The box must be a perfect square box.
Example of max sum in this 3x3 box. Max sum is 20
Question One:
I want to find a formula that when given the dimensions, gives the maximum sum as output.
example: f(3)=/unknown/=20
Question Two:
How would one arrange the numbers in such a way to achieve the maximal sum, without running it through a computer simulation
Where I am completely stuck:
- How to express mathematically that a number can share with another number. For example, in the 3x3 box, both 4's share the same 3. Thus reducing the need to add another 3 to create a 4.
My approach thus far: For the 3x3 box
4x+3y+2z+1w= Max.
9<Max<36 (The lowest if the squares are filled with 1's, highest if it is filled with 4's)
From the rules you quickly realize you cannot have 4's without at least one of the other numbers. The higher inequality is thus reduced. For the lower inequality, you can easily see that 1's can fill the middle vertical row, and thus allowing for 2's on the sides.
The new interval is thus 15<Max<30
Constraints:
x+y+z+w=9 (The total amount of squares)
I cannot compute $f(n)$ exactly yet, but I can prove that $$ \lim_{n\to\infty} f(n)/n^2=14/5 $$ Here's why. Every square labeled $2,3$ or $4$ needs to be next to a square labeled $1$. Furthermore, each $1$ can only satisfy four squares numbered $2,3$ or $4$. Therefore, at least one out of five squares must be labeled $1$.
Similarly, of the squares labeled $2,3,4$, at least $1/4$ of them must be labeled $2$, because a $2$ can only satisfy three squares labeled $3$ or $4$. And of the remaining squares labeled $3$ or $4$, at least $1/3$ must be labeled $3$. This means that $$ f(n)/n^2\le \frac15\cdot1 +\frac14\cdot \frac45\cdot2+\frac45\cdot \frac34\cdot \frac13\cdot 3+(1-\frac15-\frac14\cdot \frac45-\frac45\cdot \frac34\cdot \frac13)\cdot 4 =\frac{14}5 $$ On the other hand, we can acheive a sum which is close to $\frac{14}5n^2$ using this pattern. Namely, there is a single tile of area $5$, in the shape of a "$P$" pentomino, which tessellates the plane, where all tiles are labeled the same way.
In each block of $5$, there is a sum of $4+4+3+2+1=14$, achieving the claimed density of $14/5$. Now, there is a slight problem that these blocks of area five cannot exactly fill an $n\times n$ square. To fix this, first cover the entire $n\times n$ square with the tiling, allowing some tiles to go outside the box. Here is the result when $n=6$.
Note that some of the tiles do not have their requirements satisfied, since the numbers which satisfy them are outside of the $n\times n$ box. These are labeled in red. Here is one way to fix this:
The fact that the tiling does not quite fit, and these replacements, make a reduction in the total sum which is negligible compared to $\frac{14}5n^2$.
In order to compute $f(n)$ exactly, you would need a much more precise analysis, where you consider the number of $1$'s in the interior and on the border separately, and same for the other numbers.