Numbers and Sets - exercises for enthusiasts 1. W. T. G.

1. Let A be the sum of the digits of 4444^{4444}, and let B be the sum of the digits of A. What is the sum of the digits of B?

2. Let x_{1}, …, x_{n} be real numbers such that ∑_{i=1}^{n} x_{i} = 0 and ∑_{i=1}^{n} x_{i}^{2} = 1. How large can x_{1}x_{2} + x_{2}x_{3} + … + x_{n−1}x_{n} + x_{n}x_{1} be? (If you cannot solve this problem, try it for small values of n, or just experiment to see how large you can make the sum.)

3. Let R be a rectangle which can be divided into smaller rectangles, each of which has at least one side of integer length. Prove that R has at least one side of integer length.

4. Does there exist a real number c > 0 such that for every positive integer n it is possible to choose points (x_{1}, y_{1}), …, (x_{n}, y_{n}) in the unit square [0, 1]^{2} with the property that |x_{i} − x_{j}||y_{i} − y_{j}| ⩾ cn^{−1} whenever i ≠ j?

5. Does there exist a cycle in ℤ^{3} (i.e., a path consisting of line segments going from lattice point to neighbouring lattice point and ending up where it started - a lattice point being a point with integer coordinates) such that none of the projections in the x, y and z directions contains a cycle?

6. Let P_{1} and P_{2} be two polynomials that take the same set of values on the rationals (i.e., P_{1}(ℚ) and P_{2}(ℚ) are the same set). Prove that there are constants a and b such that P_{1}(x) = P_{2}(ax + b) for every x.

7. Let n be an even number and let A be a collection of subsets of the set {1, 2, …, n} with the property that whenever A, B ∈ A the size of A ∩ B is even (including when A = B). How many sets can A contain? How does your answer change if the sets themselves have even size but when A ≠ B the size of A ∩ B is odd?

8. For each i let [a_{i}, b_{i}] be a closed interval of positive real numbers. Suppose also that ∑_{i}(b_{i} − a_{i}) < ∞. (If you don’t know about infinite sums, you can replace this assumption by the equivalent hypothesis that there is a number C such that ∑_{i=1}^{n}(b_{i} − a_{i}) < C for every n.) Does it necessarily follow that there is a positive real number x such that nx lies outside all the intervals [a_{i}, b_{i}] for every positive integer n?

9. Define a function f : ℕ → ℕ by setting f(n) to be the smallest integer greater than n^{π}. (For example, since 10^{π} = 1385.4557..., f(10) = 1386.) Prove that there is a nontrivial solution of the equation f(x) + f(y) + f(z) + f(w) = f(a) + f(b) + f(c) + f(d) with x, y, z, w, a, b, c, d all at least 2003. +10. Each of n elderly dons knows a piece of gossip not known to any of the others. They communicate by telephone, and in each call the two dons concerned reveal to each other all the information they know so far. What is the smallest number of calls that can be made in such a way that, at the end, all the dons know all the gossip?