Consider a chessboard that is infinite in all directions. Alex the T-rex wishes to place a positive integer in each square in such a way that: No two numbers are equal. If a number m is placed on square C, then at least k of the squares orthogonally adjacent to C have a multiple of m written on them. What is the greatest value of k for which this is possible?
Problem
Source: Mexico National Olympiad Mock Exam 2021 P5
Tags: combinatorics
12.11.2021 07:22
The answer is k=2. First, two adjacent squares can't both divide each other so k≠4. To show k can't be 3, consider a square with a number a and say the number ka is written next to it. Also WLOG let the number not divisible by a adjacent to it be to its left. Then below ka, there must be a multiple of it, say its akb. But then the square to the left of this has to be a multiple of both a and akb, so can't divide either of them. For k=2, a construction is as follows. First place the numbers 1,2,4,8 in a 2×2 square. I claim we can just keep adding a new row or column to the current rectangle while still maintaining the condition, which finishes. But this is easy, since pick the top right square and add a multiple of it to its right. Then below it, take a multiple of the product of numbers on the left and top(take the multiples big enough to ensure distinctness). This works. ◼
12.11.2021 14:07
We prove that k=2.We prove that that k cannot be 3.Assume the contrary.Just choose any cell with say m written on it and neighbours a,b,such that they form an L and a,b>m.Now,let n be the other common neighbour of a,b.WLOG,a>b,now since m<a,so n>a>b but ,then n has atmost 2 such neighbours,which is a contradiction. For the construction,start with a row,which extends infinitely right.,number it 1.Then fill the ith cell in the row with number 2.3i,with i,increasing right. Then add rows on top of it and for row j,fill it with numbers 2j.3i,similarly.This clearly works as every number divides the number on top and right of it.
13.11.2021 08:53
Original (and harder) statement: Let n be a positive integer. We say that the two points in n-dimensional Euclidean space with integer coordinates (x1,x2,…,xn) and (y1,y2,…,yn) are adjacent if and only if |x1−y1|+|x2−y2|+⋯+|xn−yn|=1. Alex the T-rex wishes to place a positive integer in every point with integer coordinates in n-dimensional Euclidean space in such a way that: No two numbers are equal. If a number m is placed on point P, then at least k of the points adjacent to P have a multiple of m written on them. What is the greatest value of k for which this is possible?