That's A Lot Of Equations

Logic Level 3

$\begin{array} { c c c c c } \square & + & \square & = & \square \\ \square & + & \square & = & \square \\ \square & + & \square & = & \square \\ \square & + & \square & = & \square \\ \square & + & \square & = & \square \\ \square & + & \square & = & \square \\ \end{array}$ Is it possible to fill the above squares with all the integers from 1 to 18 (using each number only once), such that each equation holds true?

For example, if we had only 4 rows and 12 numbers from 1 to 12 available, we could do the following:
$\begin{array} { c c c c c } 1 &+& 6 & =& 7 \\ 2 &+& 10 & =& 12 \\ 3 &+& 8 & =& 11 \\ 4 &+& 5 & =& 9. \end{array}$

Yes No

3 solutions

Brian Charlesworth
Feb 3, 2017

For this to be possible, the sum $S$ of the 12 boxes on the LHS of the equations must equal the sum of the 6 boxes on the RHS of the equations. So the sum of all 18 boxes must be $2S$ , i.e., an even number.

But since the 18 boxes must be filled by the integers $1$ to $18$ , their sum must be

$\displaystyle\sum_{n=1}^{18} n = \dfrac{18 \times 19}{2} = 9 \times 19 = 171$ ,

which is odd, and thus cannot equal $2S$ for any integer $S$ . The answer is therefore $\boxed{No}$ .

Moderator note:

Great discussion in the comments below. To summarize, we can fill the $n$ equations with integers from 1 to $3n$ if and only if $n \equiv 0, 1 \pmod{4}$ .

Try your hand at proving this, before reading further.
To show that this is a necessary condition, we generalize Brian's argument.
To show that this is a sufficient condition, we have to find a construction, which is what Ben did.

You've shown that having an even sum is a necessary condition. Is it also a sufficient condition?

IE Since $\sum_{i=1}^{3n} = \frac{ 1}{2} (3n)(3n+1)$ , for the sum to be even we either have $3n \equiv 0 \pmod{4}$ or $3n+1 \equiv 0 \pmod{4}$ , which gives us $n \equiv 0, 1 \pmod{4}$ .

For $n = 1$ , we have $1 + 2 = 3$ .
For $n = 4$ , we have the example given in the problem.
I've also verified that $n = 5, 8$ can work.

So, for small values, this seems to work. However, I had to do some trial and error to determine the equations, and don't see a quick generalization. Thoughts?

Calvin Lin Staff - 4 years, 4 months ago

I think I have a pattern that will work for 0 mod 4, but it is not very elegant. I will keep thinking about this and if I can't come up with something nicer I'll just post what I've got. (EDIT: Oh, it may also work for the 1 mod 4 case...)

Ben Reiniger - 4 years, 4 months ago

Great! That's exciting :)

Calvin Lin Staff - 4 years, 4 months ago

@Calvin Lin – The picture works for both cases, but I think putting it into symbols will not illuminate things. So here is just for n=0 mod 4, and 1 mod 4 is "similar". Put n=4k.

$\begin{array}{rrrrr} 1&+&5k&=&5k+1\\\hline 2&+&6k&=&6k+2&\\4&+&6k-1&=&6k+3\\&&&\vdots&\\2k-2&+&5k+2&=&7k\\\hline 2k+2&+&5k-1&=&7k+1\\2k+4&+&5k-2&=&7k+2\\&&&\vdots&\\4k-2&+&4k+1&=&8k-1\\\hline 2k&+&8k&=&10k\\\hline 4k&+&6k+1&=&10k+1\\\hline 3&+&10k-1&=&10k+2\\5&+&10k-2&=&10k+3\\&&&\vdots&\\4k-1&+&8k+1&=&12k.\\ \end{array}$

Ben Reiniger - 4 years, 4 months ago

@Ben Reiniger – The pairing / pattern is great! Thanks for shedding light on this :)

Calvin Lin Staff - 4 years, 4 months ago

@Calvin Lin – Huh, evidently I should have recognized this. This is equivalent to the existence of Skolem sequences!

Ben Reiniger - 3 years, 5 months ago

@Ben Reiniger – I quite didn't understand for n=4k, how you paired the summands? Would it be possible for you to explain in detail?

Vighnesh Raut - 4 years, 1 month ago

@Vighnesh Raut – Let's take k = 10 :

