2
$\begingroup$

Can you please help me with this problem?

There are $2n$ boxes labeled with numbers $1, 2, \cdots, 2n$ and $2n$ papers also labeled $1, 2, \cdots, 2n$. If we put papers in boxes (one paper in each box) and add their numbers (sum of paper number and box number), what is the probability that:

a) the sum of each paper/box pair is even?
b) the sum of exactly two paper/box pairs is even?
c) the sum of at least two paper/box pairs is even?

Now, I have done the following:

a) Let's say we put the $i^{th}$ paper in the $i^{th}$ box, pairs will be $(1,1),(2,2),\cdots,(2n,2n)$ where left coordinate is paper and right coordinate is box. There are $n!$ ways of permuting odd-labeled papers and $n!$ ways of permuting even-labeled papers. The total number of possible events is (2n)!, so the probability of having only even paper/box pairs equals $\frac{(n!)^2}{(2n)!}$.

I have trouble finding the solutions for b) and c). If anyone could provide me with a detailed explanation, I would be very grateful. According to the solution, the answer to c) equals 1 - the solution for a). I don't see a connection between the two, so why is this?

$\endgroup$
  • $\begingroup$ For $b$: you must first pick the two "even" boxes and their contents. Note that one of these must have an even number and the other an odd number written on it. Then for the rest you have $n-1$ evens and $n-1$ odds to permute. $\endgroup$ – lulu Jun 9 '17 at 19:11
  • $\begingroup$ As to your comment for $c$: true, these are not mutually exclusive. But an event which is mutually exclusive with $c$ is "every box sums to an odd number " (Why?) $\endgroup$ – lulu Jun 9 '17 at 19:13
2
$\begingroup$

The key observation to make for $b)$ is that odd sums--and consequently, the number of even sums--can only be made in a certain way. This constraint not only removes some of the complexity surrounding how to get started for $b)$, but it can also be used to simplify $c)$ to a very simple problem.

Try creating an odd number of even sums. Let $S_{E}$ denote the quantity of even box-paper sums, and suppose you have an odd $S_{E}$. Even sums can only occur in box-paper pairs with the same parity, so it follows that one of the parities has a greater quantity remaining for the $S_{O}$ remaining odd sum pairs. But odd sum pairs can only be made from a box and paper with opposite parities. Thus, in pairing opposite parities together, one parity's quantity will run out. With one parity remaining, you have more even sum pairs--a contradiction. Not only do $S_{E}$ and $S_{O}$ have to be even, but the number of odd pairs and even pairs have to be equal.

So $S_{E}$ and $S_{O}$ have to be even, and the number of even pairs and odd pairs have to be equal. This will be very useful. Returning to $b)$, we can now conclude that the only way in which $S_{E} = 2$ is if there is one odd pair and one even pair. The number of ways in which an odd pair can be made is $n^{2}$, as it is for even pairs. For each such pairing, we have $(n-1)!$ choices for permuting the remaining papers in each parity. This gives

$$\frac{n^{2}(n!)^{2}}{(2n)!}.$$

For $c),$ bear in mind the key concept that we've shown so far: The quantity of even sums has to be even. Since $2$ is the smallest even number, this means that the probability of at least two even sums is equivalent to the probability of no odd sums occurring, which you've already calculated unintentionally in $a)$.

$\endgroup$
  • $\begingroup$ Hey, thank you for the answer. Although, it is still not clear to me totally. First, if in b) I can make n such pairs with odd, and n such pairs with even that is n^2, and that is ok. The question that I have is if I can permute remaining papers in (n-1)! ways for each, even and odd. Why isn't it n^2*((n-1)!)^2 ? And second, can you please give me a little bit more detailed explanation about middle part of your answer(number of even and odd sums) since I still don't understand it. Thank you. $\endgroup$ – user423843 Jun 10 '17 at 9:12
1
$\begingroup$
  1. All even papers must be assigned to even boxes, and odd papers must be assigned to odd boxes. Given that their are $(2n)!$ possible arrangements, this probability equals:

$$\frac{(n!)^2}{(2n)!}$$

  1. In order for two box/paper combinations to be even, one odd paper must be assigned to one odd box and one even paper must be assigned to one even box. For all other combinations, an even paper must be assigned to an odd box and an odd paper must be assigned to an even box. As such, the probability of this happening equals:

$$\frac{{n \choose 1}^2{n \choose 1}^2(n-1)!(n-1)!}{(2n)^2} = \frac{(n!)^2n^2}{(2n)!}$$

  1. The probability of having at least two even boxes equals 1 minus the probability of no even box/paper combinations or one even box/paper combination. However, it is impossible to have only one even box/paper combination: if an odd label is assigned to an odd box, we are left with an unassigned even label and an unassigned even box. As such, the probability of having at least two even box/paper combinations equals 1 minus the probability of having only odd box/paper combinations:

$$1-\frac{(n!)^2}{(2n)!}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy