Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Note: Not looking for the solution - just help on how to solve.

Here is the math puzzle:

enter image description here

Is there a mathematical model/method that I could employ to solve this?

Right now my only answer is to use Excel and trial-and-error my way to the solution.

share|improve this question
1  
You can set this up as a binary programming program, by assigning each candy four variables, one per calorie amount. –  user7530 Dec 7 '11 at 22:04
1  
There's a cute parity trick you can use to show that there must be at least one row and at least one column that consists only with calories 20 and 60. –  Thomas Andrews Dec 7 '11 at 22:15
1  
So, that means that each row and each column must contain at least one $20$ or $60$ calorie candy. What must be the other calories of candies in the row and column with the zero-calorie candy? –  Thomas Andrews Dec 7 '11 at 22:43

2 Answers 2

up vote 2 down vote accepted

First, divide everything by 20 to make your life easier. Then you are reduced to filling in your grid with 3 1's, 2 2's, 7 3's, and 3 4's so that every row, column and diagonal adds up to 10. (You still have a 0 where the black candy is, of course.)

Now, if you look mod 3 (i.e. consider remainders when dividing by 3), you'll see that in each row, column and diagonal, the number of 1's and 4's has to be exactly one more than the number of 2's. This is a pretty strong constraint since you have so few of these numbers available. You should also use the fact that the row and the column containing the 0 each must have one 4 and two 3's in it.

With this, I was able to find two different solutions via trial and error. I haven't bothered to determine if these are all the solutions, which I would guess is what the puzzle is asking for?

John M: If you request it, I'll post my two solutions in the comments if you're still stuck or want to check your solutions against mine.

share|improve this answer
    
(This is a laaaate question), how do you consider the remainders? –  josh Nov 5 '12 at 3:02
1  
In each row, column or diagonal, the four numbers must add up to 10. Just keep track of the remainders when you divide by 3 and add them up. Since the four numbers add up to 10, which leaves a remainder of 1 when you divide by 3, the four remainders must add up to a number with the same remainder (i.e. 1, 4, or 7). –  Michael Joyce Nov 5 '12 at 4:18
    
Got it, thanks. I misunderstood you at first. –  josh Nov 6 '12 at 11:56

You can set this up as a binary programming problem. Let $a_{i,j}$ be 1 if the candy at $(i,j)$ has 20 calories, 0 otherwise, and likewise for $b_{i,j}, c_{i,j}, d_{i,j}$ and 40, 60, and 80 calories, respectively. You then have three sets of equations:

  1. Each candy can only be of one type (except the black candy, which is of no type): $$ a_{i,j} + b_{i,j} + c_{i.j} + d_{i,j} = \begin{cases}1, & (i,j) \neq (4,3)\\ 0, &(i,j) = (4,3).\end{cases}$$

  2. The rows, columns, and diagonals must add up to the right number of calories: $$\begin{align*} \sum_k (20a_{i,k} + 40b_{i,k} + 60c_{i,k} + 80d_{i,k}) &= 200\\ \sum_k (20a_{k,j} + 40b_{k,j} + 60c_{k,j} + 80d_{k,j}) &= 200\\ \sum_k (20a_{k,k} + 40b_{k,k} + 60c_{k,k} + 80d_{k,k}) &= 200\\ \sum_k (20a_{k,5-k} + 40b_{k,5-k} + 60c_{k,5-k} + 80d_{k,5-k}) &= 200.\end{align*}$$

  3. The total number of each type of candy is constrained: $$\begin{align*} \sum a_{i,j} &= 3\\ \sum b_{i,j} &= 2\\ \sum c_{i,j} &= 7\\ \sum d_{i,j} &= 3.\end{align*}$$

That's how I would model it, at least. Actually solving this linear program likely requires an NP-hard algorithm.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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