Maths Olympiad Prep

Track / Stage 7 / 227 of 300 #1627 of 1964

Problem 1627

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.5 Find the answer

Define an ordered quadruple of integers (a,b,c,d)(a, b, c, d) as interesting if 1a<b<c<d101 \le a<b<c<d \le 10, and a+d>b+ca+d>b+c. How many ordered quadruples are there?

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

To solve the problem, we need to count the number of ordered quadruples (a,b,c,d)(a, b, c, d) such that 1a<b<c<d101 \le a < b < c < d \le 10 and a+d>b+ca + d > b + c. We can reframe the condition a+d>b+ca + d > b + c as dc>bad - c > b - a. We will break this into cases based on the value of dcd - c.

### Case 1: dc=2d - c = 2
For dc=2d - c = 2, we need ba<2b - a < 2. This means ba=1b - a = 1.

- If (a,b)=(1,2)(a, b) = (1, 2), then cc and dd can be (3,5),(4,6),(5,7),(6,8),(7,9),(8,10)(3, 5), (4, 6), (5, 7), (6, 8), (7, 9), (8, 10). This gives 6 pairs.
- If (a,b)=(2,3)(a, b) = (2, 3), then cc and dd can be (4,6),(5,7),(6,8),(7,9),(8,10)(4, 6), (5, 7), (6, 8), (7, 9), (8, 10). This gives 5 pairs.
- If (a,b)=(3,4)(a, b) = (3, 4), then cc and dd can be (5,7),(6,8),(7,9),(8,10)(5, 7), (6, 8), (7, 9), (8, 10). This gives 4 pairs.
- If (a,b)=(4,5)(a, b) = (4, 5), then cc and dd can be (6,8),(7,9),(8,10)(6, 8), (7, 9), (8, 10). This gives 3 pairs.
- If (a,b)=(5,6)(a, b) = (5, 6), then cc and dd can be (7,9),(8,10)(7, 9), (8, 10). This gives 2 pairs.
- If (a,b)=(6,7)(a, b) = (6, 7), then cc and dd can be (8,10)(8, 10). This gives 1 pair.

Total for dc=2d - c = 2 is 6+5+4+3+2+1=216 + 5 + 4 + 3 + 2 + 1 = 21.

### Case 2: dc=3d - c = 3
For dc=3d - c = 3, we need ba<3b - a < 3. This means ba=1b - a = 1 or ba=2b - a = 2.

- For ba=1b - a = 1:
- If (a,b)=(1,2)(a, b) = (1, 2), then cc and dd can be (3,6),(4,7),(5,8),(6,9),(7,10)(3, 6), (4, 7), (5, 8), (6, 9), (7, 10). This gives 5 pairs.
- If (a,b)=(2,3)(a, b) = (2, 3), then cc and dd can be (4,7),(5,8),(6,9),(7,10)(4, 7), (5, 8), (6, 9), (7, 10). This gives 4 pairs.
- If (a,b)=(3,4)(a, b) = (3, 4), then cc and dd can be (5,8),(6,9),(7,10)(5, 8), (6, 9), (7, 10). This gives 3 pairs.
- If (a,b)=(4,5)(a, b) = (4, 5), then cc and dd can be (6,9),(7,10)(6, 9), (7, 10). This gives 2 pairs.
- If (a,b)=(5,6)(a, b) = (5, 6), then cc and dd can be (7,10)(7, 10). This gives 1 pair.

Total for ba=1b - a = 1 is 5+4+3+2+1=155 + 4 + 3 + 2 + 1 = 15.

- For ba=2b - a = 2:
- If (a,b)=(1,3)(a, b) = (1, 3), then cc and dd can be (4,7),(5,8),(6,9),(7,10)(4, 7), (5, 8), (6, 9), (7, 10). This gives 4 pairs.
- If (a,b)=(2,4)(a, b) = (2, 4), then cc and dd can be (5,8),(6,9),(7,10)(5, 8), (6, 9), (7, 10). This gives 3 pairs.
- If (a,b)=(3,5)(a, b) = (3, 5), then cc and dd can be (6,9),(7,10)(6, 9), (7, 10). This gives 2 pairs.
- If (a,b)=(4,6)(a, b) = (4, 6), then cc and dd can be (7,10)(7, 10). This gives 1 pair.

Total for ba=2b - a = 2 is 4+3+2+1=104 + 3 + 2 + 1 = 10.

Total for dc=3d - c = 3 is 15+10=2515 + 10 = 25.

### Case 3: dc=4d - c = 4
For dc=4d - c = 4, we need ba<4b - a < 4. This means ba=1,2,3b - a = 1, 2, 3.

