Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The moviegoers' club

  1. Apr 29, 2013 #1
    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.
  2. jcsd
  3. May 15, 2013 #2
    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.

  4. May 15, 2013 #3

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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:

    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 abacbc. 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.
  5. May 15, 2013 #4
    Hi Mathal,
    there is at least a movie that received more than 12 votes, necessarily.
    So, 12 is not the answer.
  6. May 15, 2013 #5
    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.

    Come on, this is not a proof.
    Last edited: May 15, 2013
  7. May 15, 2013 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.

    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?
  8. May 15, 2013 #7
    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.
  9. May 15, 2013 #8
    Saying it is obvius is not a proof.
    Prove it.
  10. May 16, 2013 #9
    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.
    Last edited: May 16, 2013
  11. May 16, 2013 #10

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    "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.
  12. May 16, 2013 #11


    User Avatar
    2017 Award

    Staff: Mentor

    That is easy to prove.
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for moviegoers' club
PF Investing Club