Fill a 3x5 board with integers 1-15

phanthanhtom · 2015-07-20 22:13:04

How many ways are there to fill a 3x5 board with integers 1-15 such that the sum of the numbers on each row is the same; and the sum of the numbers on each column is the same as well?

My current count is 9x3!x5!=6480.

Btw is there any formula for square boards (n x n) for the same question?

Agnishom · 2015-07-20 22:45:45

Should I place one integers from 1 to 15 exactly once in the board?

phanthanhtom · 2015-07-21 03:27:01

Yes, please.

For any given board, we can rearrange the columns and rows in 3!x5! ways.

If we call a "basic" board as one that has 1) the number 1 at the top left position and 2) have the first column and the first row both in ascending order, then I have found 9 basic boards (and thus I claim the number of boards is 9x3!x5!). Here they are:

1 - 3 - 11 - 12 - 13
8 - 7 - 9 - 10 - 6
15 - 14 - 4 - 2 -5

1 - 5 - 9 - 11 - 14
8 - 12 - 13 - 3 - 4
15 - 7 - 2 - 10 - 6

1 - 3 - 8 - 13 - 15
9 - 11 - 12 - 6 - 2
14 - 10 - 4 - 5 - 7

1 - 5 - 6 - 13 - 15
11 - 10 - 4 - 8 - 7
12 - 9 - 14 - 3 - 2

1 - 3 - 11 - 12 - 13
9 - 6 - 8 - 10 - 7
14 - 15 - 5 - 2 - 4

1 - 2 - 11 - 12 - 14
10 - 7 - 8 - 9 - 6
13 - 15 - 5 - 3 - 4

1 - 2 - 9 - 13 - 15
11 - 14 - 5 - 4 - 6
12 - 8 - 10 - 7 - 3

1 - 6 - 8 - 10 - 15
9 - 11 - 3 - 12 - 5
14 - 7 - 13 - 2 - 4

1 - 5 - 9 - 11 - 14
10 - 4 - 12 - 6 - 8
13 - 15 - 3 - 7 - 2

I think if the above nine are all the possible "basic" boards, then my answer (9x3!x5! = 6480) should be right. However, a math teacher from a specialised school disagreed. Can you find another "basic" board? Or maybe my conclusion that there could be 3!x5! rearrangements for each basic board is wrong? I'm a bit unsure on this.

Agnishom · 2015-07-21 03:45:07

I believe your conclusion about permuting the "basic" board is correct.

But are you doing all of these by hand?

phanthanhtom · 2015-07-21 03:58:25

I did it with a friend. She arranged the columns of 3 numbers and I rearranged them to fit rows with sum of 40.

Agnishom · 2015-07-21 05:19:30

Oh okay.

I just wrote some code and I am getting 28080. I might have done something wrong but I will postpone checking my code till tomorrow.

Maybe our beloved bobbym can help.

Agnishom · 2015-07-21 05:28:10

Wait, your reasoning is correct but there are more primitive boards than you expected. 39 of them!

Here are they:

