Mykolka the numismatist possesses $241$ coins, each worth an integer number of turgiks. The total value of the coins is $360$ turgiks. Is is necessarily true that the coins can be divided into three groups of equal total value ?
Problem
Source:
Tags: combinatorics unsolved, combinatorics
19.05.2007 17:54
RDeepMath91 wrote: Mykolka the numismatist possesses $241$ coins, each worth an integer number of turgiks. The total value of the coins is $360$ turgiks. Is is necessarily true that the coins can be divided into three groups of equal total value ? Let $a_{1}$ the number of coins whose value is exactly $1$ turgik. Considering that all the other coins have a value of at least $2$, we have $a_{1}+2(241-a_{1})\leq 360$, and so $a_{1}\geq 122$ Since we have $241$ coins whose total value is $360$, the biggest coin value possible is $120$ Now split all the $241-a_{1}$ coins whose values are greater than $1$ turgik in two groups A and B whose difference of values is minimum, say $B=A+\Delta$. Take then one coin in B (any coin). Let $m$ its value. Obviously, moving this coin from group B to group A may not reduce the difference between A and B (since $\Delta$ is supposed the minimum one) and so $m\geq \Delta$. Since $A+\Delta+A+a_{1}=360$ and since $a_{1}\geq 122$, we have $A=180-\frac{a_{1}}{2}-\frac{\Delta}{2}< 120$ Consider now the 3 groups : $F$ is the group of $a_{1}$ $1$-turgik coins plus the selected $m$-turgiks coin : Total is $a_{1}+m$ $G$ is the group $A$ : Total is $A=180-\frac{a_{1}}{2}-\frac{\Delta}{2}<120$ $H$ is the group $B$ minus the selected $m$-turgiks coin. Total is $A+\Delta-m=180-\frac{a_{1}}{2}+\frac{\Delta}{2}-m\leq A<120$ In order to complete group $G$ up to $120$, we need $C_{G}=120-A=\frac{a_{1}}{2}+\frac{\Delta}{2}-60$ In order to complete group $H$ up to $120$, we need $C_{H}=\frac{a_{1}}{2}-\frac{\Delta}{2}+m-60$ And $C_{G}+C_{H}=a_{1}+m-120$ and, since no coin may have a value $>120$, $C_{G}+C_{H}\leq a_{1}$ Hence, we have enough $1$-turgik coins to move from $F$ to groups $G$ and $H$ to value them at $120$ (and group $F$ will then also have value of $120$). And it is true that the coins can be divided into three groups of equal total value. -- Patrick
20.05.2007 15:50
That's a nice solution.. Thx, pco