Grid Game Maximum Steps

Question

In a computer game, each move requires pressing a button. When the button is pressed for the first time, as a move, the computer randomly chooses a cell from a 4x4 grid of sixteen cells and puts an "X" mark on that cell. When the button is pressed subsequently, the computer randomly chooses a cell from the remaining unmarked cells and puts an "X" mark on that cell. This goes on till the end of the game. The game ends when either all the cells in any one row, or all the cells in any one column, are marked with "X".

What is the maximum possible number of times a player has to press the button to finish the game?

Accepted Answer

D. We want to place as many 'X' marks as possible on a 4x4 grid without completing any full row or column. To avoid completing any row or column, each row must have at most 3 'X's, and each column must have at most 3 'X's. By placing 'X' on 12 non-diagonal cells (leaving 4 diagonal cells unmarked, 1 per row and column), every row has 3 'X's and every column has 3 'X's. No row or column is completed with 12 marks. The 13th mark must be placed on one of the remaining 4 empty cells, which immediately completes both a row and a column. Thus, the maximum number of moves required is 13.

Answer

16

Answer

10

Answer

6

Answer

13

Answer

4

Grid Game Maximum Steps

Explanation

Related Combinatorics questions

Practise this under exam conditions