Competition problem — Combinatorics

Library / /185 of 520

Combinatorics Difficulty 5.4 AIME, harder Find the answer

Gálnierin $\Gamma$ .

In each cell of a secret $n \times n$ table, one of the digits from 1 to 9 is written. From these, $n$ -digit numbers are formed, written from left to right in the rows and from top to bottom in the columns. Petya wants to write an $n$ -digit number without zeros in its representation, such that neither this number nor its reverse matches any of the $2n$ numbers in the rows and columns of the table. What is the minimum number of cells Petya needs to know the digits of to achieve this?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

If less than $n$ cells have been checked, then in some row of the checked cells there is none, and any numbers can be there.

Suppose Petya has checked $n$ cells along the diagonal, at the intersection of rows and columns with the same numbers. Then it is enough for Petya to present a palindrome number, in which the $i$ -th and ( $n-i$ )-th positions contain the same digit, different from the digits in the checked cells of the $i$ -th and ( $n-i$ )-th rows. Such a number will differ from the numbers in the $k$ -th row and $k$ -th column precisely by the $k$ -th digit.

## Answer

In $n$ cells.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.