Better than Average Ice-creams
The store has 6 flavors of ice-cream. Each of 6 friends likes exactly 4 flavors.
Is there guaranteed to be a flavor which at least 4 friends like?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
8 solutions
This is a good understandable solution demonstrating good thinking without getting bogged down in math. I like elegant solutions like this.
The most ice creams she can supply without handing over four ice creams with the same flavour is 6 x 3 = 18. How did you get this ?
Log in to reply
Hi Dane,
The vendor has six flavours of ice cream. If she hands over three ice creams from each flavour, that makes 18 ice creams. If she hands over even one more ice cream, she has no option but for it to be one of the six flavours. But she has already handed out three ice creams with that flavour.
Hope you get it!
Yes, I would also like to know how to arrive at this result.
Upvote for the "greedy" :-)
(6 people * 4 likes / person) / 6 flavors = an average of 4 likes per flavor. They can't all be liked by fewer than the average.
Moderator note:
To clear up some confusion from the comments, this answer is discussing the average . In an positive average, it is perfectly allowable to have some of the numbers be zero; but that means other numbers in the list must be larger to compensate. For example, if all the friends like the same four flavors, then the average is
( 6 + 6 + 6 + 6 + 0 + 0 ) / 6 = 4 .
We can then apply the pigeonhole principle , using flavors as holes and friend-flavors as pigeons, to conclude that there is at least one hole with at least 4 pigeons. Thus, this gives us the flavor that is liked by at least 4 friends.
Nothing in the question precludes all of the friends liking the same combination. If all six friends like vanilla, chocolate, strawberry and mint -- then no one likes the fudge ripple and sorbet.
Log in to reply
This is true. But this answer discussing the average, which doesn't exclude the possibility some flavors are liked by nobody. The problem is merely to establish there is a flavor at least 4 friends like.
good thinking.
What if all like the dame 4 ice creams, and the other ice cream is chosen??
Log in to reply
Sorry not dame it's same
Log in to reply
It's asking if there exists a flavor liked by at least 4, not if all flavors are liked by at least 4.
if all likes the same 4 ice creams then the condition is already filled(is there a guaranteed way to be a flavor which at least 4 friends like?)
There just cannot be any flavour that is not liked by anybody, as it's clearly stated that each of 6 friends like exactly 4 flavours. And how this came, For example, if all the friends like the same four flavors, then the average is (6+6+6+6+0+0)/6 = 4 ??
Log in to reply
Yes, they like exactly 4 flavors, it didn't state the set of flavors they liked were distinct. They could each like exactly the same 4 flavors.
Let a i j = 1 if the flavor i is liked by the friend j , and is 0 otherwise. Since each friend likes at least 4 flavors, we have i , j ∑ a i j ≥ 6 × 4 = 2 4 . ( 1 ) Now, assume on the contrary that no flavor exists which is liked by at least 4 friends, i.e., all flavors are liked by 3 friends or less. This implies that i j ∑ a i j ≤ 6 × 3 = 1 8 . ( 2 ) Eqn (2) contradicts (1) and this implies that there does exist a flavor which is liked by at least 4 friends.
This is the Pigeonhole Principle (under Discrete Mathematics on the topics on this site). Putting 24 pigeons (the 24 unknown icecreams in the diagram) into 6 pigeonholes (the 6 flavours).
Friend A Friend B Friend C Friend D
Flavor 1 X X
Flavor 2 X X
Flavor 3 X X X
Flavor 4 X X X X
Flavor 5 X X X
Flavor 6 X X
No matter what you do, at least one row and column intersect 4 times.
its saying each friend likes exactly 4 flavours, not atleast 4 flavours
It doesn't say that the store has the flavors that the kids like.
I took a slightly different approach to the other posted solutions.
Let us suppose that everyone liked exactly 3 flavours. We could arrange this by dividing the 6 friends into two even groups, with each group liking the flavours the other group didn't. So, let's say that friends 1, 2, and 3 like flavours a, b, and c, and friends 4, 5, and 6, like flavours d, e, and f. This sets up a situation where each flavour is liked by exactly 3 people.
Now, to bring things in line with the question, I need to assign an extra flavour to each friend. But, any flavour assigned to friend 1, 2, or 3 would have to already be liked by friend 4, 5, and 6. And the same is true in reverse. Therefore, there must be a flavour 4 or more friends like.
This is an interesting constructive approach I hadn't thought about. Can you explain how this splitting mentioned in the second paragraph is done?
Log in to reply
Sure. (I know I have a tendency to not type an important step when I'm not working with rigorous equations. Damn you, Dyspraxia!)
If we suppose each person likes exactly 3 flavours, and no flavour is liked more than three times, then however you arrange the flavours, each flavour will be liked by 3 people, but not the other three. For the sake of clarity of the thought experiment, I split them into two groups, with each group of friends having identical favourite flavours of icecreams.
very clever
Exactly the way I did it!
There are 6!/(4!)(2!)=15 ways to select 4 from a group 6. So 6 of those possibilities would have to have at least one common choice.
Each friend likes exactly 4.......so, there should have been= 6 × 4 = 2 4 flavors for them to select distinct 1.
as, it is not possible, They can't all be liked by fewer than the average of the flavor
I made a chart. listing friends A,B,C,D,E,F as a column. Next to each friend their choices were 1,2,3,4 (of 1-6) for A. 2,3,4,5 for B and so on to F's choices of 6,1,2,3 Quickly you see that there are multiple flavors that they share four times.
Yup, that's just pigeonhole principle in disguise.
Wasn't familiar with the Pigeonhole Principle before. I am now. I'm learning, this is fun.
Is the question right? Because as it reads isn't it obvious? The 6 friends all like exactly 4 flavour of ice cream. So the total 'likes' (if it were as if they were 'liking' on Facebook would be 6 people x 4 likes/person = 24 'likes'. And the AVERAGE of each flavour of ice cream that they 'like' would be 4. And so if there are flavours with less 'likes' than the average, then there has to be at least one flavour with more than 4 'likes' to compensate for that. | If the question had been 'is there guaranteed to be a flavour which at least 5 friends 'like' then the answer would be 'not necessarily' because each of the flavours could be 'liked' by exactly the average of 4 people. Regards, David
If the question had been 'is there guaranteed to be a flavour which at least 5 friends 'like' then the answer would be 'not necessarily' because each of the flavours could be 'liked' by exactly the average of 4 people.
I agree, but that is not what the question is.
The question asks
Is there guaranteed to be a flavor which at least 4 friends like?
and the answer is
Yes, always
Suppose the six greedy friends all order the four flavours which they like.
Then the vendor must supply 24 ice-creams.
The most ice creams she can supply without handing over four ice creams with the same flavour is 6 × 3 = 1 8 .
So to make the number up to 24 she must hand out at least four ice creams with the same flavour.
These four ice-creams must all go to different people, because no one ordered more than one ice-cream with the same flavour! Since these four people ordered only the ice-creams they like, they must all like this flavour!