Min of the largest sum of adjacent numbers in a 2nx2n array

phanthanhtom · 2015-09-19 23:14:43

Fill a 2nx2n array with the numbers from 1 to

. Calculate all the sums of two adjacent numbers (sharing an edge is considered adjacent). Suppose S is the largest sum. Express min S in terms of n.

Last edited by phanthanhtom (2015-09-19 23:15:29)

bobbym · 2015-09-20 01:43:24

S is the largest sum. What is min of S?

anonimnystefy · 2015-09-20 02:42:32

The minimum of S across all possible ways to fill the grid up, I am guessing?

phanthanhtom · 2015-09-20 03:51:05

That is right.

For example, min S(1) = 6 and min S(2) = 19.

bobbym · 2015-09-20 05:00:23

If it is the min, then why is not S(1) = 3? And where does the 19 come from in S(2)?

anonimnystefy · 2015-09-20 05:38:11

Hej bobbym

You look at all possible fillings of the grid and for each filling you see what the maximum sum of adjacent ellements is. Then you find the minimum of those numbers.

For example, for n=1, you are filling a 2x2 grid with numbers 1,2,3,4. The lowest adjacent sum, which is 6, can be obtained with the filling:

or any equivalent filling, (obtained by rotation or symmetrical mapping, t.ex.)

For n=2, a filling with S=19 *can* be found, but I am not sure if there is a lower one (probably not):

bobbym · 2015-09-20 06:11:25

Hi;

Why can you not use 1 + 3 = 4 in the first one? And why use 16 + 3 in the second one? There are higher and lower ones in that very diagram.

anonimnystefy · 2015-09-20 09:49:40

Hej,

You are usign the highest sum you can find in the grid. In the 2x2 case, that is 6. If you arrange the numbers any other way, you'll get a higher maximum sum. For example:

Here, the highest sum is 7, which is higher than the 6 for the previous grid, so we do not want that.

For the second, 4x4 grid, the highest sum inside it is 19. To prove that this is the minimal highest sum, we would need to prove that for all other arrangements of numbers from 1 to 16 into the grid, there will be two adjacent numbers which sum to 19 or higher.

Last edited by anonimnystefy (2015-09-20 09:50:06)

bobbym · 2015-09-20 10:49:46

Hi;

I get it now. Thanks for the explanation.

anonimnystefy · 2015-09-20 15:20:13

Hej bobbym

Inget problem!

bobbym · 2015-09-20 15:24:31

The what problem?

anonimnystefy · 2015-09-20 15:30:04

"No problem".

bobbym · 2015-09-20 16:09:31

In Swedish it is.

Agnishom · 2015-09-20 21:07:45

Hi phanthanhtom;

Is this is a problem about the extremal principle? If it is a proof question, please post the expression: reverse engeneering the answer might be easier

phanthanhtom · 2015-09-20 23:10:23

No, I don't have the expression.

I can prove S(2) = 19.

First of all, if 16 is in a square with 3 or 4 adjacent squares then one of its neighbours will be at least 3. Thus there will be a sum of at least 19.

Otherwise, 16 is in a corner. We prove that then the maximum sum will still be at least 19. If 3, 4, 5 etc is adjacent to 16 then QED. Suppose 16's neighbours are 1 and 2. Then wherever 15 is, it must have at least two neighbours other than 1 or 2. Thus 15 must have a neighbour at least 4 in value, and the sum would then be 4.

However, I did try to use a kind of checkerboard pattern like this:

16 - 02 - 13 - 06
01 - 14 - 05 - 10
15 - 04 - 11 - 08
03 - 12 - 07 - 09

When I apply this kind of checkerboard pattern to n from 3 to 5 I get S(3) = 40, S(4) = 69 and S(5) = 106. (ofc I'm not sure if this pattern yields the smallest S). Therefore I'm proposing that:

Agnishom · 2015-09-22 04:50:54

First of all, if 16 is in a square with 3 or 4 adjacent squares then one of its neighbours will be at least 3. Thus there will be a sum of at least 19.
Otherwise, 16 is in a corner. We prove that then the maximum sum will still be at least 19. If 3, 4, 5 etc is adjacent to 16 then QED. Suppose 16's neighbours are 1 and 2. Then wherever 15 is, it must have at least two neighbours other than 1 or 2. Thus 15 must have a neighbour at least 4 in value, and the sum would then be 4.

But how does the proof ensure that, say, 14 and 11 are not adjacent?

anonimnystefy · 2015-09-22 17:32:26

Well, their proof shows that the minumum is 19 or greater. After that, we only one example of the sum being 19 to prove that is the minimum.

Math Is Fun Forum

#1 2015-09-19 23:14:43

Min of the largest sum of adjacent numbers in a 2nx2n array

#2 2015-09-20 01:43:24

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#3 2015-09-20 02:42:32

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#4 2015-09-20 03:51:05

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#5 2015-09-20 05:00:23

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#6 2015-09-20 05:38:11

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#7 2015-09-20 06:11:25

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#8 2015-09-20 09:49:40

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#9 2015-09-20 10:49:46

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#10 2015-09-20 15:20:13

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#11 2015-09-20 15:24:31

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#12 2015-09-20 15:30:04

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#13 2015-09-20 16:09:31

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#14 2015-09-20 21:07:45

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#15 2015-09-20 23:10:23

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#16 2015-09-22 04:50:54

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

#17 2015-09-22 17:32:26

Re: Min of the largest sum of adjacent numbers in a 2nx2n array

Board footer