Moviegoers' Club: Largest Number of Common Favorite Movies

[Rogerio]

Each one of the 23 members of a moviegoers' club has selected his two favorite movies from a 50 movies list.
It is noted that any two members have at least one favorite movie in common.
What is the largest number of members that have necessarily selected a same movie?
Prove that.

 

[mathal]

I'm not sure why this wasn't solved sooner.

Spoiler

A member has two favorite movies. One or both match one or both of the other member's choices. In the extreme case the other 22 members are split equally between the two movies the member chose. 12 is the answer. (11+1) Any higher number is not necessarily what happened. 12 always will be true.

mathal

 

[D H]

I'm not sure why this wasn't solved sooner.

Possibly because it wasn't worded well. Poorly worded puzzles tend to be ignored.

Here's my interpretation:

Each members of a 23-member moviegoers' club selects two movies from a list of 50 movies as their personal favorite movies. On examining the selections, it is noted that the selections by any two members have at least one movie in common. Given this, what is the smallest possible number of members who voted for the most popular movie, the movie that was selected by the most number of members?

Note: There may be a tie for the most popular movie.​

TL;DR answer:

Spoiler

Sixteen

Details:

Spoiler

Denote S as the set of selections made by the members, P as the number of people who voted for the most popular movie in the selection S, and U as the set of unique movies in the set S. and . The key is the cardinality of the set U.

The set U comprises at least two members (all members voted for the same two movies) and at most 24 members (all members voted for the same most popular movie, but their is no commonality amongst their second choices). In both of these extreme cases, the number of people who voted for the most popular movie is 23. In fact, if the cardinality of U is four or more then all of the members had to agree on one movie as the most popular. Thus P is 23 if the cardinality of U is anything but three. The only way to have P less than 23 is if the cardinality of U is three.

Designate these three movies as A, B, and C, and the designate the number of people who voted for movies A & B as ab, A & C as ac, and B & C as bc. Without loss of generality, stipulate that ab≥ac≥bc. This means movie A is the most popular movie with ab+ac total votes. This will attain a minimum value of 16 when ab=8, ac=8, bc=7 or when ab=9, ac=7, bc=7. Any other combination of votes yields a larger value for P.

 

[Rogerio]

I'm not sure why this wasn't solved sooner.

A member has two favorite movies. One or both match one or both of the other member's choices. In the extreme case the other 22 members are split equally between the two movies the member chose. 12 is the answer. (11+1) Any higher number is not necessarily what happened. 12 always will be true.
mathal

Hi Mathal,
there is at least a movie that received more than 12 votes, necessarily.
So, 12 is not the answer.

 

[Rogerio]

Possibly because it wasn't worded well. Poorly worded puzzles tend to be ignored.

Here's my interpretation:

Each members of a 23-member moviegoers' club selects two movies from a list of 50 movies as their personal favorite movies. On examining the selections, it is noted that the selections by any two members have at least one movie in common. Given this, what is the smallest possible number of members who voted for the most popular movie, the movie that was selected by the most number of members?
​

That's right, the way puzzles are worded matters a lot!
And it seems you have correctly understood my puzzle.

However, the answer to your version (which has nothing to do with the original idea) is "ONE" .
If, for instance, 23 members had voted for a movie, then there would be one member who had voted for that movie.
And 1 is smaller then 23.
So, "one" is the smallest number of members who voted for the most popular movie.

In fact, if the cardinality of U is four or more then all of the members had to agree on one movie as the most popular. Thus P is 23 if the cardinality of U is anything but three. The only way to have P less than 23 is if the cardinality of U is three.

Come on, this is not a proof.

 

[D H]

However, the answer to your version (which has nothing to do with the original idea) is "ONE" .
If, for instance, 23 members had voted for a movie, then there would be one member who had voted for that movie.
And 1 is smaller then 23.
So, "one" is the smallest number of members who voted for the most popular movie.

Nonsense. You already said that that movie received 23 votes.

This apparently is a minimax problem. You worded it very poorly. I had to read it multiple times before I realized that you meant smallest rather than largest.

Come on, this is not a proof.

Sure it is. Read the proofs in an advanced math text. They skip over the obvious steps. If four (or more) movies received a vote by at least one member, then there is exactly one movie in that set of four (or more) movies for which each of the 23 members voted. That's rather obvious, isn't it?

 

[Rogerio]

If 23 have voted, then 1 has voted. So 1 is the smallest number.
And this is not "advanced math" - it should be found in an introductory logic text.

 

[Rogerio]

In fact, if the cardinality of U is four or more then all of the members had to agree on one movie as the most popular. Thus P is 23 if the cardinality of U is anything but three. The only way to have P less than 23 is if the cardinality of U is three.

If four (or more) movies received a vote by at least one member, then there is exactly one movie in that set of four (or more) movies for which each of the 23 members voted. That's rather obvious, isn't it?

Saying it is obvius is not a proof.
Prove it.

 

[Rogerio]

I'm not sure why this wasn't solved sooner.

Hi Mathal,
I don't know, either.


But I would like to point out that "the largest necessary" is equivalent to "the smallest enough".
Maybe someone doesn't understand this.

 

[D H]

"The smallest enough" is not proper grammar. This appears to be a puzzle of your own making, or you've reworded the original so much that I can't find it on the net. In any case, the wording needs help. Prima facie evidence: The puzzle lingered unanswered for more than two weeks. That doesn't happen at this site unless the puzzle is either inscrutable or impossible.

Some advice: When someone tells you that what you wrote isn't clear, you most likely did not write clearly. Don't be defensive. Peer review is the time to "check your ego at the door." If you (or anyone else) have a better wording than mine, have at it.

 

[mfb]

Saying it is obvius is not a proof.
Prove it.

That is easy to prove.

Spoiler

Consider an arbitrary person 1, call his favorite movies A and B. Consider a second person 2 who chose at least one different movie, call this C, and let A be the movie they both chose. If any other member 3 chooses a movie different from A, B and C (this is possible if U>3), the second chosen movie has to be A, otherwise he does not have a movie in common with person 1 (if the selection is B), 2 (if C), or even both (if the selection is none of A,B,C). At the same time, the combination (BC) becomes impossible as it would not give a common choice with person 3. Therefore, all members have to select A as one of their favorite movies.