USAMTS Problem 1/1/15

 

Let f(x) =  for all real numbers x, where for any real number r,  means the greatest integer less than or equal to r.  For example,
 f(π) = 3 + 31 + 314 + 3141 = 3489.  Find, with proof, a positive integer n less than 2003 such that f(x) = n has no solution for x, but f(y) = n + 11 and f(z) = n + 111 have solutions for y and z.

 

For any given real number x, let

 

 

a, b, c, and d are all integers, with b, c, and d greater than or equal to 0 and less than or equal to 9.

 

(When x is written in decimal form, a is the whole number to the left of the decimal point, and b, c, and d are the first three digits to the right of the decimal point.)

 

(We  can show  that b, c, and d are nonnegative integers less than or equal to 9  

If we let , then 0 < z < 1.

, so 0 < b < 9.  The same is true for c and d.)

 

From the above definition, 

     f(x)              

 

 

So, f(x) = n  n = 1111a + 111b + 11c + d.

 

Theorem:

Any integer n can be written as  for a unique integer set {p, r, t, u}, where:

 

 

In addition, when t = 10, u must equal 0,

and when r = 10, t and u must both equal 0.

 

            Proof:

 

We divide n by 1111, and let p be the quotient and q be the remainder:

n = 1111p + q              (0 < q < 1111)

 

We divide q by 111, and let r be the quotient and s be the remainder:

q = 111r + s                 (0 < s < 111, and 0 < r < 10; if r = 10, then s = 0)

 

Again, we divide s by 11, and let t be the quotient and u be the remainder:

s = 11t + u                   (0 < u < 11, and 0 < t < 10; if t = 10, then u = 0)        

 

So, .

 

 

For f(x) = n to have no solution, one of {r, t, u} must equal 10. 

The corresponding value from {b, c, d} will then not exist.

 

There are three such possible cases:

(1)   r = 10              (In this case, t = u = 0)

(2)   t = 10               (In this case, u = 0, and r is some value between 0 and 9)

(3)   u = 10              (Both r and t are some value between 0 and 9)

 

We want to find a value for n such that f(x) = n has no solution,

but f(y) = n + 11 and f(z) = n + 111 both have solutions.

 

 

For case (1), we have

n = 1111p + 111(10) = 1111p + 1110

So,

n + 11 = 1111p + 1221

            = 1111(p + 1) + 110

            = 1111(p + 1) + 11(10)

That is, in this case we get  t = 10.  Therefore, f(y) = n + 11, too, has no solution.

Case (1) does not satisfy the requirements specified by the problem.

 

For (2), we have

n = 1111p + 111r + 11(10) = 1111p + 111r + 110

So,

n + 11 = 1111p + 111r + 121

            = 1111p + 111(r + 1) + 10

That is, in this case u = 10.  Therefore, f(y) = n + 11 has no solution.

Case (2) does not satisfy the requirements specified by the problem.

 

For (3), we have

n = 1111p + 111r + 11t + 10

So,

n + 11 = 1111p + 111r + 11t + 21

            = 1111p + 111r + 11(t + 1) + 10

 

If 1 < t < 8,

then u = 10 and f(y) = n + 11 has no solution.

 

However, if t = 9, we have:

n + 11 = 1111p + 111r + 99 + 21

            = 1111p + 111r + 120

            = 1111p + 111(r + 1) + 9

We have a valid solution for f(y) = n + 11 for n where u = 10 and t = 9.

 

Also for (3), we have

n + 111 = 1111p + 111r + 11t + 121

             = 1111p + 111(r + 1) + 11t + 10

 

If 1 < r < 8,

then u = 10, and f(z) = n + 111 has no solution.

 

However, if r = 9, we have:

n + 111 = 1111p + 999 + 11t + 121

             = 1111p + 11t + 1120

             = 1111(p + 1) + 11t + 9

We have a valid solution for f(z) = n + 111 for n where u = 10 and r = 9.

 

Therefore, in order to have a valid solution for f(y) = n + 11 and  f(z) = n + 111,

we must have n where:

u = 10

t = 9

r = 9

 

That is,        n   = 1111p + 999 + 99 + 10

                        = 1111p + 1108

 

When p < 0,

n < 1108  1111, that is, n < -3

However, n must be positive, so p must be greater than or equal to 0

 

When p = 0,

n = 1108;                     there is no solution for f(x) = 1108

n + 11 = 1119;             f(y) = 1119 when y = 1.008

n + 111 = 1219;           f(z) = 1219 when z = 1.099

 

n = 1108 is a solution.

 

When p > 1,

n > 1111 + 1108, that is, n > 2219

However, in this problem, n must be less than 2003.

 

Thus, n = 1108 is the only possible solution.

 

 

USAMTS Problem 2/1/15

 

Find all primes p for which 6p + 1 is the fifth power of an integer.  Prove that you found all of them.

 

,

so ,

where n is some integer.

 

We can factor n⁵  1 as .

 

So, .

Since the factors of 6 are {6, 3, 2, 1}, we have eight possible cases:

1.  
   

 

2.  
   

 

3.  
   

 

4.  
   

 

5.  
   

 

6. 
   
    

 

7.  
   

 

8.  
   

 

When n = 1, , and when n > 2,  .  So, cases 2, 4, 6, and 8 are impossible.

 

Taking case 1:

n  1 = 6, so n = 7, and , which is in fact prime.

 

For case 3, we have:  

