26 thoughts on “The Nation Has Problems, Vol. 4”

1. Problem 1:

   Spoiler	SelectShow
   n = number of letters z = number of repeated letters The number of different strings is n!/2^z. n! gives the total number of permutations, and 2^z removes the examples where repeated letters are swapped (which would give the same string). BASE --> 4! = 24 BALL --> 4!/2 = 12 BASEBALL --> 8!/2^3 = 5,040 BASEKETBALL --> 11!/2^4 = 2,494,800

   Problem 2:

   Spoiler

   SelectShow

   are we talking distribution of drinks? or just which four he picks out of the cooler? Put another way, is giving Tolbert a Diet Coke while Nishioka, Casilla, and Plouffe get a Coke the same as Casilla getting a Diet Coke while the other three get Coke? 7 soda options Different for each is 7!/3! = 840 possibilites (assuming order matters). Divide by 4! to remove the different orders of the same sodas if order doesn't matter. 840/4! = 35. If repetitions are allowed then he has 7^4 = 2,401 possibilities (assuming order matters). If order doesn't matter, I'm having a tough time with this for some reason.

   1. Your first solution is right, but doesn't quite generalize to a string like MISSISSIPPI. I think that is probably a harder question.

      For the second one, I guess you can interpret it in either way. It's an easier problem if you assume it matters who gets what drink. It's a harder problem if you assume it doesn't--that is, just assume he comes back in his car with 4 different drinks--how many different combinations are there?

      1. Right, my solution for #1 only works if the letters are either unique or duplicates.

         Haven't checked this but what about this as a general solution:

         Spoiler	SelectShow
         n = number of letters z = number of letters repeated y times strings = n!/(y!^z) So, for MISSISSIPPI, strings = 11!/[(4!^2)*(2!^1)] = 34,650

         1. Yep! Now try working on the second one when order doesn't matter. 🙂

            1. Spoiler

               SelectShow

               The answer is 210, which I got by a modified-BFH approach. Reverse-engineering from there the formula for this is the sum of a series sum from n=1 to k of (k-n+1)*(n^2+n)/2 in this case, k=7, so the sum becomes: 7*1 + 6*3 + 5*6 + 4*10 + 3*15 + 2*21 + 1*28 = 210 Why does this work for choosing 4? I'm not sure. For choosing 3 the formula is different: sum from n=1 to k of (k-n+1)*n And choosing 2 the formula becomes: sum from n=1 to k of (k-n+1)*1 and converting the '1' term in the choosing 2 case to the 'n' term in the choosing 3 case to the '(n^2+n)/2' is that each is the sum of the previous case (this makes sense in my head, but I feel like I'm not explaining it very well). So it's kind of a sum-within-a-sum thing that I don't know how best to express. That's the best I got.

            2. Alternatively:

               Spoiler

               SelectShow

               my modified-BFH approach. There are 5 possible ways 4 sodas can be arranged. AAAA - can be arranged one way (4!/4!^1 = 1) AAAB - can be arranged four ways (4!/3!^1 = 4) AABB - can be arranged six ways (4!/2!^2 = 6) AABC - can be arranged twelve ways (4!/2!^1 = 12) ABCD - can be arranged 24 ways (4! = 24) AAAA - 7 choose 1 = 7 possibilities AAAB - 7 choose 2 = 7!/5! = 42, then *4 arrangements = 168 possibilities AABB - same as above except *6 arrangements and /2 to remove AABB = BBAA = 126 possibilities AABC - 7*6 choose 2 = 7*6!/2! = 1260 possibilities ABCD - 7 choose 4 = 7!/3! = 840 possibilities note that 7+168+126+1260+840 = 2401 (the number of total possible 4-soda choices) Then divide the possibilities by the permutations AAAA - 7/1 = 7 AAAB - 168/4 = 42 AABB - 126/6 = 21 AABC - 1260/12 = 105 ABCD - 840/24 = 35 7+42+21+105+35 = 210.

               1. That is right! There is actually a much simpler way to count this, but it's not the most obvious idea. I didn't even know about it until I came across it in my book when I was going to teach my students!

               2. Spoiler	SelectShow
                  Mastermind!

