0

We have 1000 apples and 900 of them are "Good".If we distribute these apples into some equal groups ,what's the minimum percentage of groups in which the majority of apples are "Good"?

I think the answer must be 90%,but the formal answer says it is: 80% !! I don't get it! because overall 90% of apples are "Good"! I tried many different equal groupings...
(Origin: Iranian National Mathematical Olympiad,1st round,2016)

Hamid Reza Ebrahimi
  • 3,445
  • 13
  • 41

2 Answers2

3

We divide the 1000 apples in $n$ groups. In order for a group to not have a majority of good apples, there must be $\lceil \frac{1000}{n} \times \frac{1}{2} \rceil = \lceil \frac{1000}{2n} \rceil$ bad apples in the group. Since we have 100 apples, the maximum number of groups for which there are at least $\lceil \frac{1000}{2n} \rceil$ bad apples equals $\bigg\lfloor \frac{100}{\lceil \frac{1000}{2n} \rceil} \bigg\rfloor = \frac{n}{5}$ for $n | 500$ and $5 | n$. Since there are $n$ groups, the maximum percentage of groups for which there is no majority of good apples thus equals $\frac{\frac{n}{5}}{n} = \frac{1}{5} = 20\%$. As such, at least $80\%$ of groups contain a majority of good apples.

The following table shows the ratio of groups not containing a majority of bad apples, for all divisors of 1000 (multiply row and column value):

$$ \begin{array}{r | c c c c} & 1 & 2 & 4 & 8 \\ \hline 1 & 0.000 & 0.000 & 0.000 & 0.125\\ 5 & 0.200 & 0.200 & 0.200 & 0.175\\ 25 & 0.200 & 0.200 & 0.200 & 0.167\\ 125 & 0.200 & 0.200 & 0.200 & 0.100 \end{array} $$

jvdhooft
  • 7,589
  • 9
  • 25
  • 47
  • Excellent,but please answer my question:
    Do you agree that we must put good apples in the same group in order to get the minimum percentage?     – Hamid Reza Ebrahimi Jun 03 '17 at 09:27
  • @HamidRezaEbrahimi In order to get the minimum percentage of groups with a majority of good apples, it must hold that $n | 500$ and $5 | n$, and we must put $\frac{500}{n}$ bad apples in each non-majority group. I updated my answer and provided the ratio of groups not containing a majority of bad apples for all divisors of 1000. – jvdhooft Jun 03 '17 at 09:46
2

This in no way proves that 80% is the correct answer, but it's actually not clear if you want a proof of that or just an explanation of why 90% is wrong. Make 500 groups of two apples. Potentially 100 (20%) of those groups contain a bad apple and thus the majority of apples in that group aren't good, leaving 80% of groups in which the majority is good.

Henrik supports the community
  • 6,831