2003 AIME II problem 12

The members of a distinguished committee were choosing a president, and each member gave one vote to one of the 27 candidates. So it looks like they all got at least one vote. For each candidate, the exact percentage of votes the candidate got was smaller by at least one than the number of votes for that candidate. Let me underline this again and read it again. It's kind of a confusing statement. For each candidate, the exact percentage of votes the candidate got was smaller by at least one than the number of votes for that candidate. What is the smallest possible number of members of the committee? So let's define some variables here and maybe we can get our heads around this. So let's just say that m is equal to the number of members of the committee. That's equal to the number of members. And let's just think about each candidate. Let's say that we have 27 candidates, but let's just pick some arbitrary candidate i, so that i could be any number from one to 27, any integer. This sentence right here, let me write in blue since I underlined it in blue. Let me write it here. Candidate c sub i is equal to the number of votes for the ith candidate. Now let's see if we can do something with what I underlined in blue. The exact percentage of votes the candidate got was smaller-- OK. So the exact percentage of votes the candidate got would be the votes he got or she got divided by the total number of members. Now this will give you a decimal. If you want it as a percentage, you're going to want to multiply it by 100. So times 100. So that's this part. The exact percentage of votes the candidate got, so that's this right here, was smaller by at least one than the number of votes for that candidate. So smaller by at least one. So the number of votes of the candidate is c sub i, and it's not less than or equal to the number of votes they got. It's less than or equal to 1 less than the number of votes they got, at least 1 less. So we're going to put a minus 1 here. So this is telling us that the percentage of votes that any candidate got is less than the number of votes they got minus 1, which is really what that sentence is saying. And frankly, that's the hardest part about this problem, is understanding what that sentence is even saying. Now what is the smallest possible number of members of the committee? Now think about it. We want to minimize the number of members. So we really want to minimize the number of votes that each candidate gets. So let's just think about the minimum number of votes for each candidate, per candidate. So can we have 0 votes for a candidate? Well, they tell us here. They say each member gave one vote to one of the 27 candidates. So everyone got at least one vote. So no. We cannot have 0 votes. Can we have one vote per candidate? It seems fair that they each got at least one vote. But if we look over here, their percentage having to be 1 less than the number of votes they have, and that's what we wrote over here, that makes 1 pretty difficult. Let's think about this a little bit. Let's think about it. If the minimum number of votes is 1, that means for that candidate who got the minimum number of votes, the right-hand side of this equation right here, this right-hand side of the equation would be-- sorry. My cell phone is ringing. My apologies. So where I left off, we were thinking, can we have one vote for a candidate or can there be a candidate that only has one vote? Can the minimum votes per candidate be one? And we were looking at the right-hand side of this equation we set up from the word problem. And if it was 1, this right here would be 0. And this, on the left hand side, if it's at least 1-- we know that we have a positive number of members. And we know that this is going to be at least 1. So this is going to be some positive fraction that we're going to multiply by 100. So there's no way that that can be less than or equal to 0. So even the guy or the gal who got the fewest votes has to get more than one vote. So this also can't be the case. This expression right over here can never be less than or equal to 0, which would be the case if the minimum number of votes was one. So let's think about more of them. Let's see if we can ever have two votes for a candidate, a minimum of two votes. And to do that, what I want to do-- if we put 2 in here-- what I want to do is I want to see what repercussions that has for our members. Does it put any threshold for our members? And to do that, let me solve for m. It actually simplifies a little bit now that we've put the constraint that our minimum number of votes can never be equal to 1. So what I want to do is, let's take the inverse of both sides of this equation. Let me do this in a new color. Let me do it in pink. Let's take the inverse of both sides of this equation. The left hand side over here, we essentially have 100 ci over m, so that will be m over 100 c sub i. And since we're inverting both sides of the equation, this less than or equal is going to become a greater than or equal to. And then we're going to have 1 over c sub i minus 1. So I just inverted both sides. You swap the inequality. Obviously, if you had 1 is less than 2, now if you invert them, 1 is greater than 1/2. So that's the logic behind swapping the inequality. And now, if I want to solve for m, I can multiply both sides by 100ci, and that's a positive value, so it won't do anything to the inequality. So m is going to be greater than or equal to 100 c i, the number of votes the ith candidate got over ci minus 1. So let's see. Can a candidate get 2 votes? So if a candidate got 2 votes-- if the candidate with the fewest votes got 2, what repercussions would that have based on what we just solved for? Well, in that situation, m would have to be greater than or equal to 100 times 2 over 2 minus 1. So m would have to be greater than 200. Seems reasonable. Maybe our answer is 200, or greater than or equal to 200. So maybe our answer's 200. But let's try it with some larger minimum number of votes. Maybe that can bring down our m a little bit. So what if we had 3? What does this inequality tell us? Then m would have to be greater than or equal to 300 divided by 3 minus 1, 300 divided by 2. Yep. It did come down. So it looks like as we increase our minimum number of votes per candidate, we're getting this threshold for m to come down. So let's try higher numbers. If our minimum vote per candidate is 4, then we have m is greater than or equal to 400 over 3. So m would have to be greater than or equal to 133 1/3. And obviously, this has to be an integer right here. So the smallest possible m in this situation would be 134. Well, it seems like we're making progress here. Let's try 5. If we have a minimum number of votes of 5, then m has to be greater than or equal to 500 divided by 4 is 125. Now this looks tempting, but remember, this is the minimum number of votes per candidate, and we have 27 candidates. So what does this tell us about the minimum-- if this is the minimum votes per candidate, what is the minimum number of votes, not even thinking about this threshold here. Well, it's going to be this number times 27. In this case, if you had two votes for candidate you would have to have 54. That's 27 times 2. 27 times 3 is 81. 27 times 4 is what. That's 80, that's 108. 27 times 5 is 135. So even though having at least 5 votes per candidate kind of loosens your constraint on m, if you have 5 votes per candidate, you're going to have 135 votes. You can't get down to 125 votes. If you have 4 votes per candidate-- in order to have 4 times 27, you only need 108. So if you bump that 108 to 134-- Well, there's two ways you could get 134 votes. You can give 26 people 5 votes, and then give the last person 4 votes, and that would meet the constraint over here. It gets you 1 less than 135. Or you could give 26 people 4 votes and give the last person-- I think it would come out to be 30 votes. And either way, this would work. So our answer is if we have 134 votes-- or I guess another way to say it is our answer to the question is the minimum number of committee members we need is 134. Hopefully, you found that interesting.