Not-Quite-Sufficiently-Advanced-Technology Square

Question

This was given as an assignment to a group of sixth graders, who were told they could use calculators. Beyond that, no real assistance was provided. They were not working on it as a group, so independent effort was presumably expected.

---

MAGIC SQUARE

Place the numbers provided into the grid so that the numbers ACROSS every row and DOWN every column add up to 200.

$$\begin{array}{|c|c|c|c|c|}\hline27&&&&36\\\hline&40&&19\\\hline&&42\\\hline&47&&42\\\hline32&&&&35\\\hline\end{array}$$

Numbers:
$ ~~~~ ~~~~ \boxed{66} ~~~~ \boxed{46} ~~~~ \boxed{15} ~~~~ \boxed{41} ~~~~ \boxed{30} ~~~~ \boxed{72} ~~~~ \boxed{24} ~~~~ \boxed{28} $ $ ~~~~ ~~~~ \boxed{25} ~~~~ \boxed{66} ~~~~ \boxed{39} ~~~~ \boxed{22} ~~~~ \boxed{45} ~~~~ \boxed{54} ~~~~ \boxed{58} ~~~~ \boxed{49} ~~~~ $

---

First, this isn't going to be a real "Magic Square" for a number of reasons, but we'll ignore that.
The thing is, even with the grid partially filled in, a true unconfined brute-force search for a solution would take a very long time. A more intelligently created exhaustive search program can find a solution in seconds (there are two), but still requires a LOT of permutations to be evaluated. By computer, that's fast. With a hand-held calculator alone, manually keeping track of and testing the various permutations would be hellishly impractical.

So -
Is there a way to solve this, using only pencil and paper and a calculator, without sheer luck or exhaustive effort?
(Or, to put it another way, is this in any way a fair assignment for a sixth grader?)

---

Bonus Question

Ok, I'll add this because some of you will want to try it.
Go ahead, find the two solutions any way you like. First one to supply them gets the brownie points.
But I'm mainly interested in a practical no-computers method, if one exists.

Answer 1

I was able to find one of the solutions using "paper and pencil". I stopped searching for more solutions after that. It is certainly very very time consuming.

In my explanation I name rows as A,B,C,D,E - columns as 1, 2, 3, 4, 5. My search strategy is based on an observation that

The sum of the unknown numbers in the first column is the same as the sum of the unknown numbers in the row $B$ and it is equal to $141$. This means

$ B1+B3+B5 = B1+C1+D1 = 141 $

$ B3+B5 = C1+D1 $

So I calculated (in the same way as @rinspy) all 106 pair-wise sums of the 16 given numbers and found which sums can be represented (a) in two different ways and (b) can be combined with a third given number to get to $141$. The results of this stage is shown on page 1.

As you can see this gave me only 4 possible values for $B1$

$30, 45, 54, 72$

Page 2 shows how I eliminated the first possible value for $B1$

$30$.
I considered cases when {39, 72} goes to column $1$ and to a row $B$. All of them lead to a contradiction - impossibility. Pair-wise sums from page 1 served as a simple lookup table. In most cases if you lookup a sum of two numbers the table tells you if this sum is impossible to get or gives you very few possible number combinations.

The second possible value for $B1$ lead to a solution. Pages 3-5 show the search and elimination process.

Page 3

Page 4

Page 5

Answer 2

These are the two solutions I found by 80x86 PC:

$\begin{array}{|c|c|c|c|c|} \hline \color{purple}{27} & \color{black}{46} & \color{black}{25} & \color{black}{66} & \color{purple}{36}\\ \hline \color{black}{72} & \color{purple}{40} & \color{black}{28} & \color{purple}{19} & \color{black}{41}\\ \hline \color{black}{54} & \color{black}{22} & \color{purple}{42} & \color{black}{24} & \color{black}{58}\\ \hline \color{black}{15} & \color{purple}{47} & \color{black}{66} & \color{purple}{42} & \color{black}{30}\\ \hline \color{purple}{32} & \color{black}{45} & \color{black}{39} & \color{black}{49} & \color{purple}{35}\\ \hline \end{array}$

