20
$\begingroup$

I am submitting a very interesting problem from a French mathematical recreation site:

http://www.diophante.fr/problemes-par-themes/g-probabilites/g2-combinatoire-denombrements/1434-g248-le-billet-universel

This is a 10-year-old problem, and they gave me their consent to share it here (provided of course, that I cite the author of the problem: Michel Lafond). I used to spend time on this... The problem is still open (this is an optimization problem).


Let me define tickets and coupons: A ticket is a 3x3 square with a value on each square. The ticket value is the sum of all squares. From this square, we can extract a coupon, which basically is a polyomino, to pay any sum from 1 to the ticket value.

A valid ticket is a square from which we can extract coupons for all sums from 1 to the ticket value.

Example from original site, with a 3x3 ticket of value 90, allowing to pay any sum from 1 to 90:

We can show that this is a valid ticket (all sums from 1 to 90 can be paid with polyominos extracted from this ticket)

2 Questions Here:

  1. try to find a valid 3x3 ticket maximizing the possible sum we can pay (note that ALL values from 1 to ticket value must be possible) (Original question was: try to find a valid 3x3 ticket of value 100)
  1. try to find a valid 4x4 ticket maximizing the possible sum we can pay (Original question was for a 4x4 valid ticket of value 1000)
$\endgroup$
9
  • $\begingroup$ "try to find a 4x4 ticket": you mean a valid one? $\endgroup$
    – msh210
    Jun 27, 2022 at 0:15
  • 3
    $\begingroup$ A rough upper bound for the optimal solution is the number of polyominos. There are 2^9-1=511 ways to pick some subset of the 9 squares but of course a lot of these are not connected so the number polyominos is lower than that. Just saw that the linked page in French already computed that. There are 218 possible polyominos. $\endgroup$
    – quarague
    Jun 27, 2022 at 6:13
  • 4
    $\begingroup$ @quarague this upper bound is $218$ for $n=3$ and $11506$ for $n=4$: oeis.org/A059525 $\endgroup$
    – RobPratt
    Jun 27, 2022 at 6:15
  • 1
    $\begingroup$ ooh I like this problem! I can see myself spending months on this $\endgroup$ Jun 27, 2022 at 23:50
  • 4
    $\begingroup$ I wrote a simulated annealing algorithm that managed to find the best known value (165) three times. Each time the solution was identical to the one posted on the French site, so there is no point repeating it here. The 4x4 is much much harder. $\endgroup$ Jun 29, 2022 at 13:41

3 Answers 3

17
$\begingroup$

The previously best-known solution has score of 165, with the following grid:

$\begin{matrix} 3 & 1 & 16 \\ 2 & 8 & 7 \\ 70 & 26 & 32 \\ \end{matrix}$

From a clever brute-force search, one can learn that

this is the optimal solution assuming all entries are nonnegative integers. The solution is unique up to rotation and reflections.

However, you can do better! The ticket

$\begin{matrix} 2 & -1 & 7 \\ 3 & 10 & 11 \\ 36 & 24 & 77 \\ \end{matrix}$

achieves a score of

170.

$\endgroup$
2
  • 1
    $\begingroup$ Well done! I did never try this on my side... Do you think this can this be improved? $\endgroup$ Jul 4, 2022 at 7:05
  • $\begingroup$ @franckvivien: On an even bet, I would bet it could be improved, yes. My search for nonnegative integer entries was exhaustive, but it gets super slow with negative entries because of all the potential for cancellation. I tried placing a single -1 in the grid. I wouldn't be surprised if this was the best possible there, but I didn't even finish that search in full. I am "worried" (or honestly: excited!) the actual optimum might have a very negative entry, which is currently outside of the reach of my exhaustive searches. Perhaps a more random search would find something! $\endgroup$
    – A. Rex
    Jul 4, 2022 at 12:32
15
$\begingroup$

Very unlikely to be optimal, but got to 120 on my first go:

enter image description here

Approach:

  1. mess around with the problem until it becomes clear that connectivity of the squares will be the main problem.
  2. invent glue, place it in the middle
  3. split the rest of the grid in two: one side for counting ones, the other side for counting the tens (which turned out to be elevens this time around)
$\endgroup$
5
  • 1
    $\begingroup$ According to the link as of 2010, 165 is the highest one found $\endgroup$ Jun 26, 2022 at 23:55
  • $\begingroup$ Nice answer with manual search and smart use of the 0! How would this transpose to 4x4? $\endgroup$ Jun 27, 2022 at 7:04
  • 6
    $\begingroup$ You can change the middle to 1, to increase all sums by 1. Then the range will be 1-121 instead of 0-120, improving this solution by 1. $\endgroup$
    – Kruga
    Jun 27, 2022 at 8:47
  • 2
    $\begingroup$ @Kruga I believe you can even change the middle to 2 increasing all sums with 2. making it able to go from 2-122, but there's a single 1 as well so we can make 1-122. EDIT: Actually you could make it 3 even if I'm not mistaken, so we get 1-123 $\endgroup$
    – Ivo
    Jun 27, 2022 at 13:02
  • $\begingroup$ Yeah, if it weren't for the connectivity requirement, the solution would be trivial - just use every power of 2 from 2^0 to 2^(n-1) (where n is the total number of cells in the square) - gets you any number from 1 to (2^n)-1, so 1-511 for a 3x3, 1-65,535 for 4x4. $\endgroup$ Jun 27, 2022 at 17:24
4
$\begingroup$

Update: Honing in the parameters allowed for a score of 153. This is much closer than I expected to get to the 165 mentioned on the website.

153

original:

I decided to go for a brute force approach and managed a score of 141

141

I generated pseudo-random 3x3 tickets and checked whether or not they were valid solutions.

Tickets were created through the following method:

  • Create a 3x3 matrix of random integers 1 to 35
  • Change another one of the values to be a number between 50 and 70 in order to achieve a higher score (I'll probably do more tests with higher numbers later)
  • I have found that almost all of my solutions with a score greater than 130 have had the numbers 1-4 present, so I made sure all my tickets tested had those 4 numbers

This is by no means the optimal way to generate a ticket, it's just the best method that I found to generate high scoring solutions at a reasonable rate.

The highest single tile that I managed to generate was 67 on this ticket:

enter image description here

$\endgroup$
2
  • $\begingroup$ If I end up generating any better tickets I'll leave a comment or update my answer if its substantial enough $\endgroup$
    – Misdrop
    Jun 29, 2022 at 2:09
  • $\begingroup$ 70 26 32 2 8 7 3 1 16 is 165 one fyi. $\endgroup$
    – Oray
    Jun 29, 2022 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.