Putnam preparation (Table of contents)

Mathematical Induction

Problem 1 Prove that \(\displaystyle 1^3+2^3+3^3+\cdots+ n^3=\frac{n^2(n+1)^2}4\).

Problem 2 Determine the maximal possible number of regions in which the plane can be partitioned with \(n\) lines.

Problem 3

Given \(3n\) points \(A_1,A_2,\dots,A_{3n}\) in the plane, assume that no three of them collinear. Prove that it is possible to construct \(n\) disjoint triangles with vertices at the points \(A_i\).

Problem 4 Find all positive integers \(n\) such that \(\displaystyle 5^n > n!\).

Problem 5

Consider the polynomial \(p(x)=a_0x^k+a_1x^{k-1}+\dots+ a_k\) with integer coefficients. The polynomial \(p\) is said to be divisible by an integer \(m\) if \(p(x)\) is divisible by \(m\) for all integers \(x\). Prove that if \(p(x)\) is divisible by \(m\), then \(k!a_0\) is also divisible by \(m\).

Problem 6

Prove that for every positive integer \(n\) there exist positive integers \(a_{11}\), \(a_{21}\), \(a_{22}\), \(a_{31}\), \(a_{32}\), \(a_{33}\), \(\dots\), \(a_{n1}\), \(a_{n2}\), \(\dots\), \(a_{nn}\) such that \[a_{11}^2=a_{21}^2+a_{22}^2=a_{31}^2+a_{32}^2+a_{33}^2=\cdots=a_{n1}^2+\cdots+a_{nn}^2.\]

Problem 7

Consider the set \(\mathcal F\) of all injective functions \(f:\mathbb N\to\mathbb N\) that satisfy \[f(2x)+f(x)f(y)=f(x\cdot y)+2f(x),\;\;\mbox{for all }x,y\in\mathbb N.\] Determine \(\displaystyle\min_{f\in\mathcal F}\left\{f(2012)\right\}.\)

Problem 8

The sequence \((a_n)_{n=1}^{\infty}\) is defined as \(a_0=2\), \(a_1=\frac52\), and \(a_{n+1}=a_n(a_{n-1}^2-2)-\frac52\), for \(n\geq 1\). Prove that \[3\log_2{[a_n]}=2^n-(-1)^n,\] where \([x]\) is the integral part of \(x\).