2. I'm stalling on Problem 1.

   Spoiler

   SelectShow

   BASE: 4 one-letter strings 4x3=12 two-letter strings 4x3x2=24 three letter strings 4x3x2x1=24 four-letter strings Total: 4+12+24+24=64 strings BALL: 4-1=3 one-letter strings B, A, L, L 4x3-2-3=7 two-letter strings BA, BL, BL AB, AL, AL LB, LA, LL LB, LA, LL 4x3x2-3x2-3x2=12 three-letter strings BAL, BAL, BLA, BLL, BLA, BLL ABL, ABL, ALB, ALL, ALB, ALL LBA, LBL, LAB, LAL, LLB, LLA LBA, LBL, LAB, LAL, LLB, LLA 4x3x2x1-3x2x1-3x2x1=12 four-letter strings BALL, BALL, BLAL, BLLA, BLAL, BLLA ABLL, ABLL, ALBL, ALLB, ALBL, ALLB LBAL, LBLA, LABL, LALB, LLBA, LLAB LBAL, LBLA, LABL, LALB, LLBA, LLAB Total: 3+7+12+12=33 strings The generalization of this isn't screaming out at me, but I'll trudge through a few different routes to a solution. Method 1: N total characters (BALL has 4). There are N!/(N-X)! different N-char strings. Then subtract the number of those that would be double-counted. This is what I illustrated above. The trick here would be determining the number of double-countable (or generally multiple-countable) strings. Method 2: M total letters (BALL has three). There are M different possibilities for the first character, but then, there might be M or M-1 different possibilities for the second character, depending upon which letter is first. We could get to the two-letter strings by 3x2+1 (for the one that uses both Ls), and for three-letter strings 3x2x1 + 2x3 (3x2x1 are the number of 3-distinct-letter strings, 2x3 is the number of 3-letter strings with both Ls: 2 for the possibilities of the other letter and 3 for the number of positions it could be in). Again, this doesn't feel easily generalizable. Oh well, I'll try this tack for "BASEBALL": Rearranging the letters for simplicity: AABBLLES. 5 letters, 8 characters. By string length n and d doubles (n,d): D represents doubled letters (D1, D2, D3) S represents non-doubled letters (S1, S2, etc.) (1,0): 5 (2,0): 5x4 = 20 (2,1): 3 (3,0): 5x4x3 = 60 (3,1): 3x4x3 = 36 (3 choices for D, four choices for S, 3 ways of arranging: SDD, DSD, DDS) (4,0): 5x4x3x2 = 120 (4,1): 3x(4x3)x6 = 216 (3 choices D, 4x3 ordered choices for the Ss, 6 ways of ordering them keeping the non-doubled letters in order: DD12, D1D2, D12D, 1DD2, 1D2D, 12DD) (4,2): 3x2x3 = 18 (3 choices D1, 2 choices for D2, 3 ways of ordering them: 1122, 1212, 1221). (5,0): 5x4x3x2x1 = 120 (5,1): 3x(4x3x2)x10* = 720 (3 choices of D, 4x3x2 ordered choices for the Ss, 10 ways of arranging them.) (5,2): (3x2x3)x3x5 = 270 (3x2x3 from (4,2) scenario, 3 choices for S, 5 locations for S). (6,0): 0 (6,1): 3x(4x3x2x1)x15* = 1080 (3 choices for D, 4x3x2x1 choices for the Ss, 15 ways to arrange them). (6,2): (3x2x3)x(3x2)x15* = 1620 (3x2x3 choices and orderings for the two Ds, 3x2 choices for Ss, 15 ways of arranging them across each other. (6,3): (3x2x1)x(5x3) = 90 (6 ordered ways of picking the Ds, 15 ways to order them, which I came to by this: First letter must be D1, and the first D2 must be before D3. After removing the second D1, there are three ways of arranging the D2 and D3. Then the second D1 must be in position 2 through 6.) (7,1): 0 (7,2): (3x2x3)x(3x2x1)x35** = 3780 (7,3): ((3x2x1)x(5x3))x2x7 = 1260 ((3x2x1)x(5x3) is from (6,3), two choices for S, 7 positions it can be in) (8,2): 0 (8,3): ((3x2x1)x(5x3))x(2x1)x28* = 5040 (much like 7,3, but with 28 arrangements for S1 and S2. *One insight I got into this was using the triangular numbers. Consider the (5,1) case. If the first D is in position 1, then the other D can be in positions 2,3,4, or 5. If the first D is in position 2, the other D can be in positions 3,4, or 5. All possibilities are 4+3+2+1 = 10. **35 is a "pyramidal number" There are 5 positions that S1 can be in, if S1 is in position 1, there are 15 positions that S2 and S3 can be in. If S1 is in position 2, there are 10 positions that S2 and S3 can be in, and so on... Overall: 1char: 5 2char: 23 3char: 96 4char: 354 5char: 1,110 6char: 2,790 7char: 5,040 8char: 5,040 Total: 14,458

   I stole from my employer this afternoon. I think I must stop here for now.

   1. Wow. That is way more answer than I expected from anyone! You're overthinking the problem a bit though. We're only counting strings created by rearranging the letters into a string of the same length.

      1. That sounds easier, but I think I came to some ideas through brute forcing that might allow me to do it the way you said.

         Anyways, shifting to #2:
         Assuming that Diet Coke != Coke Zero (although I believe otherwise)

         Spoiler

         SelectShow

         I counted seven types of soda. If everyone wants a different type of soda, I've got 7x6x5x4/(4x3x2x1) = 7!/(3!4!) = 35 different possibilities. Then, if he can have multiple cans of the same type of Soda, 7 ways of getting all four the same, 63 ways of getting two different types: 21 = 7!/(2!5!) ways of choosing 2 flavors, times three ways of allocating them to four cans (AAAB, AABB, ABBB) 105 ways of getting three different types: 35 = 7!/(3!4!) ways of choosing 3 flavors, times three ways of allocating them to four cans (AABC, ABBC, ABCC) 35 ways of getting four different flavors (above). 7+63+105+35 = 210 Hmm... That's 7x6x5 = 7!/4! Seems like that should mean something.

         1. Spoiler	SelectShow
            The answer I know is actually represented as C(10,4) (10 choose 4), which gives the same value.

            1. You got any insight into that?
               Or are you going to make us wait a month?

               1. I dunno, I might just make you wait. 🙂

            2. Also, I've forgotten my terminology.
               I read above that DG called them "permutations," which was a term I should have remembered.
               I don't know how well I could keep "Choose" from "Pick" even when I was taking Discrete Mathematics, or whatever other class(es) it came in.
               I know one is ordered and one is unordered (counts separate permutations as the same thing).
               That's why I just went back to spelling it out with the factorials and even just writing the factors.

               1. Permutations refer to cases when you care about the order of something, while combinations don't care about order. So for instance, lining up people in a row would be a permutation problem, while just picking a subset of a group of people is a combination problem.

                  Here, problem 1 is about permutations while problem 2 is about combinations. And yeah, you probably got it in a discrete math course!

      2. BASEKETBALL = 11 Characters, 7 letters.
         4 doubled letters, 3 single letters.

         Spoiler

         SelectShow

         If we identify the doubled letters, BASEKetbaLl, there are 11! different combinations. By making the two B's identical, BASEKeTBaLl, we halve the number of possiblities: 11!/2 For each two-letter pair where we make the letters identical, we halve the number of possibilities. Therefore, BASEKETBALL has 11!/(2^4) = 2,494,800 combinations. Generalizing, given a string of X characters where there are A single-use letter, B double-use letters, C triple-use letters, D, quadruple-use letters... (and where X = A + 2B + 3C + 4D + ...), then the number of combinations is X!/[(1!^A)x(2!^B)x(3!^C)x(4!^D)x...] Checking my math, BALL should have 4!/(2!) = 12 BASEBALL should have 8!/(2!^3) = 5040. Hey! It works! Sometimes I just need to brute-force things for a while until I get a feel for what's going on. I couldn't finish it at work, so I just posted what I had. I now see why looking for all of the strings of any length was way more complicated: have to cover all of the different ways that the given multiples can be used.

         I wasn't completely stealing from my employer, either. It was just sub-optimal use of my time. I am an actuary and exercising my math skills is still valuable.

         1. It's cool, I'm posting right now from work. As a professor, I consider this a valid use of my time, since I'm contributing to the mathematical community!

            1. please cite as "GreekHouse. 2011d. `The Nation Has Problems, Vol. 4.' Teh Interweb's basement: wgom.org Press."

               1. This is truly a citation that will change the world of mathematics.

3. Spoiler

   SelectShow

   1. Since BASE has four unique numbers, than it would be 4! = 4*3*2 = 24. BALL has two Ls, so I presume the Ls aren't differentiated, so you don't count the times the Ls swap positions, so that would cut the number of strings in half to 12. IIRC, that is actually 4! / 2!, which is 4*3. BASEBALL has eight letters, so there are 8! strings, which = 40,320. However, there are two pairs of repeating letters, so you would divide by 4!, which is 5*6*7*8 = 1,680. BASEKETBALL has 11 letters, so that would be 11! = 39,916,800. However, it has three pairs of repeating letters, so that would mean it has 11! / 3! unique strings, which would be 4*5*6*7*8*9*10*11 = 6,652,800 strings. 2. Assuming Mauer is not getting a drink for himself, if he must get four different drinks and seven to choose from, then he has seven to pick from to begin with and his choices reduce by 1 each time he picks another, so that would be 7*6*5*4 = 840. If repetitions are allowed, then he has seven to choose from each time, so it is just 7^4 = 2,401.

   1. Spoiler	SelectShow
      2. Whoops. I forgot order doesn't matter since we don't know who the teammates are, so it doesn't matter what order they are in. For example, if he wanted all diet, that is only one combination, not 4! combinations, so I think that means you have to divide by 4!, which would be 35 if repeats aren't allowed. I'm not sure how to do it with repeats. I don't have time right now to tackle that one.

      1. Yes, the second part of #2 is the hardest one. The first part should be a bit easier.

   2. Spoiler	SelectShow
      That is almost correct, but you're dividing by the wrong thing. Try thinking about what you are overcounting when you count 8!

      1. Spoiler

         SelectShow

         OK, since these are just pairs of identical letters, then that means when they swap positions, they are being counted a second time even though the string is identical, so you are double-counting for each pair of identical letters, so you should divide by 2 for each pair, meaning for BASEBALL, you divide by 6 (I missed the third pair originally), so it is 8! / 6 = 6720. That means in BASEKETBALL, with 11 letters and four pairs, it is 11! / 8 = 4,989,600.

         1. Spoiler	SelectShow
            Still not quite right. In BASEBALL, you should be dividing by 8 (which is (2!)^3). Think about why...

Comments are closed.