An $n$ by $n$ grid, where every square contains a number, is called an $n$-code if the numbers in every row and column form an arithmetic progression. If it is sufficient to know the numbers in certain squares of an $n$-code to obtain the numbers in the entire grid, call these squares a key. a.) Find the smallest $s \in \mathbb{N}$ such that any $s$ squares in an $n-$code $(n \geq 4)$ form a key. b.) Find the smallest $t \in \mathbb{N}$ such that any $t$ squares along the diagonals of an $n$-code $(n \geq 4)$ form a key.
Problem
Source: China TST 1994, problem 2
Tags: function, ratio, arithmetic sequence, algebra, system of equations, combinatorics unsolved, combinatorics
25.05.2005 00:06
a) in worst case scenario, you can first pcik n numbers on thesame line or column with which you cannot find the whole grid obviously. Then if you pick one more number outside that line you cal also find the column of that number using the number on that column from the line you already know. And now if you know a line and a column you know all the grid.This is simple to show: suppose we know the first and last column and take another cell which is on neither fo these -suppose we take cell 3,3. Let's denote by x the value in this cell. Already you can express the value of the cel 2,3 as a function of x (more precisely it's the arithmetic media of x and the value of cell 1,3). Now if you know cell 2,3 depending on x, you know the whole row number 2 depending on x since the last value on that row (the one corresponding to the last column) you already know, and it's a known number. Working the same you can express the cells of row 3 as functions of x. So, you know the cell 2,2 for example as a function of x, and the cell 3,2 as a function of x. Now knowing that cells (1,2 )(which you know as being a cell on row 1), (2,2) and (3,2) form an arithmetic progression you can determine x. This was you can find out the whole grid. b) if you know just 2 numbers on the diagonal, you can arbitrarelly choose a progression for the line corresponding to the first number, and then with that line and the second number you can complete the grid as shown for point a). So since in the beginning we chose the ration arbitrarlly it means we have an infinite number of solutions so thw numbers are not enough. But three are as if you know 3 numbers on the diagonals, you just take the cells at the intersection of their lines and columns, this means a 3 X 3 square in which if you form a system of equations having as nedeterminates the ratios on the columns corresponding to those 3 numbers let's say, you can solve and thus determine 3 columns of the grid which are enough to determine the whole n-code.
06.08.2018 20:59
fdump wrote: a) in worst case scenario, you can first pcik n numbers on thesame line or column with which you cannot find the whole grid obviously. Then if you pick one more number outside that line you cal also find the column of that number using the number on that column from the line you already know. And now if you know a line and a column you know all the grid.This is simple to show: suppose we know the first and last column and take another cell which is on neither fo these -suppose we take cell 3,3. Let's denote by x the value in this cell. Already you can express the value of the cel 2,3 as a function of x (more precisely it's the arithmetic media of x and the value of cell 1,3). Now if you know cell 2,3 depending on x, you know the whole row number 2 depending on x since the last value on that row (the one corresponding to the last column) you already know, and it's a known number. Working the same you can express the cells of row 3 as functions of x. So, you know the cell 2,2 for example as a function of x, and the cell 3,2 as a function of x. Now knowing that cells (1,2 )(which you know as being a cell on row 1), (2,2) and (3,2) form an arithmetic progression you can determine x. This was you can find out the whole grid. b) if you know just 2 numbers on the diagonal, you can arbitrarelly choose a progression for the line corresponding to the first number, and then with that line and the second number you can complete the grid as shown for point a). So since in the beginning we chose the ration arbitrarlly it means we have an infinite number of solutions so thw numbers are not enough. But three are as if you know 3 numbers on the diagonals, you just take the cells at the intersection of their lines and columns, this means a 3 X 3 square in which if you form a system of equations having as nedeterminates the ratios on the columns corresponding to those 3 numbers let's say, you can solve and thus determine 3 columns of the grid which are enough to determine the whole n-code. Your answer for a) is incorrect smallest $s$ is $2n$.First we call the highest row in an grid number $1$ ,one beneath it $2$ and so on until the last row $n$.We call the leftmost column $1$,next on right $2$ and so on until last column which we call $n$. Row $a$ and column $b$ intersect each other at square that square is $(a,b)$ . Now we show that if we know $2n-1$ or less squares there exist two solutions for table.Let the sqaures we know be $(1,1)$,$(1,2)$,...,$(1,n)$,$(2,1)$,$(3,1)$,...,$(n,1)$ ;and in them are all zeroes. Then there are two solutions; whole table is filled with zeroes, and other solution is that in square $(a,b)$ is number $(a-1)(b-1)$ (it is trivial to see that second construction is indeed solution).Now we show that if we know value in $2n$ squares we know whole table.Next it is easy to see that if we know two sqaures in column or row we know that column or row.Notice that if we know two whole columns (or rows) we know whole table because in every row (column) we know two squares so we know every row (column), so it is sufficient to show that we know two whole columns (rows).We know two columns if we know two squares in two different columns ,but this must trivialy exist because if we have only one row with two or more squares, that we know, then we know less than or equal to $n+n-1=2n-1$ squares contradiction,so we know two squares in two different columns, because of that we know two columns ,a then we know whole table and we are done.For part b) i dont understand part with diagonals.
06.08.2018 21:17
If these diagonals are two main diagonals than answer is $n+1$.Example that $n$ is impossible is we know one diagonal and in it are alll zeroes, than there are two solutions:all zeroes,in a square $(a,b)$ is $ab-4$.Now show that we can find whole table .There are two squares in same row(trivial) so we know that row.Next we know two squares in different columns(none of them belongs to row we know trivial to prove that exist) so we know these two columns . Now we know two columns so we know whole table(proved in post above).We are done.