Assorted Problems

16 Prove that

$$1^3 + 2^3 + \ldots + n^3 = (1 + 2 + \ldots + n)^2$$

17 (Putnam 1973) Given an collection of $2n+1$ integers such that - if you remove any one of them, the remaining numbers may be divided into two sets of n integers with the same sum. Prove the numbers must all be equal. (Hint: Not inducting on $n$; actually, first show the numbers must be congruent mod 2)

18 Suppose $x$ is a real number and $x + \frac{1}{x}$ is an integer. Show that $x^n + \frac{1}{x^n}$ is also an integer for any positive integer $n$.

19 The Fermat numbers are defined as follows: $F_n = 2^{2^n} + 1$. Thus, $F_0 = 3$, $F_1 = 5$, $F_2 = 17$, etc. Show that the Fermat numbers are pairwise relatively prime (that is, greatest common divisor of any two distinct Fermat numbers is 1).

Induction may be relevant here in relating each Fermat number to the product of all the preceeding Fermat numbers. Note this is another proof of the infinitude of primes.

20 Prove that in any set of $2^{n+1} - 1$ integers, there is a subset of exactly $2^n$ of them whose sum is divisible by $2^n$.

21 (USAMO 1978) An integer will be called good if it can be written as the sum of positive integers (not necessarily distinct) the sum of whose reciprocals is 1. Given that the integers 33 through 73 are good, prove every integer greater than or equal to 33 is good.

22 Find all polynomials $P(x)$ that have the property: $x$ is rational if and only if $P(x)$ is rational.

23 Show that the geometric mean of $n$ positive numbers is always less than or equal to their arithmetic mean. (There are many ways to do this, but one way using induction involves first showing it when $n=1$, then show how the truth of the result for $n$ yields the truth of it for both $2n$ and $n-1$. Is this sufficient?)

24 (1971 Putnam, I think) Given that $q(x) = 3x^2 + 5x + 7$, find all polynomials $p(x)$ (with real coefficients) satisfying $p(0) = 0$ and $p(q(x)) = q(p(x))$ for all real $x$.

25 In any graph (with at least two vertices, and disallowing any edges that connect a vertex to itself), at least two vertices have the same number of edges. (in any group of people, at least two have the same number of friends, if friendship is interpreted as a symmetric, non-reflexive relationship).

26 (Bridges of Königsburg) In a connected graph, if two of the vertices have an odd number of edges and the rest have an even number of edges, it is possible to travel through the graph, using every edge exactly once.

(you can also do this if all the vertices have an even number of edges, and you'll end on the same vertex on which you began.)

27 For any prime $p$, and any integer $n \geq p$, show that ${n\choose p} \equiv \left\lfloor {n/p} \right\rfloor \bmod p$.

28 (Dutch-Flemish, 1996?- but older, and well-known) Given a finite collection of of sets, closed under union (that is, if $A$ and $B$ are sets belonging to the collection, then $A\cup B$ is also a set in the collection.) Prove or disprove: there exists an element $x$ that belongs to at least half the sets in the collection.

Hint: if there is any set with only 1 element in it, the proof is immediate.

29 Show that every integer $n$ may be written as $\pm 1^2 \pm 2^2 \pm 3^2 \ldots \pm k^2$ for some $k$ and some choice of either ``+'' or ``-'' for each term.

30 Prove Euler's Formula (Vertices + Faces - Edges = 2, for either polyhedron or connected planar graphs, suitably interpreted) using induction on number of faces. (The smallest case requires some clarification: it must have at least one vertex, but not necessarily any edges. Also, we need to accept that if there is only one face, the graph must be a tree, i.e. have no cycles.)

31 Prove Euler's Formula using induction on number of vertices. (contraction)

32 Prove Euler's Formula using induction on number of edges.

33 Using Euler's formula, prove that every planar graph must have at least one vertex that has at most five edges. Use this to show that it is possible to color the vertices of any planar graph using 6 colors so that no to vertices joined by an edge are the same color.

34 Evaluate:

$$\lim_{n \rightarrow \infty} \cos \frac{\pi}{2^2} \cdot \cos \frac{\pi}{2^3} \cdots \cos \frac{\pi}{2^n}$$