I am submitting a very interesting problem from a French mathematical recreation site:
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:
- 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)
- 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)