8
$\begingroup$

These four ellipses represent four sets and all the possible ways they can intersect (a Venn diagram, in other words). There are 8 regions inside each ellipse, and 15 regions altogether.

Is it possible to assign the numbers 1 to 15 to the fifteen regions so that the sum of the numbers in each ellipse is the same?

enter image description here

$\endgroup$
10
$\begingroup$

Here is a method for constructing a solution without the use of a computer.

[EDIT: This generalises to any even number of sets, but not to odd numbers. See the edit at the end for a different method that I think will work for any number of sets.]

Associate the first four powers of $2$ with the ellipses, i.e. label them $1$, $2$, $4$, and $8$. Then for each region, give it the number that is the sum of all the ellipse numbers it lies in.

While this assigns the numbers $1$ to $15$ to the regions inside the ellipses, the ellipses don't all add up to the same amount. This is because of that one bit that all the regions within an ellipse share.

To fix this problem, change every number with even bit parity to its complement, i.e. for every region that belongs to exactly $2$ or $4$ ellipses change its number to 15 minus that number. This changes four numbers in each ellipse, in such a way that each bit is used in exactly half the numbers in every ellipse. This gives the following picture:

enter image description here

Every ellipse adds up the the same amount, namely $60 = 4(1+2+4+8)$. Unfortunately the region that was $15$ became $0$, so the regions are now numbered 0 to 14. So all that is left to do is to add 1 to all the numbers to get the following valid solution where each ellipse adds to $68$:

enter image description here

$1+2+7+8+11+12+13+14=68\\1+3+6+8+10+12+13+15=68\\1+4+5+8+10+11+14+15=68\\1+4+6+7+9+12+14+15=68$

EDIT:
Here is a different method that I believe generalises to any number of sets. I will use 5 sets in this description.

Label the sets A,B,C,D,E.
Pick any region, and calculate the number of that region as follows:

1. Start with zero.
2. If the region lies in an odd number of the sets A,B,C,D,E, then add $2^4=16$.
3. If the region lies in an odd number of the sets A,B,C,D, then add $2^3=8$.
4. If the region lies in an odd number of the sets A,B,C, then add $2^2=4$.
5. If the region lies in an odd number of the sets A,B, then add $2^1=2$.
6. If the region lies in an odd number of the sets A,C, then add $2^0=1$.
The number you end up with is the number for that region.

Put differently, if a,b,c,d,e are variables which are $1$ if the region lies in a particular set and $0$ otherwise, then the region is given a binary number where the bits are (a^b^c^d^e), (a^b^c^d), (a^b^c), (a^b), (a^c) where the ^ symbol indicates the exclusive or (XOR) operation.

The order of the bits does not matter. I think you are even free to use any XOR expressions of the variables, as long as they are linearly independent and contain at least one XOR operation.

$\endgroup$
  • 2
    $\begingroup$ I assume this procedure can be generalized for Venn diagrams with any number of sets. Am I correct? Five sets in particular? $\endgroup$ – Bernardo Recamán Santos Nov 26 '18 at 0:04
  • 1
    $\begingroup$ @BernardoRecamánSantos: I think it only works for an even number of sets, unfortunately. $\endgroup$ – Jaap Scherphuis Nov 26 '18 at 5:43
  • 1
    $\begingroup$ @BernardoRecamánSantos I have added a different method that I think generalises to any number of sets. $\endgroup$ – Jaap Scherphuis Nov 26 '18 at 9:36
4
$\begingroup$

Computational Solution

Diagram

I only wanted to do the math if I had to, so I made a computer program to solve this problem written in C (view it on GitHub here):

How It Works

Each section is identified and placed in an array based on their letter's alphabetical index. The program then uses a brute-force approach. It works how you would expect, it cycles through every possible permutation and outputs a solution if the sums of each set are equal. You can view the output here.

Example solution

As seen in this diagram a solution is given by the following array in the alphabetical form:

[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O]

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

First Eclipse Sum

A + B + C + D + E + F + G + H = 10 + 9 + 11 + 13 + 6 + 8 + 5 + 1 = 63

Second Eclipse Sum

I + J + M + B + C + E + H + N = 3 + 7 + 12 + 9 + 11 + 6 + 1 + 14 = 63

Third Eclipse Sum

K + L + J + M + C + E + F + D = 4 + 2 + 7 + 12 + 11 + 6 + 8 + 13 = 63

Fourth Eclipse Sum

L + O + M + E + N + H + G + F = 2 + 15 + 12 + 6 + 14 + 1 + 5 + 8 = 63

Other Solutions

I ended up finding many solutions, here are a few in the same alphabetical form:

[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O]

Example 1:

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

Example 2:

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

Example 3:

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

Conclusion

There are many solutions based on my code. If you want to see all of them just compile and run the code linked at the top of this post. Or view the linked youtube video showing a small amount of the many there are. So it is possible and there are many solutions, not just one - given that my code is correct.

$\endgroup$
  • $\begingroup$ Nice! I was running some code too but gave up after it crashed. $\endgroup$ – Hugh Nov 25 '18 at 19:35
  • $\begingroup$ @W.Ambrozic: Of your solutions, which has the largest magic sum, and which the least? $\endgroup$ – Bernardo Recamán Santos Nov 28 '18 at 17:00
  • 1
    $\begingroup$ @BernardoRecamánSantos Given that I was using brute force to find all permutations of the 15 values, finding all solutions would take days; however, I recently optimized my code, and if it worked it should have looked at every permutation while checking for a maximum and minimum sum. So far I got a maximum sum of 77 with the solution array:[4,5,14,6,15,10,12,11,3,9,2,8,13,7,1], and a minimum sum of 51 with the solution array:[12,7,3,8,1,5,13,2,15,10,14,6,4,9,11] (in the form mentioned in my answer). I'll post my results when I have time to make sure my optimization did not skip any solutions. $\endgroup$ – W.Ambrozic Nov 30 '18 at 2:47
  • $\begingroup$ @W.Ambrozic: Fascinating stuff! $\endgroup$ – Bernardo Recamán Santos Nov 30 '18 at 2:53

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.