Olympiad Maths Prep

Track / Stage 6 / 151 of 400 #1151 of 2000

Problem 1151

National olympiad, first round
Combinatorics Difficulty 6.2 Find the answer

p1. Let A={(x,y)∣3x+5y≥15,x+y2≤25,x≥0,x,yA = \{(x, y)|3x + 5y\ge 15, x + y^2\le 25, x\ge 0, x, y integer numbers }\}. Find all pairs of (x,zx)∈A(x, zx)\in A provided that zz is non-zero integer.

p2. A shop owner wants to be able to weigh various kinds of weight objects (in natural numbers) with only 44 different weights.
(For example, if he has weights 1 1, 22, 55 and 1010. He can weighing 1 1 kg, 22 kg, 33 kg (1+2)(1 + 2), 4444 kg (5−1)(5 - 1), 55 kg, 66 kg, 77 kg, 8 8 kg, 99 kg (10−1)(10 - 1), 1010 kg, 1111 kg, 1212 kg, 1313 kg (10+1+2)(10 + 1 + 2), 1414 kg (10+5−1)(10 + 5 -1), 1515 kg, 1616 kg, 1717 kg and 1818 kg). If he wants to be able to weigh all the weight from 1 1 kg to 4040 kg, determine the four weights that he must have. Explain that your answer is correct.

p3. Given the following table.
[img]https://cdn.artofproblemsolving.com/attachments/d/8/4622407a72656efe77ccaf02cf353ef1bcfa28.png[/img]
Table 4×44\times 4 ​​is a combination of four smaller table sections of size 2×22\times 2.
This table will be filled with four consecutive integers such that:
∙\bullet The horizontal sum of the numbers in each row is 1010 .
∙\bullet The vertical sum of the numbers in each column is 1010
∙\bullet The sum of the four numbers in each part of 2×22\times 2 which is delimited by the line thickness is also equal to 1010.
Determine how many arrangements are possible.

p4. A sequence of real numbers is defined as following:
Un=arn−1U_n=ar^{n-1}, if n=4m−3n = 4m -3 or n=4m−2n = 4m - 2
Un=−arn−1U_n=- ar^{n-1}, if n=4m−1n = 4m - 1 or n=4mn = 4m, where a>0a > 0, r>0r > 0, and mm is a positive integer.
Prove that the sum of all the 1 1st to 20092009th terms is a(1+r−r2009+r2010)1+r2\frac{a(1+r-r^{2009}+r^{2010})}{1+r^2}

5. Cube ABCD.EFGHABCD.EFGH is cut into four parts by two planes. The first plane is parallel to side ABCDABCD and passes through the midpoint of edge BFBF. The sceond plane passes through the midpoints ABAB, ADAD, GHGH, and FGFG. Determine the ratio of the volumes of the smallest part to the largest part.

Official solution

To prove that the sum of the first 2009 terms of the sequence Un U_n is given by a(1+r−r2009+r2010)1+r2\frac{a(1+r-r^{2009}+r^{2010})}{1+r^2}, we will follow these steps:

1. **Redefine the sequence Un U_n based on the given conditions:**
Un={arn−1if n=4m−3 or n=4m−2,−arn−1if n=4m−1 or n=4m U_n = \begin{cases} ar^{n-1} & \text{if } n = 4m - 3 \text{ or } n = 4m - 2, \\ -ar^{n-1} & \text{if } n = 4m - 1 \text{ or } n = 4m \end{cases}
where m m is a positive integer.

2. Group the terms in sets of four:
Notice that every four terms form a pattern:
(ar4m−4,ar4m−3,−ar4m−2,−ar4m−1) (ar^{4m-4}, ar^{4m-3}, -ar^{4m-2}, -ar^{4m-1})
For example, the first four terms are:
(a,ar,−ar2,−ar3) (a, ar, -ar^2, -ar^3)
The next four terms are:
(ar4,ar5,−ar6,−ar7) (ar^4, ar^5, -ar^6, -ar^7)
And so on.

3. Sum the terms within each group of four:
The sum of each group of four terms is:
ar4m−4+ar4m−3−ar4m−2−ar4m−1 ar^{4m-4} + ar^{4m-3} - ar^{4m-2} - ar^{4m-1}
Factor out the common term ar4m−4 ar^{4m-4} :
ar4m−4(1+r−r2−r3) ar^{4m-4}(1 + r - r^2 - r^3)

4. Sum the series up to the 2008th term:
Since 2009 is not a multiple of 4, we need to handle the last term separately. The sum of the first 2008 terms can be written as:
S=∑m=1502ar4m−4(1+r−r2−r3) S = \sum_{m=1}^{502} ar^{4m-4}(1 + r - r^2 - r^3)
This is a geometric series with the common ratio r4 r^4 :
S=(1+r−r2−r3)∑m=0501ar4m S = (1 + r - r^2 - r^3) \sum_{m=0}^{501} ar^{4m}
The sum of the geometric series is:
∑m=0501ar4m=a1−(r4)5021−r4 \sum_{m=0}^{501} ar^{4m} = a \frac{1 - (r^4)^{502}}{1 - r^4}
Therefore:
S=a(1+r−r2−r3)1−r20081−r4 S = a(1 + r - r^2 - r^3) \frac{1 - r^{2008}}{1 - r^4}

5. Add the 2009th term:
The 2009th term is ar2008 ar^{2008} . So, the total sum Stotal S_{total} is:
Stotal=a(1+r−r2−r3)1−r20081−r4+ar2008 S_{total} = a(1 + r - r^2 - r^3) \frac{1 - r^{2008}}{1 - r^4} + ar^{2008}

6. Simplify the expression:
Combine the terms:
Stotal=a((1+r−r2−r3)(1−r2008)1−r4+r2008) S_{total} = a \left( \frac{(1 + r - r^2 - r^3)(1 - r^{2008})}{1 - r^4} + r^{2008} \right)
Simplify the numerator:
(1+r−r2−r3)(1−r2008)=1+r−r2−r3−r2008−r2009+r2010+r2011 (1 + r - r^2 - r^3)(1 - r^{2008}) = 1 + r - r^2 - r^3 - r^{2008} - r^{2009} + r^{2010} + r^{2011}
Therefore:
Stotal=a(1+r−r2−r3−r2008−r2009+r2010+r20111−r4+r2008) S_{total} = a \left( \frac{1 + r - r^2 - r^3 - r^{2008} - r^{2009} + r^{2010} + r^{2011}}{1 - r^4} + r^{2008} \right)
Combine the terms:
Stotal=a(1+r−r2009+r20101+r2) S_{total} = a \left( \frac{1 + r - r^{2009} + r^{2010}}{1 + r^2} \right)

Thus, the sum of the first 2009 terms is:
a(1+r−r2009+r2010)1+r2 \boxed{\frac{a(1 + r - r^{2009} + r^{2010})}{1 + r^2}}

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