Putnam preparation (Table of contents)

Practice Test 2

Problem 1

Determine all functions \(f: \mathbb{N} \to \mathbb{N}\) (where \(\mathbb{N}\) is the set of positive integers) such that \(f(4)=4\) and \[\frac{1}{f(1)f(2)} + \frac{1}{f(2)f(3)} + \cdots + \frac{1}{f(n)f(n+1)} = \frac{f(n)}{f(n+1)}.\]

Problem 2

Given \(n\) biased coins \(C_1\), \(C_2\), \(\dots\), \(C_n\), assume that the probability of getting heads when \(C_k\) is tossed is equal to \(\frac1{2k+1}\) for each \(k\). Find the probability of getting an odd number of heads when all these \(n\) coins are tossed.

Problem 3

Let \(N\) be the number of ordered pairs \((x,y)\) of integers such that \[x^2+xy+y^2\leq 2012.\] Prove that \(N\) is not divisible by \(3\).

Problem 4

Assume that \(P(x)=ax^4+bx^3+cx^2+dx+e\) is a polynomial of degree four with integer coefficients that has two roots \(x_1\) and \(x_2\) such that \[x_1+x_2\in\mathbb Q\setminus\left\{\frac{-b}{2a} \right\}.\] Prove that \(x_1x_2\in\mathbb Q\).

Problem 5

Let \(s:\mathbb C\to\mathbb C\) be defined as \[s(z)=\left\{\begin{array}{cc} z,& \mbox{ if Re }(z)\geq 0\newline -z,&\mbox{ if Re }(z) < 0.\end{array}\right.\] Given a complex number \(\gamma\), consider the sequence \((z_n)_{n=1}^{\infty}\) defined by \[z_1=\gamma\quad\quad\quad\mbox{ and }\quad\quad\quad z_{n+1}=s\left(z_n^2+z_n+1\right) \mbox{ for }n\geq 1.\] Determine all \(\gamma\in\mathbb C\) for which the sequence \((z_n)_{n=1}^{\infty}\) is periodic.

Problem 6

Numbers \(1\), \(2\), \(\dots\), \(2013^2\) are written in the cells of a \(2013\times 2013\) table. In each of the moves a player is allowed to perform one of the following transformations: Exchange places of any two rows, or any two columns; or reverse a row or a column. (When row or column is reversed, the first and the last entry exchange their positions, so do the second and second last, etc.) Is it possible that after finitely many moves arbitrary two numbers exchange their positions and no other number exchange its position?