Maths Olympiad Prep

Library / /42 of 47

, 2018

Combinatorics Difficulty 4.2 AIME Prove it Canada

Eight people, including triplets Barry, Carrie and Mary, are going for a trip in four canoes. Each canoe seats two people. The eight people are to be randomly assigned to the four canoes in pairs. What is the probability that no two of Barry, Carrie and Mary will be in the same canoe?

Diagonal WYWY of square WXYZWXYZ has slope 2. Determine the sum of the slopes of WXWX and XYXY.

Solution

Solution 1

Among a group of nn people, there are n(n1)2\dfrac{n(n-1)}{2} ways of choosing a pair of these people:

There are nn people that can be chosen first.

For each of these nn people, there are n1n-1 people that can be chosen second.

This gives n(n1)n(n-1) orderings of two people.

Each pair is counted twice (given two people A and B, we have counted both the pair AB and the pair BA), so the total number of pairs is n(n1)2\dfrac{n(n-1)}{2}.

We label the four canoes W, X, Y, and Z.

First, we determine the total number of ways to put the 8 people in the 4 canoes.

We choose 2 people to put in W. There are 872\dfrac{8\cdot 7}{2} pairs. This leaves 6 people for the remaining 3 canoes.

Next, we choose 2 people to put in X. There are 652\dfrac{6\cdot 5}{2} pairs. This leaves 4 people for the remaining 2 canoes.

Next, we choose 2 people to put in Y. There are 432\dfrac{4\cdot 3}{2} pairs. This leaves 2 people for the remaining canoe.

There is now 11 way to put the remaining people in Z.

Therefore, there are 872652432=87654323=76543\dfrac{8 \cdot 7}{2} \cdot \dfrac{6 \cdot 5}{2} \cdot \dfrac{4 \cdot 3}{2} = \dfrac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3}{2^3} = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 ways to put the 8 people in the 4 canoes.

Now, we determine the number of ways in which no two of Barry, Carrie and Mary will be in the same canoe.

There are 4 possible canoes in which Barry can go.

There are then 3 possible canoes in which Carrie can go, because she cannot go in the same canoe as Barry.

There are then 2 possible canoes in which Mary can go, because she cannot go in the same canoe as Barry or Carrie.

This leaves 5 people left to put in the canoes.

There are 5 choices of the person that can go with Barry, and then 4 choices of the person that can go with Carrie, and then 3 choices of the person that can go with Mary.

The remaining 2 people are put in the remaining empty canoe.

This means that there are 4325434 \cdot 3 \cdot 2 \cdot 5 \cdot 4 \cdot 3 ways in which the 8 people can be put in 4 canoes so that no two of Barry, Carrie and Mary are in the same canoe.

Therefore, the probability that no two of Barry, Carrie and Mary are in the same canoe is 43254376543=43276=2442=47\dfrac{4 \cdot 3 \cdot 2 \cdot 5 \cdot 4 \cdot 3}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3} = \dfrac{4 \cdot 3 \cdot 2}{7 \cdot 6} = \dfrac{24}{42} = \dfrac{4}{7}.

Solution 2

Let pp be the probability that two of Barry, Carrie and Mary are in the same canoe.

The answer to the original problem will be 1p1-p.

Let qq be the probability that Barry and Carrie are in the same canoe.

By symmetry, the probability that Barry and Mary are in the same canoe also equals qq as does the probability that Carrie and Mary are in the same canoe.

This means that p=3qp=3q.

So we calculate qq.

To do this, we put Barry in a canoe. Since there are 7 possible people who can go in the canoe with him, then the probability that Carrie is in the canoe with him equals 17\frac{1}{7}. The other 6 people can be put in the canoes in any way.

This means that the probability that Barry and Carrie are in the same canoe is q=17q = \frac{1}{7}.

Therefore, the probability that no two of Barry, Carrie and Mary are in the same canoe is 13171 - 3\cdot\frac{1}{7} or 47\frac{4}{7}.
Solution 1

Consider square WXYZWXYZ in the first quadrant. Suppose that WYWY makes an angle of θ\theta with the horizontal.

[[IMAGE0]]

Since the slope of WYWY is 2, then tanθ=2\tan \theta = 2, since the tangent of an angle equals the slope of a line that makes this angle with the horizontal.

Since tanθ=2>1=tan45\tan \theta = 2 > 1 = \tan 45^\circ, then θ>45\theta > 45^\circ.

