Generating Functions or Counting?

Question

Alice has two bags. Each bag has $4$ slips of paper with the numbers $1$ through $4$ on them.

Betty also has two bags, each with $4$ slips of paper with positive integers on them. They decide to play a game whereby each girl pulls a slip from each of her own bags, records the sum of the numbers, then returns each slip to the bag it came from. The numbers in Betty's bags are not $1$ through $4$ in each bag, but the expected distribution of her sums is the same as Alice's. What are all eight numbers in Betty's bags?

Would a way to solve this problem be using generating functions? Counting?

score 4 · Accepted Answer · answered Jun 13 '15 at 02:58

4

Neither. Start by computing the frequency distribution of sums for Alice:

$$\begin{array}{rccc} \text{sum}:&2&3&4&5&6&7&8\\ \text{frequency}:&1&2&3&4&3&2&1 \end{array}$$

Betty has the same distribution, and the slips of paper in her bags have positive integers written on them.

Show that each of Betty’s bags must contain exactly one slip with the number $1$.
Show that if each of Betty’s bags contained a slip with the number $2$, then her bags would be a copy of Alice’s which is not allowed. Conclude that one of Betty’s bags contains two slips numbered $2$, and the other contains no slips numbered $2$.

At this point we know that one of Betty’s bags contains a $1$ and no $2$s, and the other contains a $1$ and two $2$s, so we have totals of $2,3$, and $3$, and the smallest remaining number in either bag is a $3$.

Show that in order to get the sum $4$ with frequency $3$, we must have two $3$s in one bag and one $3$ in the other. Which bag is which?
Now complete the assignment of numbers to Betty’s bags.

answered Jun 13 '15 at 02:58

Brian M. Scott

616,228

Are the eight numbers $1, 1, 2, 2, 3, 3, 3, 4$? $1, 2, 2, 3$ for one of the bags and $1, 3, 3, 4$ for the other? – Dreamer Nov 04 '16 at 22:25
1

@Regina: Not quite: you can’t get $8$ with those numbers, and you get frequencies of $5,4$, and $1$ for $5,6$, and $7$, when you should have $4,3$, and $2$. One of your numbers has to be changed, but only one. – Brian M. Scott Nov 04 '16 at 22:34
Is it $1, 1, 2, 2, 3, 3, 3, 5$? I know it's the last number. – Dreamer Nov 04 '16 at 22:49
1

@Regina: Yes, assuming that you split it $1,2,2,3$ and $1,3,3,5$, – Brian M. Scott Nov 04 '16 at 22:49
[+1] Thanks for taking your time to go over this problem with me! – Dreamer Nov 04 '16 at 22:51
@Regina: You’re very welcome! – Brian M. Scott Nov 04 '16 at 22:51

score 2 · Answer 2 · answered Jun 13 '15 at 02:52

Generating functions, I think.

The generating function for Alice’s outcomes is $g(x)=(x+x^2+x^3+x^4)^2$. Can you find polynomials (one for each of Betty’s bags, which have $N$ and $M$ slips in them, respectively) $b_1(x)=\sum\limits_{i=1}^{N}x^{n_i}$ and $b_2(x)=\sum\limits_{i=1}^{M}x^{m_i}$ where $g(x)=b_1(x)\cdot b_2(x)$ and the sets $\{n_i\}_{i=1}^N$ and $\{m_i\}_{i=1}^M$ are sets of positive integers that are different from $\{1,2,3,4\}$?

Generating Functions or Counting?

2 Answers2