Grades 11-12 Video Solutions 2011-11&12 Video Solutions 2011 problem29

Video Transcription

Question number 29. The cells of a 4x5 grid are filled with 20 different positive integers in such a way  that the numbers in two neighboring cells, that is, any two cells with a common edge, have a common divisor greater than 1. So here is such an example.  And note that neighboring cells, or cells that share an edge, are not relatively prime. So they have a common divisor greater than 1.  Now let n be the largest number in this grid, and our task is to find the smallest possible value of n. We have an example here where n is equal to 26.  And can we find a smaller value of n? We note that we have to remove, or not use, the number 1.  That's automatic, because if 1 were present and in the corner with 2 being the minimal number of neighbors, we would also have to use numbers that are, in fact, relatively  prime to 1, as 1 is relatively prime to all integers. So here, with just one number removed, n is bigger than or equal to 21.  20 cells, 20 would be the biggest number, but if we shift everything 1, n has to be at least 21. But with n equal to 21, we use the number 19.  We still use 19, which is prime, hence also we have to use 2 times 19 and 3 times 19. If 19 goes in the corner, it has 2 neighbors, and they cannot be relatively prime to 19,  so that has to be 2 and 3 times 19. So that doesn't work. So we keep increasing n by 1 like that, and with n bigger than or equal to 22, we still  use the number 17, having thrown 19 out. Hence also 2 times 17 and 3 times 17 have to be used. So that's bad. n is bigger than our current value of n, so we increment again.  Let n be bigger than or equal to 23, which is prime. So we use also 2 times 23 and 3 times 23, which is bad. We have to use at least 24. Let n be bigger than or equal to 24.  So we have thrown out a bunch of prime numbers. We still use the number 13, and if we use 13, also 26 and 39, which is bad, so we have to keep incrementing n.  Now with n bigger than or equal to 25, we have thrown out a bunch of prime numbers. We still use 11, and so also 22, which is fine, but 33 is not.  So finally, n has to be bigger than or equal to 26, which we have an example. So that's how we show that 26 is the smallest possible value, and so indeed it is the answer here.

Video Summary

In a 4x5 grid filled with 20 different positive integers, each pair of neighboring cells must share a common divisor greater than 1. The objective is to determine the smallest possible largest number, denoted as \( n \). By systematically evaluating lower values of \( n \) and the required inclusion of certain multiples that disrupt the conditions, it is shown that any attempt to reduce \( n \) below 26 involves using prime numbers or their multiples that don't satisfy the grid's constraints. Thus, the smallest possible \( n \) for which the grid's rules hold is 26.

Keywords

grid

positive integers

common divisor

smallest number

constraints