USAMTS Problem
Each member of the sequence 112002, 11210, 1121, 117, 46, 34, … is obtained by adding five times the rightmost digit to the number formed by omitting that digit. Determine the billionth (109) member of this sequence.
Writing a term as 10a + b (0 <
b < 9) we see the next term
will be a + 5b. The difference is 9a 4b. So,
we see that:
if a > 4, then the next term will be smaller than the previous.
Once the term is less than 50, the following term(s) will remain less than 50.
Thus the sequence will repeat after a term becomes less than 50.
Starting from term 1, we have:
|
Term # |
Value |
Term # |
Value |
|
1 |
112002 |
25 |
30 |
|
2 |
11210 |
26 |
03 |
|
3 |
1121 |
27 |
15 |
|
4 |
117 |
28 |
26 |
|
5 |
46 |
29 |
32 |
|
6 |
34 |
30 |
13 |
|
7 |
23 |
31 |
16 |
|
8 |
17 |
32 |
31 |
|
9 |
36 |
33 |
08 |
|
10 |
33 |
34 |
40 |
|
11 |
18 |
35 |
04 |
|
12 |
41 |
36 |
20 |
|
13 |
09 |
37 |
02 |
|
14 |
45 |
38 |
10 |
|
15 |
29 |
39 |
01 |
|
16 |
47 |
40 |
05 |
|
17 |
39 |
41 |
25 |
|
18 |
48 |
42 |
27 |
|
19 |
44 |
43 (1*) |
37 |
|
20 |
24 |
44 (2*) |
38 |
|
21 |
22 |
45 (3*) |
43 |
|
22 |
12 |
46 (4*) |
19 |
|
23 |
11 |
47 (5) |
46 |
|
24 |
06 |
48 (6) |
34 |
As we can see from the above table, excluding the first four terms, the sequence repeats every 42 terms. After the first “cycle”, the sequence repeats with first four terms 37, 38, 43, 19, … and then continues with the same following 38 terms as the first cycle.
We want to find what term in the cycle that term 109 corresponds to.
109 ≡ 34 (mod 42)
So, term 109 corresponds to term 34 in the repeating sequence.
Term 109 = Term 34 = 40
USAMTS Problem 2/2/14
The integer 72 is the first of three consecutive integers 72, 73, and 74, that can each be expressed as the sum of the squar es of two positive integers. The integers 72, 288, and 800 are the first three members of an infinite increasing sequence of integers with the above property. Find a function that generates the sequence and give the next three members.
Writing {72, 73, 74}, {288, 289, 300}, and {800, 801, 802} as the sums of two squares, we have:
72 = 62 + 62
73 = 32 + 82
74 = 52 + 72
288 = 122 + 122
289 = 82 + 152
290 = 112 + 132
800 = 202 + 202
801 = 152 + 242
802 = 192 + 212
Let us take n to be any positive integer. We see that:
2n2 = n2 + n2
and
2n2 + 2 =
(n + 1)2 + (n 1)2
Thus, for any m = 2n2 we see that both m and m + 2 can be written as the sum of two squares.
If n itself is k(k + 1) (with k being an integer greater than 1), then
m + 1 = 2n2 + 1 = 2(k(k + 1))2 + 1
= (2k2 + 2k)2 + 1
= (k2 1)2 + (k2 + 2k)2
Thus m + 1 can be written as the sum of two squares.
So, for m = 2(k(k + 1))2 will give succeeding terms in the above described sequence, starting with k > 1 (k = 2)
Taking k = 2, we have:
2(2 × 3)2 = 72 = 62 + 62
2(2 × 3)2 + 1 = 73 = 32 + 82
2(2 × 3)2 + 2 = 74 = 52 + 72
When k = 3,
2(3 × 4)2 = 288 = 122 + 122
2(3 × 4)2 + 1 = 289 = 82 + 152
2(3 × 4)2 + 2 = 290 = 112 + 132
When k = 4,
2(4 × 5)2 = 800 = 202 + 202
2(4 × 5)2 + 1 = 801 = 152 + 242
2(4 × 5)2 + 2 = 802 = 192 + 212
When k = 5,
2(5 × 6)2 = 1800 = 302 + 302
2(5 × 6)2 + 1 = 1801 = 242 + 352
2(5 × 6)2 + 2 = 1802 = 292 + 312
When k = 6,
2(6 × 7)2 = 3528 = 422 + 422
2(6 × 7)2 + 1 = 3529 = 352 + 482
2(6 × 7)2 + 2 = 3530 = 412 + 432
When k = 7,
2(7 × 8)2 = 6272 = 562 + 562
2(7 × 8)2 + 1 = 6273 = 482 + 632
2(7 × 8)2 + 2 = 6274 = 552 + 572
So, the first six terms of this sequence are {72, 288, 800, 1800, 3528, 6272, …}
A term a is 2(k(k + 1))2, where k = a + 1;
so, a term a in this sequence is
2((a + 1)(a + 2))2
(Note: Although this formula will always produce three consecutive numbers that can be written as the sum of two squares, it does not generate all the numbers with this property.)
USAMTS Problem
An integer lattice point in the Cartesian plane is a point (x, y) where x and y are both integers. Suppose nine integer lattice points are chosen such that no three of them lie on the same line. Out of all 36 possible line segments between pairs of those nine points, some line segments may contain integer lattice points besides the original nine points. What is the minimum number of line segments that must contain an integer lattice point besides the original nine points? Prove your answer.
We define a “good” line segment as one that contains no integer lattice points other than its two endpoints, and a “bad” segment as one that contains integer lattice points other than endpoints.
A line segment with
endpoints (x1, y1) and (x2, y2) is a “good” segment if and
have no common factors other than 1.
Now, if we take a point (x, y), it’s coordinates can be such that:
x is even and y is even (E, E)
x is even and y is odd (E, O)
x is odd and y is even (O, E)
x is odd and y is odd (O, O)
(E and O denote “even” and “odd”, respectively. We define a point’s coordinates in terms of evenness or oddness as the point’s “even/odd coordinate type”.)
Two points with the same even/odd coordinate type will form a bad line because the difference of even numbers is even, and the difference of two odd numbers is even. That is,
and
are always even.
So, for two points of the
same even/odd coordinate type, and
will always have a common factor of two.
By the pigeonhole principle, there must be at least one even/odd coordinate type with three or more points as members because there are 9 points and only 4 even/odd coordinate types. Two points with the same even/odd coordinate type result in 1 bad line; three points result in 3, and four points result in 6. If we have one coordinate type with three points and three with two, we have a total of 6 bad lines. If we have even one coordinate type with four points, this alone results in six bad lines. Thus, to keep a minimum of bad lines, it is best to “spread” the points across the coordinate types as evenly as possible so that we only have one coordinate type with three members and thus only six bad lines total.
If we take point 1(E, E), point 2(E, O), point 3(O, E), and point 4(O, O), any other points must have the same even/odd coordinate type as one of the first four. So, taking point
5(E, E), point 6(E, O), point 7(O, E), and point 8(O, O), we have one bad line between each pair of points with the same coordinate type. Point 9 must have the same even/odd coordinate type as two other points. Let us take point 9(E, E)
Now, points 1, 5, and 9 have the same even/odd
coordinate type
3 bad lines
points 2 and 6 have the same even/odd coordinate type
1 bad line
points 3 and 7 have the same even/odd coordinate type
1 bad line
points 4 and 8 have the same even/odd coordinate type
1 bad line
This results in a minimum total of: 6 bad lines
Below is an example of 9 points forming 6 bad lines. In this case, we are taking
point 1(0, 0), point 2(6, 1), point 3(3, 2), point 4(1, 3), point 5(4, 4), point 6(10, 11),
point 7(5, 12), point 8(11, 7), and point 9(2, 8). Bad lines are shown in black. Note that there is 1 bad line between pairs of points with the same even/odd coordinate type (pairs 2 and 6, 3 and 7, and 4 and 8), and there are 3 bad lines between the triplet of points with the same even/odd coordinate type (pts. 1, 5, and 9).
We have proved that there must be at least 6 bad line segments, and given an example that shows this situation.
USAMTS Problem
Let f(n) be the number of ones that occur in the decimal representations of all the numbers from 1 to n. For example, this gives f(8) = 1, f(10) = 2, f(11) = 4, and f(12) = 5. Determine the value of f(10100).
Taking f(x) for some
values of x of the form 10n 1, we have:
f(9) = 1
f(99) = 10 + 10 = 20
f(999) = 100 + 100 + 100 = 300
It is easy to see that, if
x = 10n 1 (x is
n digits long), there are
ones in the first position,
ones in the second, and so on. (If we take all numbers from 0 to 10n
1 as n-digit
numbers, left justifying by zeroes when needed, there are 10n total possibilities, one tenth of which are ones.)
So,
,
or
Now,
f(10n) = n(10n 1)
+ 1 (there
is exactly one “1” in 10n)
So, for n = 100,
f(10100) =
100(10100 1) + 1
= (102 )(1099) + 1
= 10101 + 1
USAMTS Problem 5/2/14
For an isosceles triangle ABC where AB = AC, it is possible to construct, using only compass and straightedge, an isosceles triangle PQR where PQ = PR such that triangle PQR is similar to triangle ABC, point P is in the interior of line segment AC, point Q is in the interior of line segment AB, and point R is in the interior of line segment BC. Describe one method of performing such a construction. Your method should work on every isosceles triangle ABC, except that you may choose an upper limit or lower limit on the size of angle BAC.
Given a triangle ABC, with ,
let us select point
R on BC and point P
on AC such that, for a given k,
Join points P and R, and
draw a segment from point R to a
point Q on AB such that .
Now, taking triangles QBR and RCP, we
will show that they
are similar:
,
and
(because
,
and
.)
So, .
So, .
and .
Hence, .
Taking triangles PQR and ABC,
and
.
Thus, .
When k = ,
we obtain the construction shown below:
This construction will work for all triangles ABC where
(As approaches 90,
approaches 0; for proof, see Appendix.)
The construction for when k = is shown below:
This construction works
for all triangles ABC where .
(As approaches 120,
approaches 0; for proof, see Appendix.)
When k > (obviously, k is less than 1), this construction will work for any value of
.
(0 <
< 180) (Again, for proof, see Appendix.)
Construction following the above method is simple;
· Find points P and R (using method 9: partitioning)
· Join PR (using method 2: line)
· Copy angle BAC to angle RPQ (using method 7: angle)
Appendix: Valid values of k for a given angle BAC
Since ,
.
So,
So,
For the construction to
work, must be less than 1.
We get
When k = ,
must be less than
. This is true for all angles BAC where
.
When k = ,
must be less than
. This is true for all angles BAC where
.
When k = ,
must be less than 2. However,
is always less than 2. Thus,
using k = we can construct a similar triangle PQR for any triangle ABC.