Ball In A Box

Disclaimer: this is a qualitative solution (not a formal proof). It still led me to guess the correct solution.

We know the answer shall be between 100 (density: $\frac{\pi}{4} = 0,785$ ) and 115 (most dense packing of discs, with density: $\frac{\pi}{2 \sqrt{3} } = 0,907$ ). Let us try to narrow the interval to find the answer.

If we try to pave a 10X10 grid in an hexagonal way, we can manage to put 105 discs (6 rows of 10, and 5 rows of 9):

This paving seems very satisfactory in the "bottom" of the grid, but there is quite some spare at the top, as the height of the packing is: $H = 5c +1 = 9,66$ , where $c = \sqrt{3}$ is the height of the hexagonal packing unit.

This idea is to improve the top of the packing by taking advantage of the vertical spare space, using a square paving for the top of the packing (last two rows):

The square paving, while it is less vertically efficient, allows to put more discs in the horizontal axis (10 for every row, instead of 10 every other row). We can put one more disc this way.

Now the height is $H = 4c +3 = 9,93$ : if we try to arrange one more row in a square pakcing, the height would be: $H = 3,5c +4 = 10,06$ , which shows that this is the best we can do with this method.

From this heuristic approach, we conclude that the answer should be $\boxed{106}$

The pattern will contain $p$ rows of 10 balls and $q$ rows of 9 balls. Normally each row takes up 1 unit of vertical length, but wherever two rows of different length touch each other, we save $1 - \tfrac12\sqrt 3$ units of length.

An optimal pattern will have $p \geq q$ . For if $p < q$ , we could replace all rows of 9 balls by rows of 10, and vice versa; this will increase the total number of balls without changing the length needed.

Also, in an optimal pattern every row of 9 balls is directly located between two rows of 10 balls, because this maximizes the number of alternations, and therefore the amount of length saved. The only possible exception is if $q = p$ , in which case one row of 9 is at the end of the pattern. It is not difficult to see that we can make $2q$ alternations between the different kinds of rows if $p > q$ , and $2q - 1$ if $p = q$ .

We have the following mathematical model: $N = 10p + 9q = 19q + 10(p-q)\ \ \ \ \ \text{(number of balls)} \\ \ell = p + q - (1 - \tfrac12\sqrt 3)\cdot 2q = \sqrt 3 q + (p-q)\ \ \ \ \ \text{(vertical length)}.$ (But if $p = q$ , we must increase $\ell$ by $1 - \tfrac12\sqrt 3$ .)

We want to optimize $N$ under the condition $\ell \leq 10$ and $p - q \geq 0$ . The following graph shows the situation: We must stay above the blue line to keep $p - q \geq 0$ ; and below the red line to keep $\ell \leq 10$ . The green lines show where $N = 100, 105, 110$ respectively; the arrow indicates the direction in which the optimal point is to be found.

The basic solution is found on the intersection of the two conditions: the intersection of the blue and red lines, with $p = q = 10/\sqrt 3 \approx 5.774$ and $N \approx 109.70$ . However, $p$ and $q$ must be integers.

In the graph the nearest grid point is $(q, p) = (5, 6)$ . This would give $\ell = 1 + 5\sqrt 3 \approx 9.66$ and $N = 105$ . However, there is a better alternative: $(q, p) = (4, 7)$ . This gives $\ell = 3 + 4\sqrt 3 \approx 9.93$ , thus utilizing the vertical length better; and $N = \boxed{106}$ .

Hexagonal packing of 11 rows as below:

2*(10+9+10+9+10)+10 =106

Answer=106

I followed the same reasoning as Mat, but had something rattling around in my head about random packing.

The following link confirms 106 but throws up some interesting patterns for other square sizes.

The best known packing of equal circles in a square