La réponse du jeudi (59) : score impossible

You can find this issue in pdf format.

Thursday question # 59: In a sport, actions can yield $ 6, $ 9 or $ 20 $ points. What is the highest score that is impossible to achieve?


Begin by determining the number of points that can be obtained by executing only the corresponding measures $ 6 and $ 9 points. Since $ 6 = 3 \ times $ 2 and $ 9 = 3 \ times $ 3, it is already clear that we will obtain the so multiples of $ 3.

But we can say better. For this, demonstrate an intermediate result.

Lemma. Any integer $ \ geq $ 2 can be written in the form $ a \ times 2 + b \ times $ 3.

Proof. The proof of this result is very simple, but based on a principle that resservira us, we will call the principle of consecutive scores . The key point is that $ 2 and $ 3 are two consecutive integers can be written in the form requested (tautological way in their case). By adding $ 2, we get it then is the same $ 4 $ and $ 5. By adding $ 2 to $ 6 and $ 7, and so on for all the successive integers: as $ 2 is in the list of allowed scores, simply find $ 2 consecutive scores for all higher scores.

our intermediate issue was therefore resolved: the scores (strictly positive) possible from shares worth $ 6 and $ 9 $ points are exactly the scores of the form $ 3 \ times n $, where $ n $ is an integer $ \ geq $ 2.

What will happen if we now allow the action to $ 20 $ points? Like $ 6 and $ 9 are always multiples of $ 3, he'll have to use the action to $ 20 $ points to get scores that are not multiples of $ 3. Specifically, as $ 20 = 3 \ times 6 + $ 2 and $ 40 = 3 \ times 13 + $ 1, we have to at least do this once to get scores like $ 3k + $ 2 and at least two time to get scores like $ 3k + 1 $. This already shows that all the scores of the form $ 3k + $ 1 lower at $ 40 are impossible (the latter is $ 37 = 3 \ times 12 + $ 1) and even that $ 43 is impossible because it would take to get . score twice $ 20 $ points, but it is impossible to score three points missing to verify that numbers greater than $ 43 are possible scores, then we can adopt several strategies:
 

Note. Possible scores in a sport form what is called a digital semigroup . For example, there has been interest here in semigroup $ \ langle 6, 9, 20 \ rangle $. One can quite easily show that if the number of points reported by the various actions (the generators of the semigroup) have no common divisor $> $ 1, then all scores are possible from a certain rank (included) , is called the number Frobenius or the driver of the semigroup. Here was therefore demonstrated that the number of Frobenius $ \ langle 6, 9, 20 \ $ rangle was $ 44. The problem of determining the number of Frobenius a digital semi-group is an extremely complicated issue and very wide open. For more on this, we can not recommend the excellent article Digital Semi-groups and conjecture Wilf Shalom Eliyahu, appeared on Mathematics Images .