# 2012 Pascal Contest - Question 24



Use the variables $q, r, s, t, u, v, w, x, y$ to denote the values in all nine circles.



Let $C$ denote the sum of the three integers along each line. 
The following four equations hold.

$$
\begin{align}
q + r + s &= C \\
s + t + u &= C \\
u + v + w &= C \\
w + x + y &= C
\end{align}
$$

We are going to do some arithmetic, but the values $2012, 2013, \dots, 2020$ are somewhat large.
However, we can solve the problem using reduced values $q', r', \dots, y'$ and then convert that answer to the solution of the original problem.
Observe that if we reduce the nine consecutive integers each by the same amount, 
say $M$, so 

$$
\begin{align}
q' &= q - M \\
r' &= r - M \\
   &\vdots \\
y' &= y - M
\end{align}
$$

then the reduced integers are still consecutive and their sums along the four lines, will still be equal, say $C'$, although now this constant will be reduced by $3M$
compared to $C$. 
For example, consider the line formed by $q', r', s'$:

$$
\begin{split}
C'  &= q' + r' + s' \\
    &= q - M + r - M + s - M \\
    &= q + r + s - 3M \\
    &= C - 3M
\end{split}
$$

and similarly for the other three lines.

Take $M$ to be the average value of the original integers:

$$
M = (2012 + 2020)/2 = 2016
$$

With $M = 2016$, the reduced integers are $-4, -3, -2, -1, 0, 1, 2, 3, 4$.
Note that the sum of these values is $0$.
Therefore any arrangement of these integers also sums to $0$:

$$
q' + r' + s' + t' + u' + v' + w' + x' + y' = 0
$$

The line sum equations in terms of the reduced variables are:

$$
\begin{align}
q' + r' + s' &= C' \\
s' + t' + u' &= C' \\
u' + v' + w' &= C' \\
w' + x' + y' &= C'
\end{align}
$$

Add these four equations together.

