Maths Olympiad Prep

Library / HMMT November /463 of 672

HMMT November, 2018

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:
Let AA be the number of unordered pairs of ordered pairs of integers between 11 and 66 inclusive, and let BB be the number of ordered pairs of unordered pairs of integers between 11 and 66 inclusive. (Repetitions are allowed in both ordered and unordered pairs.) Find A−BA - B.

Solution

Solution:
There are 6⋅66 \cdot 6 ordered pairs of integers between 11 and 66 inclusive and 2121 unordered pairs of integers ((62)=15\binom{6}{2} = 15 different pairs and 66 doubles). Then, A=(362)+36=666A = \binom{36}{2} + 36 = 666 and B=21⋅21=441B = 21 \cdot 21 = 441. Therefore A−B=225A - B = 225.

For general nn, there are n2n^{2} ordered pairs of integers and n(n+1)2\frac{n(n+1)}{2} unordered pairs of integers. Then A=n2(n2+1)2A = \frac{n^{2}(n^{2}+1)}{2} and B=n2(n+1)24B = \frac{n^{2}(n+1)^{2}}{4} so
A−B=n2(2(n2+1)−(n+1)2)4=(n(n−1)2)2 A - B = \frac{n^{2}\left(2\left(n^{2}+1\right)-(n+1)^{2}\right)}{4} = \left(\frac{n(n-1)}{2}\right)^{2}

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.