[[1, 7, 8, 10, 14], [11, 15, 3, 5, 6], [12, 2, 13, 9, 4]]
[[1, 7, 8, 9, 15], [10, 11, 2, 12, 5], [13, 6, 14, 3, 4]]
[[1, 7, 8, 9, 15], [11, 4, 14, 5, 6], [12, 13, 2, 10, 3]]
[[1, 7, 9, 10, 13], [8, 3, 11, 12, 6], [15, 14, 4, 2, 5]]
[[1, 7, 9, 10, 13], [8, 14, 11, 2, 5], [15, 3, 4, 12, 6]]
[[1, 6, 8, 12, 13], [9, 3, 11, 10, 7], [14, 15, 5, 2, 4]]
[[1, 6, 8, 10, 15], [11, 14, 3, 5, 7], [12, 4, 13, 9, 2]]
[[1, 6, 8, 10, 15], [11, 4, 13, 5, 7], [12, 14, 3, 9, 2]]
[[1, 6, 8, 10, 15], [9, 11, 13, 2, 5], [14, 7, 3, 12, 4]]
[[1, 6, 8, 10, 15], [9, 11, 3, 12, 5], [14, 7, 13, 2, 4]]
[[1, 6, 9, 10, 14], [8, 13, 4, 12, 3], [15, 5, 11, 2, 7]]
[[1, 5, 6, 13, 15], [11, 10, 4, 8, 7], [12, 9, 14, 3, 2]]
[[1, 5, 6, 13, 15], [11, 10, 14, 3, 2], [12, 9, 4, 8, 7]]
[[1, 5, 7, 12, 15], [9, 11, 4, 10, 6], [14, 8, 13, 2, 3]]
[[1, 5, 9, 11, 14], [8, 12, 13, 3, 4], [15, 7, 2, 10, 6]]
[[1, 5, 9, 11, 14], [10, 4, 12, 6, 8], [13, 15, 3, 7, 2]]
[[1, 5, 10, 11, 13], [9, 15, 2, 6, 8], [14, 4, 12, 7, 3]]
[[1, 5, 10, 11, 13], [9, 4, 12, 7, 8], [14, 15, 2, 6, 3]]
[[1, 4, 8, 12, 15], [10, 14, 11, 3, 2], [13, 6, 5, 9, 7]]
[[1, 4, 8, 12, 15], [10, 14, 5, 9, 2], [13, 6, 11, 3, 7]]
[[1, 4, 8, 12, 15], [9, 7, 11, 10, 3], [14, 13, 5, 2, 6]]
[[1, 4, 8, 12, 15], [9, 13, 5, 10, 3], [14, 7, 11, 2, 6]]
[[1, 4, 9, 11, 15], [10, 6, 12, 5, 7], [13, 14, 3, 8, 2]]
[[1, 4, 10, 12, 13], [8, 14, 11, 5, 2], [15, 6, 3, 7, 9]]
[[1, 3, 7, 14, 15], [10, 12, 11, 2, 5], [13, 9, 6, 8, 4]]
[[1, 3, 7, 14, 15], [10, 12, 6, 8, 4], [13, 9, 11, 2, 5]]
[[1, 3, 8, 13, 15], [9, 11, 12, 6, 2], [14, 10, 4, 5, 7]]
[[1, 3, 9, 13, 14], [11, 15, 5, 7, 2], [12, 6, 10, 4, 8]]
[[1, 3, 10, 11, 15], [9, 8, 12, 6, 5], [14, 13, 2, 7, 4]]
[[1, 3, 10, 11, 15], [9, 8, 12, 7, 4], [14, 13, 2, 6, 5]]
[[1, 3, 11, 12, 13], [8, 7, 9, 10, 6], [15, 14, 4, 2, 5]]
[[1, 3, 11, 12, 13], [9, 6, 8, 10, 7], [14, 15, 5, 2, 4]]
[[1, 2, 9, 13, 15], [11, 14, 5, 4, 6], [12, 8, 10, 7, 3]]
[[1, 2, 9, 13, 15], [11, 14, 5, 7, 3], [12, 8, 10, 4, 6]]
[[1, 2, 10, 13, 14], [11, 15, 5, 3, 6], [12, 7, 9, 8, 4]]
[[1, 2, 11, 12, 14], [8, 9, 10, 7, 6], [15, 13, 3, 5, 4]]
[[1, 2, 11, 12, 14], [8, 13, 10, 5, 4], [15, 9, 3, 7, 6]]
[[1, 2, 11, 12, 14], [10, 7, 8, 9, 6], [13, 15, 5, 3, 4]]
[[1, 2, 11, 12, 14], [10, 15, 8, 3, 4], [13, 7, 5, 9, 6]]

[[a, b, c, d, e], [f, g, h, i, j], [k, l, m, n, o]] represents the following matrix:

So, the rest of your reasoning is okay since 39 * 5! * 3! = 28080

