The France Public Holiday's Distance Grid

Question

French Public Holidays

We consider the following rules that apply to the 11 French public holidays :

1. New Year's Day : 1st of January
2. Easter Monday : Monday following Easter Sunday which is the next Sunday after the first full moon beginning from Spring's Equinox (approximately 21 march).
3. Labour Day : 1st of May
4. Victory in Europe Day : 8th of May
5. Ascension Day : 39 days after Easter Sunday
6. Whit Monday : 50 days after Easter Sunday
7. Bastille Day : 14th of July
8. Assumption of Mary to Heaven : 15th of August
9. All Saints' Day : 1st of November
10. Armistice Day : 11th of November
11. Christmas Day : 25th of December

Date distance

We here define a pseudo-metric on dates, that we will now on call a distance to simplify for everyone $d:D\times D \longrightarrow \mathbb Z$ where:

• $D$ is the set of all the possible dates.
• $D=\{aaaa/mm/dd\}$
• $aaaa$ is a year, typically $2020$ or $1996$
• $mm$ is a month, typically $04$ for April
• $dd$ is a day
• $d$ will be closely linked to the French Public Holidays in the sense that it counts the number of French Public Holidays between two dates.
• For instance: $d(2020/12/24, 2020/12/26) = 1$ because there is exactly one public holidays between those two dates: Christmas Day.
• Note that $d(2020/12/25,2021/01/01) = 0$ (both bounds are excluded)
• A last example is $d(2020/04/10, 2020/05/10) = 3$

Puzzle

Let us suppose you have $12$ dates to define $\forall (i,j) \in \{1,2,3\}\times \{1,2,3,4\},\quad d_{ij}\in D$. With the constraint that $d_{ij} \ge 2005/11/25$ (this is a symbolic and special day for me) and $d_{ij} \le$ the day this puzzle is posted.

We thus define :

• $r_i = d(d_{i1}, d_{i2}) + d(d_{i2}, d_{i3}) + d(d_{i3}, d_{i4})$
• $\displaystyle c_j = d(\min_i{d_{ij}}, \max_i{d_{ij}})$

$$\begin{array}{rrrr|r} c_1 & c_2 & c_3 & c_4 & \\ \hline d_{11} & d_{12} & d_{13} & d_{14} & r_{1} \\ d_{21} & d_{22} & d_{23} & d_{24} & r_{2} \\ d_{31} & d_{32} & d_{33} & d_{34} & r_{3}\\ \end{array}$$

This calculation puzzle is to compute

$\max z = r_1 + r_2 + r_3 - c_1 - c_2 - c_3 - c_4 + w$

$\displaystyle w = \sum_{i=1}^3\sum_{i'=1, i'\neq i}^3\sum_{j=1}^4\sum_{j'=1, j'\neq j}^4 d(d_{ij},d_{i'j'})$

with all the previous constraint and the final one that:

• $d_{ij} \neq d_{i'j'} \text{ if } i \neq i' \text{ or } j \neq j'$ (all $d_{ij}$ are unique)

Computers are allowed :)

Answer 1

I think that

$\max z = 8892$

This can be achieved with the following choices

$(d_{11}, d_{12}, d_{13}, d_{14})$ = (2005/11/25, 2020/04/05, 2005/11/28, 2020/04/08)
$(d_{21}, d_{22}, d_{23}, d_{24})$ = (2005/11/26, 2020/04/06, 2005/11/29, 2020/04/09)
$(d_{31}, d_{32}, d_{33}, d_{34})$ = (2005/11/27, 2020/04/07, 2005/11/30, 2020/04/10)

Reasoning

First we assume that no $d_{ij}$ coincides with a holiday, we can only lose from the value of $z$ by doing so. Also, we can set each $c_j = 0$ as the distances between dates in the same column only contribute negatively to $z$. For convenience we will pick the dates in each column to be consecutive.
Under these assumptions $z$ equivalent to $$ 3 \left[ 5d(d_{11}, d_{12}) + 5d(d_{12}, d_{13}) + 5d(d_{13}, d_{14}) + 4d(d_{11}, d_{13}) + 4d(d_{11}, d_{14}) + 4d(d_{12}, d_{14} )\right] $$ This is a slightly asymmetric expression so it makes most sense to maximise the parts with coefficient $5$. This maximum is $156$ in each case, achieved by putting dates at opposite ends of the date range. Then, we also get the additional $d(d_{11},d_{14})=156$ term for free (although the other terms are zero).
This makes the maximum at $3 \times 19 \times 156 = 8892$