Competition problem — Combinatorics

Library / /298 of 348

Combinatorics Difficulty 5.1 AIME, harder Find the answer

Consider the set of 5-tuples of positive integers at most 5. We say the tuple $\left(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}\right)$ is perfect if for any distinct indices $i, j, k$ , the three numbers $a_{i}, a_{j}, a_{k}$ do not form an arithmetic progression (in any order). Find the number of perfect 5-tuples.

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

There are two situations. 1. The multiset is aabbc; the only condition here is $c \neq \frac{1}{2}(a+b)$ , for $\left(\binom{5}{3}-|S|\right) \cdot\binom{3}{1}=18$ such triples, where $S$ is the set of unordered triples $(a, b, c)$ which do not satisfy the condition, and $S=\{(1,2,3),(2,3,4),(3,4,5),(1,3,5)\}$ . Each one gives $\frac{5!}{2!2!}=30$ orderings, so $18 \cdot 30=540$ in this case. 2. There are four distinct elements in the tuple. Then, the elements must be $\{1,2,4,5\}$ . All of them work, for an additional $4 \cdot 60=240$ . Therefore, there are $540+240=780$ such tuples.

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

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.