The universal ticket

Question

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)

2. 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)

Answer 1

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.

Answer 2

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

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)

Answer 3

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.

original:

I decided to go for a brute force approach and managed a score of 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: