The sweeties shop called "Olympiad" sells boxes of $6,9$ or $20$ chocolates. Groups of students from a school that is near the shop collect money to buy a chocolate for each student; to make this they buy a box and than give to everybody a chocolate. Like this students can create groups of $15=6+9$ students, $38=2*9+20$ students, etc. The seller has promised to the students that he can satisfy any group of students, and if he will need to open a new box of chocolate for any group (like groups of $4,7$ or $10$ students) than he will give all the chocolates for free to this group. Can there be constructed the biggest group that profits free chocolates, and if so, how many students are there in this group?
Problem
Source: Albanian IMO 2011 TST
Tags: modular arithmetic, combinatorics unsolved, combinatorics
03.06.2011 16:25
Eh, I don't quite get the problem. So, let the number of students be $x$. We need to find the maximum of $x$ that cannot be represented as $6a + 9b + 20c$ for some $a,b,c \in \mathbb{Z}^+_0$. Is my interpretation correct?
03.06.2011 16:26
ridgers wrote: The sweeties shop called "Olympiad" sells boxes of $6,9$ or $20$ chocolates. Groups of students from a school that is near the shop collect money to buy a chocolate for each student; to make this they buy a box and than give to everybody a chocolate. Like this students can create groups of $15=6+9$ students, $38=2*9+20$ students, etc. The seller has promised to the students that he can satisfy any group of students, and if he will need to open a new box of chocolate for any group (like groups of $4,7$ or $10$ students) than he will give all the chocolates for free to this group. Can there be constructed the biggest group that profits free chocolates, and if so, how many students are there in this group? $43$ proof: $x\equiv 0\pmod{3}$ simple that every number bigger then $3$ is possible. $x\equiv 1\pmod{3}$ : 40+3k is possible fos each $k\ge2$ $x\equiv 2\pmod{3}$ : 20+3k is possible fos each $k\ge2$ Hence $43$ is biggest one. $2k+3s$ can be each number bigger than $1$ by chickentheorem and so each number bigger tan $3$ by $6's$ and $9's.$ ps: the interpretation was correct
02.06.2012 14:50
$43$ is not representable, as it is trivially checked. Now, we have the following: $44=6+2 \cdot 9+20$, $45=4 \cdot 9$, $46=6+2 \cdot 20$, $47=3 \cdot 9+20$, $48=2 \cdot 6+4 \cdot 9$, $49=9+2 \cdot 20$: by adding enough $6$'s, we see that every greater integer is attainable, so $43$ is the desired value. Remark. Moreover, we can find integers which are representable in arbitrarily many distinct ways.
29.09.2013 01:52
Sorry to revive, but... honestly this problem is pretty pathetic for an Olympiad. Last year, it was #2 out of 4 on the Algebra I section of a state math tournament... I didn't realize they ripped it off until now.
13.06.2023 04:10
ridgers wrote: The sweeties shop called "Olympiad" sells boxes of $6,9$ or $20$ chocolates. Groups of students from a school that is near the shop collect money to buy a chocolate for each student; to make this they buy a box and than give to everybody a chocolate. Like this students can create groups of $15=6+9$ students, $38=2*9+20$ students, etc. The seller has promised to the students that he can satisfy any group of students, and if he will need to open a new box of chocolate for any group (like groups of $4,7$ or $10$ students) than he will give all the chocolates for free to this group. Can there be constructed the biggest group that profits free chocolates, and if so, how many students are there in this group? By Chicken McNugget Theorem: The greatest integer that cannot be written in the form $3a+10b$ for non-negative integers a, b is $3\times 10-10-3=17$ $\Rightarrow$We can get all even numbers greater than $34$ can be represented in the form $6a+20b$ Adding $9:$ $\Rightarrow$ We can get all odd numbers greater than $43$ So if there exists a number $N$ that is not of the form $6p+9q+20r \Rightarrow N\le 43$ It is easy to check that $N=43$ is the maximum$_\blacksquare$