n = 4, and p = 341 / 2, which is not prime.

Similarly, for case 5, we have:

n = 3, and p = 121 / 3 which is not prime,

and for case 7, we have:

n = 2, and p = 31 / 6, which is not prime.

 

Thus, the only case which satisfies the given conditions is case 1, where n = 7  and p = 2801.

 

USAMTS Problem 3/1/15

 

We attempted to arrange the integers 1, 2, 3, …, 12 around a circle so that all sums of pairs of adjacent integers are either:

a)      all perfect squares, or

b)      all triangular numbers, which are numbers of the form  n(n + 1) / 2.

One case out of (a) and (b) succeeded.  Which one?  For the successful case, show a valid arrangement.  For the unsuccessful case, explain why it is impossible.

 

The sum of two different integers between 1 and 12 must be greater than or
equal to 3 (= 1 + 2) and less than or equal to 23 (= 11 + 12).

 

Case (a)

 

The perfect squares between 3 and 23 are {4, 9, 16}.  In the list below are the possible integer pairs that can form perfect squares. 

 

1	3, 8
2	7
3	1, 6
4	5, 12
5	4, 11
6	3, 10
7	2, 9
8	1
9	7
10	6
11	5
12	4

 

We note that for 2 (or, in fact, 8, 9, 10, 11, and 12), there is only one other number that it can sum with to form a perfect square.

                                                                                                         

If these numbers were arranged in a circle, each number would have two numbers adjacent to it, and thus would require at least two different numbers that it could sum with to form a perfect square.  This is not the case; therefore, case (a) is impossible.

Case (b)

 

Now, the triangular numbers between 3 and 23 are {3, 6, 10, 15, 21}.  In the list below, we have the possible integer pairs that can form triangular numbers. 

 

1	2, 5, 9
2	1, 4, 8
3	7, 12
4	2, 6, 11
5	1, 10
6	4, 9
7	3, 8
8	2, 7
9	1, 6, 12
10	5, 11
11	4, 10
12	3, 9

 

Each number has at least two numbers with which it can sum to form a triangular number.  Furthermore, we can arrange these numbers in a circle so that adjacent numbers always sum to form triangular numbers. 

 

Let us start with 12: it must be adjacent to 3 and 9.

3 must be adjacent to 7.

7 must be adjacent to 8.

8 must be adjacent to 2.

So far, we have: (… 9, 12, 3, 7, 8, 2…)

12 must be adjacent to 9, and 6 must also be adjacent to 9, so 9 must lie between 12 and 6.

6 must be adjacent to 4, and 11 must also be adjacent to 4, so 4 must lie between 6 and 11.

So, we have: (… 11, 4, 6, 9, 12, 3, 7, 8, 2…)

11 must be adjacent to 10.

10 must be adjacent to 5.

5 must be adjacent to 1.

We have: (…1, 5, 10, 11, 4, 6, 9, 12, 3, 7, 8, 2…)

2 and 1 must be adjacent to one another.  The arrangement can now form a circle.  The arrangement is unique (ignoring inversion):

 

USAMTS Problem 4/1/15

 

Two players play a game.  Each player, in turn, has to name a positive integer that is less than the previous number but at least half the previous number.  The player who names the number 1 loses.  If the first player starts by naming 2003 and after that both players play with the best strategy, who wins?  Describe the strategy and prove it works.

 

We call a “winning number” any number which guarantees victory to the player who calls it. 

 

If we have a winning number n, then 2n + 1 will also be a winning number because naming “2n + 1” forces the opposing player to name a number m, where n < m < 2n + 1.  This means that the player who named “2n + 1” can always name n during his next turn, because n will be less than m, but greater than or equal to m / 2. 

 

The player who names 1 loses.  Therefore, 2 is a winning number, because the player who names 2 forces his opponent to name 1. 

 

If 2 is a winning number, then so is 2(2) + 1 = 5.  Recursively, we can continue finding a next-greatest winning number until we find the greatest one less than 2003.  This is shown in the table below:

 

n	2n + 1
2	5
5	11
11	23
23	47
47	95
95	191
191	383
383	767
767	1535
1535	3071

 

We find that 1535 is the greatest winning number less than 2003. 

 

If player 1 names 2003, then player 2 can name 1535 because 2003 /2 < 1535 < 2003.  1535 is a winning number.  Thus, as long as player 2 remembers his winning numbers, he will always win.

USAMTS Problem 5/1/15

 

A rectangular piece of paper, ABCD, is folded along line segment EF, where point E is on side AD and point F is on side BC, so that C ends up at the midpoint of side AB.  Determine the length of EF if the length of AB is 240 and the length of BC is 288.

 

 

 

 

 

Let point G lie on  such that  is perpendicular to ;

.

 

We will show that right triangle C’BC is similar to right triangle EGF, and thus calculate EF.

 

Let H be the intersection of  and .

 

 because they are symmetrical with respect to the fold line,

so  and  are perpendicular to each other.

 

 is a right triangle, so

 

 

Also,

 because  is perpendicular to , and thus also to .

 

Therefore,

, or equivalently

 

 

Taking  and , we have

 (both triangles are right triangles), and

.

 

Thus, .

 

 

 

BC = 288, and GF = AB = 240.

 

C’ is the midpoint of AB, so BC’ = 240 / 2 = 120.

 

So, , and GE = 100.

 

 

 is a right triangle, so

 

 

 EF = 260