A $n\cdot n$ square grid problem?

Question

I thought of this problem when I was playing a game called BINGO with my friend. The game basically is like this:

Suppose $2$ people are playing the game(can be played with any no of people though). Both make a $5\cdot 5$ square grid and and fill the numbers from $1$ to $25$ in the grid at random, i.e. you can fill any numbers anywhere inside the grid. So each has his own grid and doesn't show it to other.

The first player now calls any number between $1$ to $25$. The second player then can call any of the remaining $24$ numbers. The players call the numbers alternately and keep circling the numbers on their grid. The first player to get $5$ groups of $5$ numbers across the row, column or diagonal (overlapping of numbers allowed) wins the game. Bingo!

So the final grid may look something like this:

Now, this game can easily be extended to $6\cdot 6$ or $7\cdot 7$ (you may call this BAZINGA). In genreal $n\cdot n$ grid where you have to get $n$ group of $n$ numbers across row,column or diagonal.

Finally, the question is this:

What is the minimum number of numbers to be used to make the group of numbers as required by the game. For $5\cdot 5$ grid, at least 17 entries have to be used (as in the image above). How do I generalise the result for $n\cdot n$ grid?

I think there exists a recursive relation. Although this wouldn't help me in winning the game, your solution is appreciated.

Answer 1

It depends on $n$ being odd or even so we'll deal with these separately:

Odd:

The minimum is as how you've drawn it for $n=5$. We have:

Cells down the first $\frac{n-1}{2}$ vertical lines: $\frac{n-1}{2} \times n$.

Extra cells across the first $\frac{n-1}{2}$ horizontal lines: $\frac{n-1}{2} \times \frac{n+1}{2}$.

Extra cells for the diagonal: $1$.

Summing: \begin{eqnarray*} \mbox{Total} &=& \frac{n-1}{2} \times n + \frac{n-1}{2} \times \frac{n+1}{2} + 1 \\ && \\ &=& \frac{n^2 - n}{2} + \frac{n^2-1}{4} + 1 \\ && \\ &=& \frac{1}{4} \left(3n^2 - 2n + 3\right) \end{eqnarray*}

This gives $17$ when $n=5$, which agrees with your answer.

Even:

The minimum is with the first $\frac{n}{2}$ cols, the first $\frac{n}{2} - 1$ rows plus the diagonal (from top-right corner). We have:

Cells down the first $\frac{n}{2}$ vertical lines: $\frac{n}{2} \times n$.

Extra cells across the first $\frac{n}{2} - 1$ horizontal lines: $\frac{n}{2} - 1 \times \frac{n}{2}$.

Extra cells for the diagonal: $1$.

Summing: \begin{eqnarray*} \mbox{Total} &=& \frac{n}{2} \times n + \left(\frac{n}{2} - 1\right) \times \frac{n}{2} + 1 \\ && \\ &=& \frac{1}{2}n^2 + \frac{1}{4}n^2 - \frac{n}{2} + 1 \\ && \\ &=& \frac{1}{4} \left(3n^2 - 2n + 4\right) \end{eqnarray*}

Answer 2

Let's see.

For 2x2, the answer is 4; there's only 6 lines, and placing three only gives you three of them.

For 3x3 the answer is I think 7, arranged in an H formation; in this situation, you cover both diagonals.

4x4 I think is the first place we get to something that looks like the general solution, and it takes up 12: two rows and two columns, in such a way that one of the diagonals is fully covered.

for 5x5 and up, you have two rows, two columns, and one of the diagonals, which you've already covered 4 parts of with the rows and columns. So that's $2n + 2(n-2) + n-4 = 5n - 8$.

I can't think of a better way to do larger squares, so I'm guessing that's your answer.

... wait, I need to do the counting for the two-diagonal method too, let's see how that turns out.

---

Okay there's three different methods here. The first is with no diagonals. You get $5n - a(5-a)$ squares, where $a$ is the number of rows that you fill. This gives, at maximum, $5n - 6$.

The second, with one diagonal, you first place two rows and two columns to maximize the overlap between those (if you place three and one, you get only 3 overlap instead of 4). You can then place teh diagonal so that it hits all four rows/columns in separate places, totalling $5n - 8$.

The third, with both diagonals, has two cases: $n$ odd, and $n$ even.

The main difference between them is that $n$ even gives no overlap between the diagonals, where $n$ odd does; this reduces odd $n$'s requirement by 1. $2n$ or $2n - 1$ so far.

Then we can pick a row to cover; as long as we don't pick the center in $n$ odd, this gives $n - 2$ for placing that one, so we're at $3n - 2$ or $3n - 3$

Now we pick two columns, such that they hit both diagonals and the chosen row at different places. This gives $n - 3$ for each, for $2n - 6$ for both, and $5n - 8$ or $5n - 9$ for all five.

So the right answer is: You can place 16 on a 5x5 grid to collect five lines, and $5n - 8 - (1 \text{ if } n \text{ is odd})$ in general. This works all the way down to size 4.