1
$\begingroup$

In how many ways can one or more of $101$ letters be posted in $101$ letter boxes?

$\quad\quad\quad\quad\quad1)10100 \quad\quad 2) 101^{100} \quad\quad 3) 100^{101} \quad\quad 4) 101(101^{101} - 1)/100$

I am not sure where I am going wrong in interpreting this problem but the obvious thing that came to my mind is to assume letters and letter boxes all distinct and apply mutual inclusion-exclusion but from the answer options that doesn't seems not be the correct approach for this one.where exactly I am going wrong?

  • 0
    Does it not say whether letters and letter boxes are distinct?2011-09-15
  • 4
    My immediate interpretation of the problem would lead to $102^{101}-1$, since each of the letters can go in either one of the 101 letterboxes or not be posted at all, and then we just have to exclude the case where none of the letters were posted. But that's not even close to any of the options.2011-09-15
  • 0
    @Thijs Laarhoven:Nopes,nothing explicitly.2011-09-15
  • 0
    If the correct answer is indeed (4), then the question is just ill-formulated.2011-09-15
  • 0
    @Thijs Laarhoven:I don't know the answer yet,but I agree this is not much of good formulation.2011-09-15

1 Answers 1

2

Hint: It appears you are considering all the letters and all the boxes to be distinct, but you post letters in a given order. I can't get any of the answers to work any other way. Then one letter can be posted to one of $101$ boxes in $101$ ways, two letters can be posted in $101^2$ ways (each letter is independent of the other), and so on. Summing the geometric series gives what?

  • 2
    So with this reasoning, you cannot only post letter $2$. If you post letter $i$, then also all letters $1, \ldots, i-1$ must get posted. Strange.2011-09-15
  • 0
    Summing up the geometric series gives that option $4$,but in that model shouldn't $102^{101} - 1$ seems more correct,consistent to the model problem *number of ways of putting some or more of $101$ distinct objects to $101$ distinct pockets*?!2011-09-15
  • 2
    @Foo I like to think of this answer as the number of nonempty strings (in the computer science sense) of length at most $101$ over an alphabet of size $101$. So it's like you decide how many letters you want to post, buy so many from the post office, and then decide in what order you want to post them. I agree that this is strange. :-)2011-09-15
  • 0
    @Sri: So if I send one letter then I only send a letter to Ross; if I send two letters, then I send letters to Ross and Fool; and only if I send three letters, then I send letters to Ross, Fool and Srivatsan... But I never only send a letter to Srivatsan. Makes sense :P2011-09-15
  • 0
    @Thijs No, that is not what I said. Actually, I said something similar to your first comment under this answer. So let's say you decide to send 3 letters. Then you can pick RFS or RRF or SSR or FFF or any other 3-letter string. [Similarly, if you want to send only 1 letter, then you can send it to R or F or S; the only issue is that the sent letter counts as letter 1 by default.] But you cannot send the second letter without sending the first. Anyway, I see no point in discussing this ill-formulated question... :)2011-09-15
  • 2
    @Sri I think your description is a good one. It that was intended, it should have been made clear. It's sort of like playing Jeopardy: the answer is $101(101^{101}-1)/100,$ what is the question?2011-09-15
  • 0
    @Sri: Boxes and letters are interchangeable here. I interpreted the different alphabet symbols as different mailboxes and position $1$ as the letter to Ross.2011-09-15