Oct. 15

Virginia Tech Regional Math Contest: Saturday, Oct. 25. Location: Himes Hall, LSU.
You must be present promptly at 8:30 A.M., or you will not be able to enter the building.
Problem Solving Seminar - Fall 2014
Oct. 15
Useful facts:
• The prime factorization of the current year is 2014 = 2 · 19 · 53, and the previous year
was 2013 = 3 · 11 · 67.
• Fermat’s Little Theorem. If p is prime and a is any integer, then ap − a is a multiple
of p.
• For any integer n, its square can only have the following remainders:
0 or 1 when divided by 3;
0 or 1 when divided by 4;
0, 1, 4, 5, or 9 when divided by 10.
• Remember that calculators are not allowed on the Virginia Tech Contest or Putnam
Exam!
1. Observe that 492 = 2401, and so 492 − 1 = 2400, which ends with two zeros.
(a) Are there other integers n such that n2 − 1 ends with two zeros?
(b) Given any k ≥ 1, is there an integer n such that n2 − 1 ends with k zeros?
2. (a) Find the positive integer solutions (x, y, z) to
1 1 1
+ + = 1.
x y z
(b) Does your answer to (a) change if the solutions are allowed to include negative
integers?
(c) Find all integer solutions to
1 1
1
+ = .
x y
6
(d) If p is prime, how many integer solutions (x, y) are there to
1
1 1
+ = ?
x y
p
33
3. (a) What is the last digit of 33 ?
(b) What are the last two digits of 20142013 ?
4. (a) What is the remainder when 20142012 is divided by 2013?
(b) What is the remainder when 20122014 is divided by 2013?
(c) Prove that 105105 + 213213 is a multiple of 2014.
Hint: This is the same as saying that the expression is a multiple of each divisor
of 2014 – use the prime factorization.
5. Are there any perfect squares whose only digits are 0s and 6s?
6. (a) Show that if there is an integer solution to a2 + b2 = c2 , then at least one of a and
b is a multiple of 3.
(b) Show that there are no integer solutions to
3x2 + 7y 2 = 4z 2 − 3.
Hint: Consider the remainder when divided by 4.
(c) [Gelca-Andreescu 706] Show that there are no positive integer solutions to
x2 + 10y 2 = 3z 2 .
Hint: It is helpful to consider the equation modulo 3 or 10.
7. [VTRMC 1979 #5] Show, for all positive integers n = 1, 2, . . . , that 14 divides 34n+2 +
52n+1 .
8. [Putnam 1979 A1] Find the set of positive integers with sum 1979 and maximum
possible product.
Extra challenge: Can you also answer this question for 2014?
n
9. (a) Prove that if n is odd, then 1010 + 10n is a multiple of 11.
10
(b) Prove that 1010 + 1010 is not a multiple of 11, but it is a multiple of 101.
10. [Putnam 2010 A4] Prove that for each positive integer n, the number
1010
10n
n
+ 1010 + 10n − 1
is not prime.
Challenge.
1. (a) In a certain country postage stamps are sold in two denominations: 5 cents and
12 cents. The first-class postage rate has risen in recent years from 25 to 29
cents, then 34, and finally 37 cents. Show how each of these values can be exactly
achieved with some combination of stamps.
(b) The most recent proposal called for a rise to 43 cents until an observant mathematician pointed out that this value was impossible to achieve! The new rate was
instead set for 42 cents. Prove the claim, that 43 cents is impossible.
(c) Furthermore, prove that 43 cents is the largest impossible value, so that any rate
44 cents or higher can be achieved.
(d) Now consider the general problem: the postage stamps are available in a cents
and b cents, where a and b have no common divisors (why?). What is the largest
postage rate that cannot be made exactly with the available stamps? Prove that
all larger values can be achieved.