Minimum Moves to Win Bingo!

I was all set to only relax on this long weekend and the only thing on top of my mind was Singapore elections and any good hope for a COVID vaccine. Just then something happened over an hour which brought afresh the nostalgic problem-solving undergrad days. My friend (Paras Miglani) came into my room and we decided to play a game of Bingo on my whiteboard! That was supposed to be just a time pass exercise but after playing maybe two games, we got obsessed into something we both liked! So, here is what we discussed and concluded so far in that hour-long discussion. The maths involved may not be the most optimal, but it was the best we could conceptualize in that period.

Bingo Gameplay

Although there are multiple versions of the Bingo game, read Wiki here, we played a simple 2-player version on a 5 X 5 board. Here was our gameplay:

1. Each player draws their 5 X 5 board and fills them in a secret pattern with numbers 1 - 25 (called range) with one in each cell without repeating any.
2. The game starts with a toss among players to decide which player goes first. And then the winner can start the next game. Players move one after another.
3. Game proceeds in successive moves of each player. With each player calls out a single number in the range, which both players cross out on their board.
4. Every time all numbers in any horizontal, vertical or diagonal line with length equal to the grid side, its crossed out and we get one successful line.
5. The first player to make 5 (each referring to a letter in the word Bingo) such successful lines wins the game.
6. In the end, remaining numbers on the grid can be matched on each player’s grid to make sure no one cheated or miss-crossed out any number!

The Big Question

Our obsession started with a thought in my head: what could be the minimum no of moves to win the game! Both of us quickly started drawing some possible grids with claims of having the most optimal solution. However, we settled that the following appears to be the minimal - two horizontal lines, two vertical lines and one diagonal cutting across all four horizontal/vertical lines. We could not arrive at a mathematical proof that this is the most optimal solution! However, we did try to reach a generalization using various other hints.

By now, we had realized the potential to generalize this problem and were enjoying it a lot. The question became:

What is the minimum number of moves needed to win an N X N Bingo grid, hence having N successful N-length horizontal/vertical/diagonal lines and a range of all 1 to N*N numbers on the grid?

Hit and Trials

We resorted to hit and trial approach to find the minimun for the N X N Bingo grid:

Bingo grid (1 x 1)

Just one line :-)

Bingo grid (2 x 2)

One horizontal + One diagonal.

Bingo grid (3 x 3)

One horizontal + One diagonal + One vertical.

Bingo grid (4 x 4)

Two horizontal + One diagonal + One vertical.

Observations

While doing a hit and trial for each N, I was able to draw following observations: (however not backed by math)

1. Our solution is not unique - which means that we can reach the same minimum moves from many arrangements. However, they all appear to be rotations of our solution.
2. Since our focus is to get the minimum moves, we have assumed that the second player will not spoil our result.
3. We have to see odd and even N separately: a. For cases when N is odd, we count one diagonal and equal no of vertical and horizontal lines as successful. b. For cases when N is even, we count one diagonal and either one more vertical or horizontal lines as successful.

Calculation

We wanted to derive an equation for the minimum, and here is how we did it:

Odd side-length grid: 2x+1 X 2x+1

We need to make x vertical lines, x horizontal lines and one diagonal:

Total cells to be covered by horizontal lines = x*(2x+1)
Total cells to be covered by vertical lines = x*(2x+1)
Total cells to be covered by diagonal line = 2x+1
Total cells to be covered by both horizontal and vertical lines = x*x
Total cells to be covered by diagonal line and not by horizontal or vertical lines = 1

Total cells hence needed = x*(2x+1) + x*(2x+1) - x*x + 1 = 3x*x + 2x + 1

3x*x + 2x + 1 is the min moves to win odd side-length 2x+1 X 2x+1 Bingo grid

Even side-length grid: 2x X 2x

We need to make x vertical lines, x-1 horizontal lines and one diagonal:

Total cells to be covered by horizontal lines = 2x*x
Total cells to be covered by vertical lines = 2x*(x-1)
Total cells to be covered by diagonal line = 2x
Total cells to be covered by both horizontal and vertical lines = x*(x-1)
Total cells to be covered by diagonal line and not by horizontal or vertical lines = 1

Total cells hence needed = 2x*(x) + 2x*(x-1) - x*(x-1) + 1 = 3x*x - x + 1

3x*x - x + 1 is the min moves to win even side-length 2x X 2x Bingo grid

This formula seems to match our Hit and Trial results. Time to check!

Test

Bingo grid (6 x 6)

By trial = 25
By formulae, (here x = 3, grid has even side-length) = 25

Bingo grid (7 x 7)

By trial = 34
By formulae, (here x = 3, grid has odd side-length) = 34

Closing Remarks

Its possible that what we did above has some conceptual or mathematical errors. But the experience of solving this thought was so delightful that it made me happy for spending the time at it. There are times when some timepass activity becomes very enjoyable. Probably this was one of it!