About Last Month
Both of these problems can be boiled down to well known combinatorial identities. However, if you're not familiar with them, they can still be tricky problems. Before reading the solutions, you should make sure you are familiar with binomial coefficients. I will use the notation C(n,k) here. This is also the same number of ways to pick k distinct objects from n things and hence is often said as "n choose k".
The first problem comes down to rearranging a string. If you have a string of length n, then there are exactly n! (see factorial) ways to rearrange the string. So for instance, BASE can be rearranged into 4!=24 different strings. When you look at the word BALL, this technique doesn't quite work since you can write BALL and then switch the last two letters, yielding the identical string BALL. The key idea here is to first label the L's as L1 and L2. Now BAL1L2 becomes BAL2L1 when the last two letters are switched. So we can count these strings and see that there are 4!=24. Of course, this isn't exactly what we want, but we'll deal with that next.
It is easy to check now that Every string (when removing the subscripts) has been counted exactly twice--each corresponding the one where L1 comes first and the one where L2 comes first. Since we've counted every string twice, this means there must be 4!/2=12 total ways.
This idea generalizes nicely. Suppose we have a string of length n with m distinct characters such that our m characters occur k1, k2, ... , km times where k1+k2+...+km=n. We first label each identical character so we can create n! strings and then check to see how much we've overcounted.
For the ith character, we can permute them in exactly ki! ways and we can do this for each character, so we've overcounted by k1!k2!...km!. Hence, we have n!/(k1!k2!...km!) total strings. For BASEBALL, this gives 8!/(2!2!2!1!1!)=5,040 different strings. For BASEKETBALL, this gives 11!/(2!2!2!2!1!1!1!)=2,494,800 different strings.
For the second problem, the answer is just C(7,4)=35 if he gets 4 different beverages, since he's choosing 4 things from 7 options. If he's allowed repetitions, there is a combinatorial identity that says the number of ways to pick k things from n objects when allowing repetitions is C(n+k-1,k). So in this case, if Mauer is allowed to pick more that one of the same beverage, he can do this in C(7+4-1,4) = C(10,4) = 210 ways. Let's see where this comes from.
Suppose he is getting the seven beverages from a machine that knows he's going to pick four. It will start by asking him if he wants a Coke. If he says "no", the machine moves on to the next beverage. However, if he says "yes" then the machine will ask him again if he wants a Coke. This continues on. Every time Joe says "yes", the machine asks him again if he wants the same beverage. The exception to this is that the machine doesn't need to ask him again after the fourth time he says "yes", since the machine will know that he can't say yes again. So the machine is going to ask Joe a total of 7+4-1 questions to which Joe is going to answer "yes" 4 times and "no" the rest of the time (more generally, it will ask n+k-1 questions and he'll say "yes" k times).
So Joe's responses will be a string of length 10 with 4 Y's. An example would look something like YYNNNNYNYN. In this example, if the questions were asked in the same order as was stated in the problem (Coke, Cherry Coke, Diet Coke, Coke Zero, Cherry Coke Zero, Vanilla Coke, and Vanilla Coke Zero), we can verify that Joe picked 2 Cokes, 1 Cherry Coke Zero, and 1 Vanilla Coke. And we could do this with any string of length 10 with 4 Y's, so there is a one-to-one correspondence.
The problems
The first problem here was actually a problem of the week here at the Citadel a few weeks back. I liked the problem, so I'm sharing it with you here. As it turns out, the problem wasn't as I interpreted it, so I'm changing it to what I had interpreted, which I think it a more interesting problem.
I've tried to generalize it a bit in problem 2, but haven't worked on it hard enough to figure it out. I don't think it's because it's necessarily that hard of a problem, I just haven't put the effort into it yet and wanted to give you guys an opportunity to help out.
1. Five people play a game where during each game they can either win a point (+1) or lose a point (-1). After they play for a while, the total number of points accumulated by the players is exactly zero. Assuming no player has the same number of points and the player with the most points has more points (in magnitude) than the player with the fewest points, what is the smallest number of points he can have?
For example, the final scores can't be any of the folowing:
-1,0,1,2,3 (scores don't sum to zero)
-2,-1,0,1,2 (the largest and smallest scores are the same in magnitude)
-1,-1,0,0,2 (several players have the same score)
In the original problem, it was meant that each person played a one-on-one match-up with another person, which is not what I mean here. Here I mean that all 5 people play every game and each can either gain or lose a point independently of each other player.
2. Five people (or k people, if you really want to generalize) play a game in which they either win m points (+m) or lose n points (-n). Assuming they can play as many times as they want and stop whenever they want, what are the possibilities for final scores?
Below is a thought for problem 2:
OK, almost immediately after writing up that spoiler, I solved the second problem. It's not so bad...
I may have misunderstood the question.
No, I think you got it and more elegantly than I did (or we're both wrong).
Ok, I should have known you were wrong at first when I got the same answer as you.
As far as I can tell, it's the same answer though. It just has one extra restriction on it. Very interesting.
For the problem of the week here, it turns out that they were supposed to interpret it the way you two did at first. I think the problem is more fun the way I presented it. 🙂
Problem 1:
Problem 1
I need to reflect to see if I even understand what problem 2 is asking before I start peeking.
I guess I did it wrong the same way that everyone else did. Yeah, that's way more interesting, GH.
So why doesn't AMR's spoiler text hide in the right column?
That's next month's TNHP.
Those are the same expressions. Not sure why I re-grouped things, but it made more sense to me for the things I was trying to do.
Yeah, you need to get off of parity a little bit. 😛
I'd really like to think more about problem 2, but work is heavy this month. Take-home work.
Also, I was more into combinatorics, and this seems more like Algebra. (The one math course I truly hated, I took it in my one semester as a grad student.)
Is it? I guess it kind of is. Combinatorics is applied algebra, though. 🙂