Results 1 to 2 of 2

Thread: 4x5 integer table

  1. #1
    Member u2_wa's Avatar
    Nov 2008

    Tricky Integer Table

    Twenty different positive integers are written in a 4 X 5 table. Any two neighbours (numbers in cells with a common side) have a common divisor greater than 1. If n is the largest number in the table, find the smallest possible value of n.
    Last edited by u2_wa; Aug 26th 2012 at 09:55 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Jul 2010

    Re: 4x5 integer table

    I present you with the following solution.


    Let m the minimum such n. I came up with the following upper bound: m \leq 26 with the following solution to the puzzle

    \begin{bmatrix}3   & 6  & 15  & 25  & 5 \\24 & 9   & 18 & 20 & 10\\21 & 12 & 26 & 8 & 4\\7   & 14 & 22  & 16 & 2\end{bmatrix}

    If we inspect this table, we see that it satisfies the conditions for divisibility and the upper bound is correct. Now, if a prime p appears explicitly in the table, its neighbors must be divisible by that prime. If the prime appears in the interior, its neighbors must be at least the sizes 2p, 3p, 4p, 5p. If it appears on an edge, the neighbors are at least 2p, 3p, 4p. If it appears in a corner the neighbors are at least 2p, 3p. Using the lowest of these upper bounds 3p, in an optimal solution we must have that 3p \leq 25, or p \leq 26/3 \leq 9. That is, the only explicit primes in this table are at most 2,3,5 and 7. No other primes can appear explicitly in the table. As we can see, up to 26, the only numbers that do not appear in this table are 1, 11, 13, 17, 19 and 23. Since these numbers are not allowed in an optimal solution, the solution I provided must be optimal. Therefore m = 26.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 13
    Last Post: Aug 3rd 2010, 03:16 AM
  2. Integer roots of integer polynomials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 3rd 2009, 12:39 PM
  3. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 12:20 PM
  4. [SOLVED] even integer and odd integer
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Oct 1st 2008, 08:35 PM
  5. table salt + table sugar
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: Sep 9th 2007, 08:35 AM

Search Tags

/mathhelpforum @mathhelpforum