$\begin{array}{|c|c|c|c|c|} \hline \color{purple}{27} & \color{black}{25} & \color{black}{54} & \color{black}{58} & \color{purple}{36}\\ \hline \color{black}{45} & \color{purple}{40} & \color{black}{30} & \color{purple}{19} & \color{black}{66}\\ \hline \color{black}{72} & \color{black}{49} & \color{purple}{42} & \color{black}{15} & \color{black}{22}\\ \hline \color{black}{24} & \color{purple}{47} & \color{black}{46} & \color{purple}{42} & \color{black}{41}\\ \hline \color{purple}{32} & \color{black}{39} & \color{black}{28} & \color{black}{66} & \color{purple}{35}\\ \hline \end{array}$

Edit: about pencil / paper / calculator

For the top row alone, there are $16! / 13! = 3360$ ordered ways to pick $3$ numbers from the $16$ available. Of those there are (by computation) $36$ distinct orderings which will sum the row to $200$.

So without some trick it looks like an unrealistic task.

Answer 3

The way I would approach this is as follows:

1. Sort the 16 numbers
2. Find sets of numbers that can fit into rows 1, 2, 4, 5. There are 105 possibilities to try for each (in reality a lot fewer, as for each 1st number pick you can eliminate some 2nd number picks, i.e. if you pick 15, the 2nd number has to be > 200-27-36-15-72 which leaves only 4 options, etc.).
3. Hopefully there will only be a small number of non-contradictory sets of 3 numbers for these rows. So we know which numbers go in rows 1,2,4,5, but not their order. We also have a much smaller set of remaining numbers to work with now.

Edit: Fairly quickly we can find the following candidate triples:

Row 1: (22,49,66), (24,41,72), (25,46,66), (30,41,66)

Row 2: (15,54,72), (24,45,72), (28,41,72), (30,39,72), (30,45,66), (41,46, 54)

Row 4: (15,24,72), (15,30,66), (24,41,46), (25,28,58), (25,41,45)

Row 5: (15,46,72), (30,45,58), (30,49,54), (39,45,49)

Hopefully from there on it should be reasonably straightforward to arrive at the correct answer.

Edit2: We then consider the possibilities for column 1. As @ppgdev, we note that the 3 numbers there have the same sum as row 2, which means that row 2 and row 4 must contain numbers that are in the same other row 2 possible combination. So we have to only go through 6 possible row 2 / column 1 options.

For example, the first option for column 1 to try is (15,54,72). That means that:

1. Row 2 cannot be (15,54,72), as both row 2 and row 4 have to have one of 15, 54, 72 in them
2. Then possible combinations for row 2 and row 4 are: [(24,45,72),(15,30,66)], [(28,41,72),(15,30,66)], [(41,46,54),(15,30,66)].
3. The only option that fits row 1 is [(28,41,72),(15,30,66)]. So the possibilites are, including rows 1 and 5: [(25,46,66),(28,41,72),(15,30,66),(39,45,49)]. And we know that row 2 starts with 72, row 4 starts with 15, and the remaining number in column 1 is 54. Now just 16 combinations of the other numbers left to try.

As it happens, it allows us to complete the puzzle; but if it didn't and we reached a dead end, there are only 5 other options for column 1 left to try.

So overall, a determined sixth grader should be able to solve it. It can also teach them to estimate computational complexity, as they quickly find that brute force will not get them anywhere, and that there are only a few things they could try that are computationally feasible. If it is a group assignment - even easier, as this task can be split among people very easily. The key is to be very careful as if you make a mistake somewhere, it can really throw you off. But overall, it is actually quite a nice puzzle.

Answer 4

This might be a bit "lateral" answer, and maybe one with assumptions, but:

Having no answer that satisfies the conditions at this site after 17 hours have passed means it is in no way a fair assignment for any non-insanely-genius sixth grader.

The "this site" is an important part; you will regularly see insanely genius answers around here.