Somewhat Technical Puzzles

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. -MMI
  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. Condensing the Gaussian: Let X be a Gaussian random variable with mean 0 and variance 1. You can transmit its value to a friend, using one of 2 numbers that have to be predetermined (before seeing X). When the friend receives the transmission, she will assume that the transmitted value is the actual value of X. What two numbers will you choose so that the expected squared error incurred by the friend is minimized. Prove that your solution cannot be beaten.
  4. 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]

    I have managed to show P[|X-Y|<=2]<= 5 P[|X-Y|<=1], but the factor of 3 seems to have eluded me. This is problem number 2 in chapter 2 of the text "The Probabilistic Method" by N. Alon and J. H. Spencer, Wiley, 2000.

  5. Integer Representations: Here are some interesting ways to write some well known integers.
    \begin{displaymath} 1=\sqrt[3]{\frac{13\sqrt{3}}{36}+\frac{5}{8}}- \sqrt[3]{\fra... ...}{8}} \qquad 2=\sqrt[3]{6\sqrt{3}+10}- \sqrt[3]{6\sqrt{3}-10} \end{displaymath}

    More generally, for arbitrary c
    \begin{displaymath} 1=\sqrt[3]{\frac{1}{8}+\frac{c^2}{2}+\frac{c(4c^2+9)\sqrt{3}... ...qrt[3]{\frac{1}{8}+\frac{c^2}{2}-\frac{c(4c^2+9)\sqrt{3}}{36}} \end{displaymath}

  6. Divisors:
  7. Co-Prime Probability: Given two positive numbers, what is the probability that they are relatively prime? (Assume a uniform distribution) Generalize to K numbers.
  8. 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.
  9. Matching the Hats: 100 coats are randomly distributed to 100 owners. What is the probability that at least one owner gets his own coat?
  10. 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?
  11. : Let U be a perfect uniform random real number generator for the interval [0,1]. Suppose we independently sample N times from U. What is the probability that that at least one of the samples is a rational number. Clearly for any finite N, this probability must be zero. So the question is as follows. Let 0 < p < 1 be any fixed probability. Let N(p) be the "smallest" N such that if N samples are drawn, then the probability that at least one is rational is p.

    What is N(p) as a function of p?

    Here is a naive computer scientists argument that the answer to this question depends on the continuum hypothesis. Let a0 be aleph 0 and a1 be aleph 1. Treating a0 and a1 as algebraic quantities, suppose that a0 samples are drawn, then the probability that at least one is rational is

    1-(1-a0/a1)^(a0) - > 1-((1-a0/a1)^(a1/a0))^(a0^2/a1).

    Now suppose that a1 samples are drawn, then the probability that at least one is rational is

    1-(1-a0/a1)^(a1) - > 1-((1-a0/a1)^(a1/a0))^(a0).

    Since a0/a1 - > 0 lets postulate that (1-a0/a1)^(a1/a0) - > 1/e. Since a0^2/a1=0, the top expression is 0 and the bottom expression is 1. Thus, if N < = aleph 0 then p=0; if N > = aleph 1 then p=1. The only way to obtain 0 < p < 1 is if there is some cardinality between aleph 0 and aleph 1, i.e. the continuum hypothesis.

    So can someone put some beef into my argument or are my heuristics just plain false?

  12. : Here is a problem originaly (to the best of my knowledge) posed by Moorthy. Consider an m by n square lattice (i.e. a rectangle decomposed into mn unit squares). Color the vertices in this lattice using two colors in any way you like.

    Question: For a large enough lattice (m,n), no matter how you color the vertices, there is a set of four monochromatic vertices at the corners of a square (the square may be of any size)?

    The original motivation for this problem is to construct a misere game for two players who alternately color the vertices on a large enough grid. The loser is the first player to create such a monochromatic quadruplet.

  13. : If x is a positive rational number, show that x^x is irrational unless x is an integer.
  14. : Let H(n) = 1/1 + 1/2 + ... + 1/n. Show that, for n > 1, H(n) is not an integer.
  15. : Given any sequence of n integers, show that there exists a consecutive subsequence the sum of whose elements is a multiple of n. For example, in sequence {1,5,1,2} a consecutive subsequence with this property is the last three elements; in {1,-3,-7} it is simply the second element.
Email: magdon (at) rpi (dot) edu to get my solutions or to tell me of an extremely ingenious and short solution that you have found.

If you have puzzles that can be solved with some ingenious and creative trick, I would like to know of it!