- For ba=1b - a = 1:
- If (a,b)=(1,2)(a, b) = (1, 2), then cc and dd can be (3,7),(4,8),(5,9),(6,10)(3, 7), (4, 8), (5, 9), (6, 10). This gives 4 pairs.
- If (a,b)=(2,3)(a, b) = (2, 3), then cc and dd can be (4,8),(5,9),(6,10)(4, 8), (5, 9), (6, 10). This gives 3 pairs.
- If (a,b)=(3,4)(a, b) = (3, 4), then cc and dd can be (5,9),(6,10)(5, 9), (6, 10). This gives 2 pairs.
- If (a,b)=(4,5)(a, b) = (4, 5), then cc and dd can be (6,10)(6, 10). This gives 1 pair.

Total for ba=1b - a = 1 is 4+3+2+1=104 + 3 + 2 + 1 = 10.

- For ba=2b - a = 2:
- If (a,b)=(1,3)(a, b) = (1, 3), then cc and dd can be (4,8),(5,9),(6,10)(4, 8), (5, 9), (6, 10). This gives 3 pairs.
- If (a,b)=(2,4)(a, b) = (2, 4), then cc and dd can be (5,9),(6,10)(5, 9), (6, 10). This gives 2 pairs.
- If (a,b)=(3,5)(a, b) = (3, 5), then cc and dd can be (6,10)(6, 10). This gives 1 pair.

Total for ba=2b - a = 2 is 3+2+1=63 + 2 + 1 = 6.

- For ba=3b - a = 3:
- If (a,b)=(1,4)(a, b) = (1, 4), then cc and dd can be (5,9),(6,10)(5, 9), (6, 10). This gives 2 pairs.
- If (a,b)=(2,5)(a, b) = (2, 5), then cc and dd can be (6,10)(6, 10). This gives 1 pair.

Total for ba=3b - a = 3 is 2+1=32 + 1 = 3.

Total for dc=4d - c = 4 is 10+6+3=1910 + 6 + 3 = 19.

### Case 4: dc=5d - c = 5
For dc=5d - c = 5, we need ba<5b - a < 5. This means ba=1,2,3,4b - a = 1, 2, 3, 4.

- For ba=1b - a = 1:
- If (a,b)=(1,2)(a, b) = (1, 2), then cc and dd can be (3,8),(4,9),(5,10)(3, 8), (4, 9), (5, 10). This gives 3 pairs.
- If (a,b)=(2,3)(a, b) = (2, 3), then cc and dd can be (4,9),(5,10)(4, 9), (5, 10). This gives 2 pairs.
- If (a,b)=(3,4)(a, b) = (3, 4), then cc and dd can be (5,10)(5, 10). This gives 1 pair.

Total for ba=1b - a = 1 is 3+2+1=63 + 2 + 1 = 6.

- For ba=2b - a = 2:
- If (a,b)=(1,3)(a, b) = (1, 3), then cc and dd can be (4,9),(5,10)(4, 9), (5, 10). This gives 2 pairs.
- If (a,b)=(2,4)(a, b) = (2, 4), then cc and dd can be (5,10)(5, 10). This gives 1 pair.

Total for ba=2b - a = 2 is 2+1=32 + 1 = 3.

- For ba=3b - a = 3:
- If (a,b)=(1,4)(a, b) = (1, 4), then cc and dd can be (5,10)(5, 10). This gives 1 pair.

Total for ba=3b - a = 3 is 11.

Total for dc=5d - c = 5 is 6+3+1=106 + 3 + 1 = 10.

### Case 5: dc=6d - c = 6
For dc=6d - c = 6, we need ba<6b - a < 6. This means ba=1,2,3,4,5b - a = 1, 2, 3, 4, 5.

- For ba=1b - a = 1:
- If (a,b)=(1,2)(a, b) = (1, 2), then cc and dd can be (3,9),(4,10)(3, 9), (4, 10). This gives 2 pairs.
- If (a,b)=(2,3)(a, b) = (2, 3), then cc and dd can be (4,10)(4, 10). This gives 1 pair.

Total for ba=1b - a = 1 is 2+1=32 + 1 = 3.

- For ba=2b - a = 2:
- If (a,b)=(1,3)(a, b) = (1, 3), then cc and dd can be (4,10)(4, 10). This gives 1 pair.

Total for ba=2b - a = 2 is 11.

Total for dc=6d - c = 6 is 3+1=43 + 1 = 4.

### Case 6: dc=7d - c = 7
For dc=7d - c = 7, we need ba<7b - a < 7. This means ba=1,2,3,4,5,6b - a = 1, 2, 3, 4, 5, 6.

- For ba=1b - a = 1:
- If (a,b)=(1,2)(a, b) = (1, 2), then cc and dd can be (3,10)(3, 10). This gives 1 pair.

Total for dc=7d - c = 7 is 11.

### Summing Up All Cases
Adding up all the cases, we get:
21+25+19+10+4+1=8021 + 25 + 19 + 10 + 4 + 1 = 80

The final answer is 80\boxed{80}

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