$$
\begin{split}
4C' &= q' + r' + s' + s' + t' + u' + u' + v' + w' + w' + x' + y' \\
    &= (q' + r' + s' + t' + u' + v' + w' + x' + y') + s' + u' + w' \\
    &= s' + u' + w'
\end{split}
$$

Therefore in any solution, $s' + u' + w'$ must be a multiple of $4$.

The line sum $C'$ takes its smallest value when $s', u', w'$ are as negative as possible, while still summing to a multiple of $4$.
The smallest multiple of $4$ that can be formed from the reduced integers occurs for the values $-4, -3, -1$.
In this case we have:

$$
4C' = -4 + -3 + -1 = -8
$$

Therefore $C' = -2$, which may or may not actually occur for some solution.

Now try to find solutions that have $C' = -2$.

Note that the problem has left-right symmetry in the sense that if we have one solution
we can find another one by interchanging the values under left-right reflection by a mirror through
$u'$. Therefore we can just look for solutions with $s' < w'$ since we obtain the other
solution by reflection.

Also note that, given a solution, we can swap $q'$ with $r'$ or $x'$ with $y'$
to get another solution. So just look for solutions with $q' < r'$ and $x' < y'$.

## Case 1: $u' = -4, s' = -3, w' = -1$

This case is impossible since

$$
\begin{split}
-2  &= s' + t' + u' \\
    &= -3 + t' + -4 \\
    &= -7 + t' \\
    &\implies t' = 5
\end{split}
$$

But $t' = 5$ is not allowed.

## Case 2: $u' = -3, s' = -4, w' = -1$

This case is also impossible for the same reason as Case 1.

## Case 3: $u' = -1, s' = -4, w' = -3$

Solve the line equations to find the other values.

Solve for $t' \in \{ -2, 0, 1, 2, 3, 4 \}$:

$$
\begin{split}
-2  &= s' + t' + u' \\
    &= -4 + t' + -1 \\
    &= -5 + t' \\
    &\implies t' = 3
\end{split}
$$

Solve for $v' \in \{ -2, 0, 1, 2, 4 \}$:

$$
\begin{split}
-2  &= u' + v' + w' \\
    &= -1 + v' + -3 \\
    &= -4 + v' \\
    &\implies v' = 2
\end{split}
$$

Solve for $q', r' \in \{ -2, 0, 1, 4 \}$ with $q' < r'$:

$$
\begin{split}
-2  &= q' + r' + s' \\
    &= q' + r' + -4 \\
    &\implies q' + r' = 2 \\
    &\implies q' = -2, r' = 4
\end{split}
$$

Solve for $x', y'\in \{ 0, 1 \}$ with $x' < y'$:

$$
\begin{split}
-2  &= w' + x' + y' \\
    &= -3 + x' + y' \\
    &\implies x' + y' = 1 \\
    &\implies x' = 0, y' = 1
\end{split}
$$

Therefore $u' = -1$ for the solutions that give the smallest value of $C'$. 

The solution to the original problem is therefore:

$$
\begin{split}
u   &= u' + M \\
    &= -1 + 2016 \\
    &= 2015
\end{split}
$$

## Python Solution

Let's now check the preceding solution by writing a Python program.
First let's try a brute force approach, namely we'll simply generate every possible arrangement of 
the nine consecutive integers, check the line sums, and keep the solutions.
The total number of arrangements of nine things is $9!$.
Let's see how big this number is using the built-in function `math.factorial`.


```python
import math

math.factorial(9)
```




    362880



We see that $9! = 362880$, which is not huge. We could easily store a list of that length in memory.

Python has a built-in function `itertools.permutaions`
to generate all permutations of a list.


```python
import itertools

list(itertools.permutations([2012, 2013, 2014]))
```




    [(2012, 2013, 2014),
     (2012, 2014, 2013),
     (2013, 2012, 2014),
     (2013, 2014, 2012),
     (2014, 2012, 2013),
     (2014, 2013, 2012)]



Next, let's define a function `isSolution` that detects permutations of nine integers that have the same sum along each of the four lines.


```python
def isSolution(t):
    C = t[0] + t[1] + t[2]

    if C != t[2] + t[3] + t[4]:
        return False

    if C != t[4] + t[5] + t[6]:
        return False
    
    return C == t[6] + t[7] + t[8]

non_solution1 = (-4, -3, -2, -1, 0, 1, 2, 3, 4)
print('non_solution1:', isSolution(non_solution1))

solution1 = (-2, 4, -4, 3, -1, 2, -3, 0, 1)
print('solution1:', isSolution(solution1))
```

    non_solution1: False
    solution1: True


We can generate the list of nine integers using the `range` function.


```python
list(range(2012, 2021))
```




    [2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020]




```python
solutions = [(t, t[0] + t[1] + t[2]) 
             for t in itertools.permutations(range(2012, 2021)) 
             if isSolution(t)]
len(solutions)
```




    96



Note that the number of solutions should be a muliple of 8 because of the symmetries of the problem. 
Given a solution, we can swap q and r, swap x and y, and reflect left to right to get other solutions. Thus there are 2 * 2 * 2 = 8 solutions that are related to eachother
by the symmetries.


```python
len(solutions) % 8
```




    0



Next, find the minimum value of $C$


```python
C_min = min([C for (t, C) in solutions])
C_min
```




    6046




```python
solutions[0]
```




    ((2012, 2018, 2017, 2016, 2014, 2020, 2013, 2015, 2019), 6047)




```python

```

Now select all the solutions that attain the minimum.


```python
min_solutions = [t for (t, C) in solutions if C == C_min]
len(min_solutions)
```




    8




```python
print(min_solutions)
```

    [(2014, 2020, 2012, 2019, 2015, 2018, 2013, 2016, 2017), (2014, 2020, 2012, 2019, 2015, 2018, 2013, 2017, 2016), (2016, 2017, 2013, 2018, 2015, 2019, 2012, 2014, 2020), (2016, 2017, 2013, 2018, 2015, 2019, 2012, 2020, 2014), (2017, 2016, 2013, 2018, 2015, 2019, 2012, 2014, 2020), (2017, 2016, 2013, 2018, 2015, 2019, 2012, 2020, 2014), (2020, 2014, 2012, 2019, 2015, 2018, 2013, 2016, 2017), (2020, 2014, 2012, 2019, 2015, 2018, 2013, 2017, 2016)]


Finally, get the value of $u$ for each of these solutions.


```python
min_us = [t[4] for t in min_solutions]
print(min_us)
```

    [2015, 2015, 2015, 2015, 2015, 2015, 2015, 2015]


We can eliminate the duplicates by converting this list to a set.


```python
set(min_us)
```




    {2015}



bd2853f527ade45ed48a0c6d90babea2095ab2b5
ipynb
Jupyter Notebook
Meeting Notes/2020/2020-06-13/2012-pascal-contest-q24.ipynb
agryman/sean
11baf69c6eb9308266126bf9c8b1c67c6fd33afc
MIT
2020-03-28T18:17:52.000Z
2020-03-28T18:17:52.000Z
Meeting Notes/2020/2020-06-13/2012-pascal-contest-q24.ipynb
agryman/sean
11baf69c6eb9308266126bf9c8b1c67c6fd33afc
MIT
2022-01-21T21:33:00.000Z
2022-01-21T21:33:00.000Z
Meeting Notes/2020/2020-06-13/2012-pascal-contest-q24.ipynb
agryman/sean
11baf69c6eb9308266126bf9c8b1c67c6fd33afc
MIT
Qwen/Qwen-72B
1. YES
2. YES