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?

• A. 16
• B. 6
• C. 13
• D. 4
• E. 10

Hint:

Pigeonhole principle: With 4 rows, if you place 13 marks, at least one row will have 4 marks.

Answer 1

The Correct Option is C

Step 1: To maximize the number of moves, we want to avoid completing a full row or column as long as possible.
Step 2: In a 4×4 grid, a row or column has 4 cells. The game ends when any row or column has all 4 cells marked.
Step 3: To avoid completing a row, we can mark at most 3 cells in each row. Similarly, at most 3 cells in each column.
Step 4: Maximum cells without completing a row or column: 3 cells in each of 4 rows = 12 cells. But we must also ensure no column gets 4 marks.
Step 5: 12 marks can be arranged such that each column also has at most 3 marks (since 12 marks distributed across 4 columns gives average 3 per column). So we can have 12 marks without completing any row or column.
Step 6: The 13th mark must complete a row or column (by pigeonhole principl(e). Therefore, the maximum number of moves before the game ends is 13.
Step 7: Final Answer: 13.