Maths Olympiad Prep

Track / Stage 6 / 240 of 400 #1240 of 1964

Problem 1240

National olympiad, first round
Combinatorics Difficulty 6.4 Find the answer

For any set A={x1,x2,x3,x4,x5}A = \{x_1, x_2, x_3, x_4, x_5\} of five distinct positive integers denote by SAS_A the sum of its elements, and denote by TAT_A the number of triples (i,j,k)(i, j, k) with 1i<j<k51 \le i < j < k \le 5 for which xi+xj+xkx_i + x_j + x_k divides SAS_A.
Find the largest possible value of TAT_A.

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

Official solution

1. Define the set and its properties:
Let A={x1,x2,x3,x4,x5} A = \{x_1, x_2, x_3, x_4, x_5\} be a set of five distinct positive integers. Denote by SA S_A the sum of its elements:
SA=x1+x2+x3+x4+x5 S_A = x_1 + x_2 + x_3 + x_4 + x_5
Denote by TA T_A the number of triples (i,j,k)(i, j, k) with 1i<j<k51 \le i < j < k \le 5 for which xi+xj+xkx_i + x_j + x_k divides SAS_A.

2. Calculate the number of possible triples:
The number of ways to choose 3 elements out of 5 is given by the binomial coefficient:
(53)=10 \binom{5}{3} = 10
Therefore, there are 10 possible triples (i,j,k)(i, j, k).

3. Example with specific values:
Consider the set A={1,2,3,4,494} A = \{1, 2, 3, 4, 494\} :
SA=1+2+3+4+494=504 S_A = 1 + 2 + 3 + 4 + 494 = 504
We need to check which triples (i,j,k)(i, j, k) satisfy the condition that xi+xj+xkx_i + x_j + x_k divides SAS_A.

4. Check each triple:
- For (1,2,3)(1, 2, 3):
x1+x2+x3=1+2+3=6and504÷6=84(divides) x_1 + x_2 + x_3 = 1 + 2 + 3 = 6 \quad \text{and} \quad 504 \div 6 = 84 \quad \text{(divides)}
- For (1,2,4)(1, 2, 4):
x1+x2+x4=1+2+4=7and504÷7=72(divides) x_1 + x_2 + x_4 = 1 + 2 + 4 = 7 \quad \text{and} \quad 504 \div 7 = 72 \quad \text{(divides)}
- For (1,2,5)(1, 2, 5):
x1+x2+x5=1+2+494=497and504÷497(does not divide) x_1 + x_2 + x_5 = 1 + 2 + 494 = 497 \quad \text{and} \quad 504 \div 497 \quad \text{(does not divide)}
- For (1,3,4)(1, 3, 4):
x1+x3+x4=1+3+4=8and504÷8=63(divides) x_1 + x_3 + x_4 = 1 + 3 + 4 = 8 \quad \text{and} \quad 504 \div 8 = 63 \quad \text{(divides)}
- For (1,3,5)(1, 3, 5):
x1+x3+x5=1+3+494=498and504÷498(does not divide) x_1 + x_3 + x_5 = 1 + 3 + 494 = 498 \quad \text{and} \quad 504 \div 498 \quad \text{(does not divide)}
- For (1,4,5)(1, 4, 5):
x1+x4+x5=1+4+494=499and504÷499(does not divide) x_1 + x_4 + x_5 = 1 + 4 + 494 = 499 \quad \text{and} \quad 504 \div 499 \quad \text{(does not divide)}
- For (2,3,4)(2, 3, 4):
x2+x3+x4=2+3+4=9and504÷9=56(divides) x_2 + x_3 + x_4 = 2 + 3 + 4 = 9 \quad \text{and} \quad 504 \div 9 = 56 \quad \text{(divides)}
- For (2,3,5)(2, 3, 5):
x2+x3+x5=2+3+494=499and504÷499(does not divide) x_2 + x_3 + x_5 = 2 + 3 + 494 = 499 \quad \text{and} \quad 504 \div 499 \quad \text{(does not divide)}
- For (2,4,5)(2, 4, 5):
x2+x4+x5=2+4+494=500and504÷500(does not divide) x_2 + x_4 + x_5 = 2 + 4 + 494 = 500 \quad \text{and} \quad 504 \div 500 \quad \text{(does not divide)}
- For (3,4,5)(3, 4, 5):
x3+x4+x5=3+4+494=501and504÷501(does not divide) x_3 + x_4 + x_5 = 3 + 4 + 494 = 501 \quad \text{and} \quad 504 \div 501 \quad \text{(does not divide)}

5. Count the valid triples:
The valid triples are (1,2,3)(1, 2, 3), (1,2,4)(1, 2, 4), (1,3,4)(1, 3, 4), and (2,3,4)(2, 3, 4). Thus, there are 4 valid triples.

Conclusion:
4 \boxed{4}

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