Results 1 to 2 of 2

Thread: 4x5 integer table

  1. #1
    Member u2_wa's Avatar
    Joined
    Nov 2008
    Posts
    119

    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
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    17

    Re: 4x5 integer table

    I present you with the following solution.

    Spoiler:


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

    $\displaystyle \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 $\displaystyle 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 $\displaystyle 2p, 3p, 4p, 5p$. If it appears on an edge, the neighbors are at least $\displaystyle 2p, 3p, 4p$. If it appears in a corner the neighbors are at least $\displaystyle 2p, 3p$. Using the lowest of these upper bounds $\displaystyle 3p$, in an optimal solution we must have that $\displaystyle 3p \leq 25$, or $\displaystyle p \leq 26/3 \leq 9$. That is, the only explicit primes in this table are at most $\displaystyle 2,3,5$ and $\displaystyle 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 $\displaystyle 1, 11, 13, 17, 19$ and $\displaystyle 23$. Since these numbers are not allowed in an optimal solution, the solution I provided must be optimal. Therefore $\displaystyle 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