# Brute force circle problem

Question:

The maximum number of individual regions formed by three lines dividing a circle is seven.  The circle contains an ant colony and  each region contains between one and seven ants.  Can you place seven groups of ants in the seven regions so that for each of the lines, the total number of ants on either side are all the same?  How many solutions can you find?

Source:-This is from Ivan Moscovich's latest puzzle book Leonardo's Mirror & Other Puzzles

Note:

This is a brute force problem and I have no idea what's the technique or algorithm to solve these kind of problems and due to this I couldn't share my approach towards this problem.

• Is this question too complicated for mathematics stackexchange?Should I ask it on some other site?May be MathOverflow. – user517784 Feb 4 '18 at 4:48
• MO is for research level mathematics, which is probably not the level of this problem. – qwr Feb 4 '18 at 6:57
• @qwr OK I will keep that in mind. – user517784 Feb 4 '18 at 6:58

## 2 Answers

If the number of ants in region $i$ is $a_i$ for $0 \leq i \leq 6$, with the regions arranged thus so that they satisfy the equations

\begin{align} a_0 + a_1 + a_2 &= a_3 + a_4 + a_5 + a_6 \\ a_1 + a_2 + a_3 + a_6 &= a_0 + a_4 + a_5 \\ a_0 + a_1 + a_5 + a_6 &= a_2 + a_3 + a_4 \enspace, \end{align} then a solution is given by:

$$2, 1, 2, 1, 2, 1, 1 \enspace.$$

Other solutions are obtained adding $1$ to each of $a_0-a_5$ until the limit of $7$ is reached. For instance, $3, 2, 3, 2, 3, 2, 1$ is another solution. This process yields $6$ solutions, the last of which is

$$7, 6, 7, 6, 7, 6, 1 \enspace.$$

Another family of solutions, $5$ in total, are obtained starting from $3, 1, 3, 1, 3, 1, 2$. Proceeding this way, we reach $7, 1, 7, 1, 7, 1, 6$.

Overall, we have $1 + 2 + 3 + 4 + 5 + 6 = 21$ solutions with rotational symmetry. The total number of solutions of any shape is $441$. One of them is

$$6, 5, 5, 4, 7, 3, 2 \enspace.$$

How do we get the total of $441$? Careful Gaussian elimination applied to the three equations yields:

\begin{align} a_0 &= a_3 + a_6 \\ a_2 &= a_5 + a_6 \\ a_4 &= a_1 + a_6 \enspace. \end{align} (For instance, subtract the first equation from the other two and simplify. Then subtract both simplified equations from the first.) Since Gaussian elimination preserves the set of solutions, all we need to do is to enumerate the integer solutions to the simplified equations, which is rather easy. It's clear that $1 \leq a_6 \leq 6$. (For instance, $a_3$ is at least $1$ and $a_0$ is at most $7$.) For each of the six choices of $a_6$ there are $(7-a_6)^3$ ways to choose $a_3$, $a_5$, and $a_1$, at which point $a_0$, $a_2$, and $a_4$ are fixed. Finally,

$$\sum_{1 \leq n \leq 6} n^3 = \frac{6^2 \cdot 7^2}{4} = 441 \enspace.$$

Some of the $441$ solutions are obtained by rotating or mirroring other solutions. Imposing the constraint $a_3 \leq a_5 \leq a_1$ (equivalently, $a_0 \geq a_2 \geq a_4$) removes these "duplicates." The number of unique solutions is then given by

$$\sum_{1 \leq i_6 \leq 6} \,\, \sum_{i_6 \leq i_3 \leq 6} \,\, \sum_{1 \leq i_5 \leq 7 - i_3} \!\! i_5 = \frac{6 \cdot 7 \cdot 8 \cdot 9}{24} = 126 \enspace.$$

We can get to the same result by application of Burnside's lemma. The symmetry group is the one of the equilateral triangle, consisting of the identity, two rotations ($120^{\circ}$ and $240^{\circ}$), and three flips, one for each vertex of the inner triangle. The solutions fixed under each symmetry are:

• $\sum_{1 \leq n \leq 6} n^3 = 441$ for the identity;
• $\sum_{1 \leq n \leq 6} n^2 = 91$ for each flip;
• $\sum_{1 \leq n \leq 6} n \,\, = 21$ for each rotation.

The number of orbits is then

$$\frac{441 + 3 \cdot 91 + 2 \cdot 21}{1+3+2} = 126 \enspace.$$

A program I wrote, which lists all solutions, with or without symmetry reduction, confirms these numbers.

• Absolutely amazing!!! ☺️ – user517784 Feb 4 '18 at 8:10

Well here's one solution: If you draw the three lines you will get 6 outer regions and one central triangle. Put one ant in the center and one ant in each region sharing a side with the center, and 2 ants everywhere else. Then every line has 5 ants on each side.

In general you would just label the outer regions $a,b,c,d,e,f$ and inner region $g$ and count solutions to

$$f+a+b+g=c+d+e$$ $$b+c+d+g=e+f+a$$ $$d+e+f+g=a+b+c$$

• Wouldn't your solution ($2$ everywhere except for $1$ in the center) give an imbalance of $1$ between the two sides of each line? – Fabio Somenzi Feb 4 '18 at 5:38
• I meant 1 ant in the center and regions sharing a side with the center and 2 ants everywhere else. thanks for pointing it out – Akababa Feb 4 '18 at 5:41