Last edited by Agnishom (2015-07-21 05:32:40)

phanthanhtom · 2015-07-21 11:26:32

Wow. Didn't expect it. Thanks a lot!

I'll print it out and meet her today.

Also, did you post those boards as an image? How did you do that?

Last edited by phanthanhtom (2015-07-21 11:30:31)

Agnishom · 2015-07-21 12:02:58

You're welcome!

I only posted an example as a matrix. It is done with LaTeX.

The majority of the boards (the ones with numbers) are selectable text. Are you having trouble selecting them?

I'll print it out and meet her today.

May I ask you why she needs this?

phanthanhtom · 2015-07-21 21:52:04

I copied it later. Thanks!

She brought me that problem.

Agnishom · 2015-07-21 22:18:58

Oh.

What is her opinion on my solution?

phanthanhtom · 2015-07-22 02:41:46

She said, "Is there any way to do this without a computer?". I couldn't answer.

Agnishom · 2015-07-22 05:19:37

The answer is "We do not know so far."

Or, here is a longer answer:

1) Can any problem be done without a computer?

This is actually a bad question: mainly because you're not defining a computer rigorously enough. So, instead you could ask:

2) If a problem looks trivial enough, can it be done by means of an average brain, a paper and a pencil and reasonable time?

An well known way to ask this question is If the solution can be verified easily, can the problem be done easily?. No one has solved this question till date.

But triviality is in the eye of the beholder. For example, there are many unsolved problems in number theory (Goldbach's anyone?) which at the first glance looks like were asked by a child; no one has solved them till date.

Textbook problems are designed to test whether you're able to apply the mathematics that you've been taught so far. Hence, the solution is already known even before the problem is framed. That is why they always have solutions. In the real world, we make answers to match the problems, not the other way round.

3) Is there a closed form formula for an m x n board?

I do not know. Maybe someone does, but most likely not. However, not being able to find out a closed form solution is not that bad.

It can indeed be proven (rigorously enough) that not all integer sequences have closed form formulae. The reason being there are an uncountably infinite number of sequences, but only a countably infinite number of closed form formulae.

By the way, there are problems that not even a computer can solve. (Look up halting problem)

4) Does that mean I should give up hope?

Not at all. More than trying to find a closed form expression, try searching for a smarter algorithm that solves the problem, whether by a computer or not. Of course, mathematics will be very useful in doing so.

Also, that does not mean you should give up on trying to find nice results and patterns. Even if there isn't one, it is a challenging task to prove why.

But these are two undeniable realities from the world of the abstract:
a) There is no shame in using a computer
b) Not everything would turn out to be a nice formula or a result in the end.

Last edited by Agnishom (2015-07-22 05:24:56)

Math Is Fun Forum

#1 2015-07-20 22:13:04

Fill a 3x5 board with integers 1-15

#2 2015-07-20 22:45:45

Re: Fill a 3x5 board with integers 1-15

#3 2015-07-21 03:27:01

Re: Fill a 3x5 board with integers 1-15

#4 2015-07-21 03:45:07

Re: Fill a 3x5 board with integers 1-15

#5 2015-07-21 03:58:25

Re: Fill a 3x5 board with integers 1-15

#6 2015-07-21 05:19:30

Re: Fill a 3x5 board with integers 1-15

#7 2015-07-21 05:28:10

Re: Fill a 3x5 board with integers 1-15

#8 2015-07-21 11:26:32

Re: Fill a 3x5 board with integers 1-15

#9 2015-07-21 12:02:58

Re: Fill a 3x5 board with integers 1-15

#10 2015-07-21 21:52:04

Re: Fill a 3x5 board with integers 1-15

#11 2015-07-21 22:18:58

Re: Fill a 3x5 board with integers 1-15

#12 2015-07-22 02:41:46

Re: Fill a 3x5 board with integers 1-15

#13 2015-07-22 05:19:37

Re: Fill a 3x5 board with integers 1-15

Board footer