Maths Olympiad Prep

Library / /211 of 213

, 2023

Combinatorics Difficulty 4.9 AIME Find the answer Canada

Given the list 2,3,4,52,3,4,5,
there are exactly three different ways to choose three integers from the
list and form a triangle whose side lengths are equal to those integers.
The integers chosen could be 2,3,42,3,4
or 2,4,52,4,5 or 3,4,53,4,5. The integers 2,3,52,3,5 cannot be used as side lengths of a
triangle. Given the list 4,10,3,n,134,10,3,n,13, there are exactly four
different ways to choose three integers from the list and form a
triangle whose side lengths are equal to those integers. If nn is different from all other numbers in
the list, then the sum of all possible values of nn is

Pick one

Solution

We can represent the given information in a Venn diagram by first
introducing some variables.

Let xx be the number of students
that participated in hiking and canoeing, but not swimming.

Let yy be the number of students
that participated in hiking and swimming, but not canoeing.

Let zz be the number of students
that participated in canoeing and swimming, but not hiking.

Since 10 students participated in all three activities and no students
participated in fewer than two activities, we complete the Venn diagram
as shown.

[[IMAGE0]]

Suppose that the total number of students participating in the school
trip was nn.

Since 50% of all students participated in at least hiking and canoeing,
then 50100n\dfrac{50}{100}n or n2\dfrac{n}{2} participated in at least
hiking and canoeing.

Since this number of students, n2\dfrac{n}{2}, is an integer, then nn must be divisible by 2.

Similarly, 60100n\dfrac{60}{100}n or
3n5\dfrac{3n}{5} students participated
in at least hiking and swimming.

Since this number of students, 3n5\dfrac{3n}{5}, is an integer, then nn must be divisible by 5 (since 3 and 5
have no factors in common).

This means that nn is divisible by
both 2 and 5, and thus nn is
divisible by 10.

From the Venn diagram, we see that x+10=n2x+10=\dfrac{n}{2}, and y+10=3n5y+10=\dfrac{3n}{5}.

Since the total number of participants is nn, we also get that x+y+z+10=nx+y+z+10=n or z=n10xyz=n-10-x-y.

We may now use these equations, x=n210, y=3n510, and z=n10xyx=\dfrac{n}{2}-10,\ y=\dfrac{3n}{5}-10, \text{ and } z=n-10-x-y and the fact that nn is divisible by 10, to determine all
possible values of zz.

We can then use the values of zz to
determine all possible values of the positive integer kk, where k%k\% participated in at least canoeing and
swimming.

Since nn is a positive integer
that is divisible by 10, its smallest possible value is 10.

However, substituting n=10n=10 into
x=n210x=\dfrac{n}{2}-10, we get x=510x=5-10 and so x=5x=-5 which is not possible. (Recall that
xx is the number of students that
participated in hiking and canoeing, but not swimming, and so x0x\geq0.)

Next, we try n=20n=20.

When n=20n=20, x=1010x=10-10 and so x=0x=0.

When n=20n=20, y=3×20510y=\dfrac{3\times20}{5}-10 or y=1210y=12-10, and so y=2y=2.

Finally, when n=20n=20, x=0x=0, and y=2y=2, we get z=201002=8z=20-10-0-2=8.

When z=8z=8, the number of students
who participated in at least canoeing and swimming is 8+10=188+10=18 (since 10 students participated
in all three), and so the percentage of students who participated in at
least canoeing and swimming is 1820×100%=90%\dfrac{18}{20}\times 100\%=90\%, and so
k=90k=90.

In the table below, we continue in this way by using successively
greater multiples of 10 for the value of nn.

nn
x=n210x=\dfrac{n}{2}-10
y=3n510y=\dfrac{3n}{5}-10
z=n10xyz=n-10-x-y
k=z+10n×100k=\dfrac{z+10}{n}\times100

20
0
2
8
k=8+1020×100=90k=\dfrac{8+10}{20}\times100=90

30
5
8
7
k=7+1030×10056.7k=\dfrac{7+10}{30}\times100\approx56.7

40
10
14
6
k=6+1040×100=40k=\dfrac{6+10}{40}\times100=40

50
15
20
5
k=5+1050×100=30k=\dfrac{5+10}{50}\times100=30

60
20
26
4
k=4+1060×10023.3k=\dfrac{4+10}{60}\times100\approx23.3

70
25
32
3
k=3+1070×10018.6k=\dfrac{3+10}{70}\times100\approx18.6

80
30
38
2
k=2+1080×100=15k=\dfrac{2+10}{80}\times100=15

90
35
44
1
k=1+1090×10012.2k=\dfrac{1+10}{90}\times100\approx12.2

100
40
50
0
k=0+10100×100=10k=\dfrac{0+10}{100}\times100=10

For values of nn that are greater
than 100, we get that z<0z<0, which
is not possible.

Therefore, the sum of all such positive integers kk is 90+40+30+15+10=18590+40+30+15+10=185.

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.