10
$\begingroup$

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 method, if one exists.

$\endgroup$
  • 1
    $\begingroup$ Do "extraordinary intuition" or "consulting an oracle" count as "sheer luck"? :) $\endgroup$ – noedne Apr 3 at 20:06
  • 2
    $\begingroup$ Not even close to a solution, but I would probably start by converting every number to its offset from 40, then trying to sum every line to 0. As long as you're comfortable with some negatives (I forget if I was in 6th grade) this makes the head-math easier. $\endgroup$ – TwoBitOperation Apr 3 at 20:07
  • $\begingroup$ @TwoBitOperation Don't you have a calculator anyway? $\endgroup$ – noedne Apr 3 at 20:08
  • $\begingroup$ True, but I think you'd be able to rule out some permutations faster without checking on the calculator. Maybe that's just how my brain works though. $\endgroup$ – TwoBitOperation Apr 3 at 20:10
  • 2
    $\begingroup$ Heh. My code originally kept finding no solutions because I hadn't realized the provided diagonals don't actually add up to 200 (yet another reason why this is not a magic square) but my code was checking diagonal sums and rejecting everything. This problem found no end of ways to annoy me. :) $\endgroup$ – Rubio Apr 3 at 22:47
10
$\begingroup$

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.

enter image description here

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.
enter image description here

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

Page 3

enter image description here

Page 4


enter image description here

Page 5


enter image description here

$\endgroup$
  • 1
    $\begingroup$ Holy cats. That’s impressive beyond words. I think my “real” question can safely be answered that this is not even remotely fair to ask 6th graders, but I am - once again - amazed at the people in this community and their ability to solve the seemingly unsolvable. Thank you! $\endgroup$ – Rubio Apr 5 at 10:03
  • $\begingroup$ @Rubio, thanks. I agree with you - it is too much as a homework for a 6th grader. $\endgroup$ – ppgdev Apr 5 at 16:27
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ bit.do/27-2x-xx-xx-36 (substituting appropriate digits for the xs) is my thrown-together solver, on tio.run. Our solutions, unsurprisingly, agree. $\endgroup$ – Rubio Apr 3 at 22:19
  • $\begingroup$ I found four solutions because of the duplicated $66$ but of course only 2 distinct solutions. Takes less than 0.5 seconds. $\endgroup$ – Weather Vane Apr 3 at 22:23
  • $\begingroup$ Edit: added a remark about the main problem. $\endgroup$ – Weather Vane Apr 4 at 18:26
  • $\begingroup$ ...with which I fully agree. Having said that, this community continually surprises me with ingenuity and insight into solving what seem to me to be unsolvable problems. I’m holding out (increasingly forlorn) hope that someone can offer such a “trick”. $\endgroup$ – Rubio Apr 4 at 18:32
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Each triplet permutes to 6 arrangements. Most choices for e.g. row 1 will eliminate at least one option from a different row, reducing the remaining permutations to check for other rows once a particular row 1 triplet has been chosen for evaluation. But the search space is still pretty enormous - I’d guess between 100000 and 200000 permutations - so still fairly untenable for paper and pencil bookkeeping. I wonder if a second pass, determining which triplets can work for given columns, might further reduce the search space. $\endgroup$ – Rubio Apr 4 at 16:06
  • $\begingroup$ See my update - by looking at column 1, we can narrow down the options further. Overall, it is time consuming, but a determined schoolkid should be able to complete it. $\endgroup$ – rinspy Apr 5 at 8:21
  • 1
    $\begingroup$ I think that you are right, with enough direction to 6th graders to get them to realize the computational complexities here and how to go about looking for ways to reduce the search space, this could be a pretty cool teaching exercise. Unfortunately it was just given as homework with no guidance, so it would be unlikely that someone without an awareness of this type of approach would stumble on such a strategy on their own, let alone stumble on THIS fairly well-optimized strategy. Solving within the search space you’ve winnowed it down to? Possible. Devising that unaided? Totally unfair. :) $\endgroup$ – Rubio Apr 5 at 10:12
  • $\begingroup$ Agreed, this should be a completely optional exercise for the kids that want to challenge themselves and not a regular homework assignment. $\endgroup$ – rinspy Apr 5 at 10:22
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.