Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

phanthanhtom
Member
Registered: 2012-06-22
Posts: 290

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

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)

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

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

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

phanthanhtom
Member
Registered: 2012-06-22
Posts: 290

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

That is right.

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

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

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):


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

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

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)


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

Hi;

I get it now. Thanks for the explanation.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

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

Hej bobbym

Inget problem! smile


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

The what problem?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

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

"No problem". smile


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

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

In Swedish it is.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

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


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

phanthanhtom
Member
Registered: 2012-06-22
Posts: 290

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

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:

Offline

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

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

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

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?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

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

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.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

Board footer

Powered by FluxBB