1 + 50 = 51, 2 + 60 = 62, 4 + 59 = 63, 6 + 58 = 64, 8 + 57 = 65, 10 + 56 = 66, 12 + 55 = 67, 14 + 54 = 68, 16 + 53 = 69, 18 + 52 = 70, 22 + 49 = 71, 24 + 48 = 72, 26 + 47 = 73, 28 + 46 = 74, 30 + 45 = 75, 32 + 44 = 76, 34 + 43 = 77, 36 + 42 = 78, 38 + 41 = 79, 20 + 80 = 100, 40 + 61 = 101, 3 + 99 = 102, 5 + 98 = 103, 7 + 97 = 104, 9 + 96 = 105, 11 + 95 = 106, 13 + 94 = 107, 15 + 93 = 108, 17 + 92 = 109, 19 + 91 = 110, 21 + 90 = 111, 23 + 89 = 112, 25 + 88 = 113, 27 + 87 = 114, 29 + 86 = 115, 31 + 85 = 116, 33 + 84 = 117, 35 + 83 = 118, 37 + 82 = 119, 39 + 81 = 120.

Is this detailed enough, Vighnesh?

C . - 2 years, 9 months ago

how have you gotten 18*19/2? (I am just self learning sums. Would appreciate a link or explanation.)

Erfan Huq - 4 years, 4 months ago

Write out the sum of consecutive integers forwards and backwards as follows:

$S = 1 + 2 + 3 + ..... + (n - 2) + (n - 1) + n$

$S = n + (n - 1) + (n - 2) + ..... + 3 + 2 + 1$

Now add the corresponding terms in each of these sums of $n$ elements. For example, the first corresponding pair sum is $1 + n$ , the next is $2 + (n - 1) = n + 1$ , the next is $3 + (n - 2) = n + 1$ , and so on down the line. Each of these $n$ pairs sum to $n + 1$ , so we end up finding that

$2S = n(n + 1) \Longrightarrow S = \dfrac{n(n + 1)}{2}$ .

You also may have learned the sum formula for an arithmetic progression with $n$ terms, first term $a$ and common difference $d$ , namely

$S_{n} = \dfrac{n}{2}(2a + (n - 1)d)$ .

By plugging in $a = 1, d = 1$ we get $S_{n} = \dfrac{n(n + 1)}{2}$ as before.

Brian Charlesworth - 4 years, 4 months ago

How can you know that the sum of all 18 boxes must be $2S$ ?

Fidel Simanjuntak - 4 years, 4 months ago

Since for each of the 6 individual equations the sum of the 2 boxes on the left is equal to the sum of the 1 box on the right, the sum of all 12 of the boxes on the left must equal the sum of all 6 boxes on the right. So if the sum of all 12 boxes on the left is $S$ , then the sum of all 6 boxes on the right must be $S$ as well, making the sum of all 18 boxes $2S$ .

Brian Charlesworth - 4 years, 4 months ago

Thank you. Nice explanation and solution.

Fidel Simanjuntak - 4 years, 4 months ago

(mod 2) the only possibilities are:

odd+odd=even
odd+even=odd
even+odd=odd
even+even=even

In each row either two, or no odd numbers must occur. So the total number of odd numbers will be even. However, there are 9 odd numbrrs in the range 1-18.

K T - 1 year, 9 months ago

Novak Radivojević
Feb 22, 2017

There are 3 ways to fill squares in each equation depending on the parity of numbers used:

even + even = even - using 3 even numbers; odd + even = odd - using 1 even and 2 odd numbers; odd + odd = even - again, using 1 even and 2 odd numbers;

So, for each equation we need to use either no odd numbers at all, or two odd numbers, meaning that the we need to use odd numbers an even number of times :) However, there are 9 odd numbers from 1 to 18 which tells us that squares can't be filled this way.

Was going to propose the exact same solution! 👍🏻

Hayk Zayimtsyan - 4 years, 3 months ago

Atomsky Jahid
Feb 15, 2017

The solution Brian Charlesworth posted is an elegant one. My solution is not that good but, I'm gonna post it nonetheless.

The right hand side (RHS) contains 6 empty boxes. Let's assume $n$ numbers that appear in RHS are even. So, $6-n$ numbers are odd. The crucial fact is an even number can be written as a sum of either 2 even numbers or 2 odd numbers. On the other hand, odd numbers can be written as a sum of one even and one odd number.

Now, assume that $k$ even numbers on the RHS are written as a sum of two even numbers. So, the number of even numbers in those equations becomes $n+1 \times (6-n) +2 \times k=6+2k$ . Clearly $6+2k$ is even.

There are 9 even numbers from 1 to 18. (Or in other words, we have odd numbers of even numbers!) But, $6+2k \neq 9$ where $k \in \mathbb{N}$ and this is a contradiction. Therefore, the answer to this question is NO.

That's a nice observation!

The even-odd counting that you have is similar to the idea in Brian's solution. As you found, each equation must have an even number of odd terms, which in Brian's solution translates to "sum of terms in each equation is even".

Chung Kevin - 4 years, 3 months ago

Your solution is good too! My approach is similar to yours :)

Christopher Boo - 4 years, 3 months ago

That's A Lot Of Equations

3 solutions

Moderator note:

0 pending reports