Spring 2017, problem 37

At the state fair, there were $6$ different food items that could be bought. After the receipts were tabulated, it was found that each pair of food items was bought by more than two fifths of the eaters. Moreover, no one bought all $6$ of the food items. Show that at least $2$ people bought $5$ of the food items. EDIT (2/6): As pointed out below, the problem should originally stated "exactly $2$ people" when it should have said "at least $2$ people".

Comments

ImpartialJames

5 years ago

I think the problem should be "Show that at least $2$ people bought $5$ of the food items."

Imagine there are 15 buckets, each labeled by a pair of foods. Place a token in a bucket for each customer who bought the corresponding pair of foods. Letting the number of customers be $N$, each bucket has more than $\frac25N$ tokens. Since $N$ is an integer, this implies each bucket as at least $\frac25(N+1)$ tokens, so there are at least $6N+6$ tokens total.

A customer who buys exactly $k$ different foods contributes a token to $(k \text{ choose } 2)=\frac{k(k-1)}{2}$ buckets. No customer bought 6 foods, each customer who bought five foods contributes $10$ tokens, and customers who bought 4 or fewer foods contribute at most $6$ tokens.

Now, suppoe there was only one customer who bought 5 foods. The other $N-1$ customers contribute at most 6 tokens apiece, so the number of tokens would be at most $6\cdot(N-1)+10\cdot 1=6N+4$, which contradicts that the number of tokens was at least $6N+6$. Therefore, at least two customers bought 5 foods.

Thank you for the modification but I have still some worries with this problem.

First it should be specified that eaters can only buy DISTINCT foods once ie a customer who buys five foods will buy five DIFFERENT foods. Now taking the bucket image we know from the problem statement that the number of tokens in each bucket is strictly more than two fifths of N (number of customers). In mathematical language it says that the number of tokens in each bucket is at least : Floor function (2N/5) +1 Consequently the total number of tokens is at least 15Floor function (2N/5) +15 Now N can take five different values( mod5) and we see that if N is equal to 2 (mod5) then the total number of tokens is at least 6N+3 and not 6N+6 as stated above. This unfortunately invalidates the above argument. As an example take N=7 If 6 customers buy four foods and one customer buys five foods then the total number of tokens is 6X6 +10=46. At the same time each bucket has at least three tokens which gives a total of 45 which is compatible with the above figure.Therefore the problem should state:show that at least one person bought 5 foods.

michel 5 years ago