Now WYWY bisects ZWX\angle ZWX, which is a right-angle.

Therefore, ZWY=YWX=45\angle ZWY = \angle YWX = 45^\circ.

Therefore, WXWX makes an angle of θ+45\theta + 45^\circ with the horizontal and WZWZ makes an angle of θ45\theta - 45^\circ with the horizontal. Since θ>45\theta > 45^\circ, then θ45>0\theta - 45^\circ > 0 and θ+45>90\theta + 45^\circ > 90^\circ.

We note that since WZWZ and XYXY are parallel, then the slope of XYXY equals the slope of WZWZ.

To calculate the slopes of WXWX and WZWZ, we can calculate tan(θ+45)\tan(\theta + 45^\circ) and tan(θ45)\tan(\theta - 45^\circ).

Using the facts that tan(A+B)=tanA+tanB1tanAtanB\tan(A+ B) = \dfrac{\tan A + \tan B}{1 - \tan A \tan B} and tan(AB)=tanAtanB1+tanAtanB\tan(A- B) = \dfrac{\tan A - \tan B}{1 + \tan A \tan B}, we obtain: tan(θ+45)=tanθ+tan451tanθtan45=2+11(2)(1)=3tan(θ45)=tanθtan451tanθtan45=211+(2)(1)=13\begin{aligned} \tan(\theta + 45^\circ) & = \dfrac{\tan \theta + \tan 45^\circ}{1 - \tan\theta \tan 45^\circ} = \dfrac{2+1}{1-(2)(1)} = -3 \\ \tan(\theta - 45^\circ) & = \dfrac{\tan \theta - \tan 45^\circ}{1 - \tan\theta \tan 45^\circ} = \dfrac{2-1}{1+(2)(1)} = \dfrac{1}{3}\end{aligned} Therefore, the sum of the slopes of WXWX and XYXY is 3+13=83-3 + \dfrac{1}{3} = -\dfrac{8}{3}.

Solution 2

Consider a square WXYZWXYZ whose diagonal WYWY has slope 22.

Translate this square so that WW is at the origin (0,0)(0,0). Translating a shape in the plane does not affect the slopes of any line segments.

Let the coordinates of YY be (2a,2b)(2a,2b) for some non-zero numbers aa and bb.

Since the slope of WYWY is 22, then 2b02a0=2\dfrac{2b-0}{2a-0}=2 and so 2b=4a2b = 4a or b=2ab=2a.

Thus, the coordinates of YY can be written as (2a,4a)(2a,4a).

Let CC be the centre of square WXYZWXYZ.

Then CC is the midpoint of WYWY, so CC has coordinates (a,2a)(a,2a).

We find the slopes of WXWX and XYXY by finding the coordinates of XX.

Consider the segment XCXC.

Since the diagonals of a square are perpendicular, then XCXC is perpendicular to WCWC.

Since the slope of WCWC is 22, then the slopes of XCXC and ZCZC are 12-\frac{1}{2}.

Since the diagonals of a square are equal in length and CC is the midpoint of both diagonals, then XC=WCXC = WC.

Since WCWC and XCXC are perpendicular and equal in length, then the “rise/run triangle” above XCXC will be a 9090^\circ rotation of the “rise/run triangle” below WCWC.

[[IMAGE1]]

This is because these triangles are congruent (each is right-angled, their hypotenuses are of equal length, and their remaining angles are equal) and their hypotenuses are perpendicular.

In this diagram, we have assumed that XX is to the left of WW and ZZ is to the right of WW. Since the slopes of parallel sides are equal, it does not matter which vertex is labelled XX and which is labelled ZZ. We would obtain the same two slopes, but in a different order.

To get from W(0,0)W(0,0) to C(a,2a)C(a,2a), we go up 2a2a and right aa.

Thus, to get from C(a,2a)C(a,2a) to XX, we go left 2a2a and up aa.

Therefore, the coordinates of XX are (a2a,2a+a)(a-2a,2a+a) or (a,3a)(-a,3a).

Thus, the slope of WXWX is 3a0a0=3\dfrac{3a-0}{-a-0}=-3.

Since XYXY is perpendicular to WXWX, then its slope is the negative reciprocal of 3-3, which is 13\dfrac{1}{3}.

The sum of the slopes of WXWX and XYXY is 3+13=83-3 + \dfrac{1}{3} = -\dfrac{8}{3}.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.