2
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ Isn't $d(2020/04/10, 2020/05/10) = 3$? Easter Monday, 1/5, 8/5. $\endgroup$ – Culver Kwan Apr 10 at 7:44
  • $\begingroup$ @CulverKwan Oh yeah! You're 100% right, thanks! $\endgroup$ – JKHA Apr 10 at 7:47
1
$\begingroup$

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$

| improve this answer | |
$\endgroup$
  • $\begingroup$ I think your objective is wrong, especially for the term $w$! $w$ is the sum of all the distances between each couple of $d_{ij}$ and $d_{i'j'}$, those being different. But I +1 you anyway because there are great ideas in you answer $\endgroup$ – JKHA Apr 13 at 18:45
  • $\begingroup$ @JKHA Your last comment is incorrect. w is the sum of all distances between elements which are in a different row and column to each other. Check your summation again, both i' and j' are different to i and j. $\endgroup$ – hexomino Apr 14 at 15:30
  • $\begingroup$ Oh indeed! I wrote something different than I wanted. Well, I'm not changing my puzzle now it has an answer, congrats ;) $\endgroup$ – JKHA Apr 15 at 0:08

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.