Maths Olympiad Prep

Library / /282 of 348

Combinatorics Difficulty 5.1 AIME, harder Find the answer

How many functions f:{1,2,,10}{1,2,,10}f:\{1,2, \ldots, 10\} \rightarrow\{1,2, \ldots, 10\} satisfy the property that f(i)+f(j)=11f(i)+f(j)=11 for all values of ii and jj such that i+j=11i+j=11.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To construct such a function ff, we just need to choose a value for f(x)f(x) from {1,2,,10}\{1,2, \ldots, 10\} for each x{1,2,,10}x \in\{1,2, \ldots, 10\}. But the condition that f(i)+f(j)=11f(i)+f(j)=11 whenever i+j=11i+j=11 means that f(10)=11f(1)f(9)=11f(2)f(6)=11f(5)\begin{aligned} f(10) & =11-f(1) \\ f(9) & =11-f(2) \\ \vdots & \\ f(6) & =11-f(5) \end{aligned} This means that once we have chosen f(1),f(2),f(3),f(4)f(1), f(2), f(3), f(4), and f(5)f(5), the five remaining values of f(6),f(7),f(8),f(9)f(6), f(7), f(8), f(9), and f(10)f(10) are already determined. The answer is therefore just the number of ways to choose these first five values. Since there are 10 possibilities for each one, we get that the answer is 105=10000010^{5}=100000.

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.