Putnam preparation (Table of contents)

Practice Test 1

Problem 1

Let \(n\) and \(k\) be positive integers such that \(n > k\). Prove that the numbers \(\binom nk\), \(\binom{n+1}k\), \(\binom{n+2}k\), \(\dots\), \(\binom{n+k}k\) do not have a common factor greater than 1.

Problem 2

Prove that there exists a function \(f:\mathbb R\to\mathbb R\) and a sequence \((x_k)_{k=1}^{\infty}\) that satisfy the following relations: \begin{eqnarray*} &&\lim_{k\to\infty}x_k=+\infty,\\ &&\lim_{x\to+\infty}\frac{f(x)}{x}=+\infty, \mbox{ and }\\ &&\left|f(2x_k)-2f(x_k)\right|\leq 1. \end{eqnarray*}

Problem 3

Let \(n\) be a positive integer. Determine the largest integer \(k\) for which there exists a \(4n\times 4n\) matrix with \(0\) and \(1\) entries such that the following three conditions are satisfied:

  • (i) The sum of the numbers in each row is \(k\);

  • (ii) The sum of the numbers in each column is \(k\);

  • (iii) The product of numbers from any two adjacent cells is \(0\). (Two cells are adjacent if they share an edge or a corner.)

Problem 4 Assume that \(P\) is a polynomial with real coefficients such that \(P(x)\geq 0\) for all \(x\geq 0\). Prove that there are two polynomials \(A\) and \(B\) with real coefficients such that \[P(x)=A(x)^2+x\cdot B(x)^2.\]