Arithmetic Puzzles 01

Here are a small collection of technical puzzles that I find interesting. The answers to some of them may elude me from time to time. Their appeal to me lies in the fact that one can spend MANY hours on them and get nowhere. Sometimes the solution is elegent and sometimes ugly, so as Erdos would say, if you have a "book" proof for some of these problems, please do tell.

1. A Trig Inequality: Cos(Sin x) > Sin(Cos x)

2. The Monotonic Subsequence: Consider any permutaiton of {1,2,...n^2+1}. There must exist a monotonic sub-sequence of size at least n+1.

3. A Probability Problem: Let X and Y be two independent identically distributed real random variables. Show that
P[X-Y<=2]<= 3 P[X-Y<=1]

4. Divisors:

a} How many numbers less than 1000 are not divisible by 3 or 5 or 7? Generalize.

b}How many divisors does 9112001 have (including 1 and 9112001) and what is the sum of all these divisors?

5. Co-Prime Probability: Given two positive numbers, what is the probability that they are relatively prime? (Assume a uniform distribution) Generalize to K numbers.

6. A Line Through 2 Points: Given any set of greater than 2 points on the plane, not all on a line, there is at least one line that passes through exactly two points.

7. Matching the Hats: 100 coats are randomly distributed to 100 owners. What is the probability that at least one owner gets his own coat?

8. Betting the Deck: A deck has 26 red and black cards. A red card rewards you $1, and a black card fines you $1. You draw cards one by one, and may stop whenever you wish. What is your optimal strategy?

9. If x is a positive rational number, show that x^x is irrational unless x is an integer.

10. Let H(n) = 1/1 + 1/2 + ... + 1/n. Show that, for n > 1, H(n) is not an integer.