# 4x5 integer table

• Aug 26th 2012, 12:00 AM
u2_wa
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.
• Aug 26th 2012, 07:36 PM
Vlasev
Re: 4x5 integer table
I present you with the following solution.

Spoiler:

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$.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 16, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8641340136528015, "perplexity": 179.06662508890196}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2017-04/segments/1484560280128.70/warc/CC-MAIN-20170116095120-00156-ip-10-171-10-70.ec2.internal.warc.gz"}