ChristianZ97/putnambench-satp-v4.27 huggingface dataset:
Problem: putnam_2009_a5
Category: abstract_algebra

Is there a finite abelian group $G$ such that the product of the orders of all its elements is 2^{2009}?

Solution: Show that the answer is no such finite abelian group exists.

Lean 4 formalization:
import Mathlib

open Topology MvPolynomial Filter Set

abbrev putnam_2009_a5_solution : Prop := sorry
theorem putnam_2009_a5
: (∃ (G : Type*) (_ : CommGroup G) (_ : Fintype G), ∏ g : G, orderOf g = 2^2009) ↔ putnam_2009_a5_solution := by
Problem: putnam_2009_b1
Category: number_theory

Show that every positive rational number can be written as a quotient of products of factorails of (not necessarily distinct) primes. For example, 10/9 = (2! * 5!)/(3! * 3! * 3!).


Lean 4 formalization:
import Mathlib

open Topology MvPolynomial Filter Set

theorem putnam_2009_b1
(isquotprodprimefact : ℚ → Prop)
(hisquotprodprimefact : ∀ q, isquotprodprimefact q ↔
  (∃ (k m : ℕ) (a : Fin k → ℕ) (b : Fin m → ℕ),
    (∀ i : Fin k, Nat.Prime (a i)) ∧ (∀ j : Fin m, Nat.Prime (b j))
    ∧ (q = (∏ i : Fin k, Nat.factorial (a i))/(∏ j : Fin m, Nat.factorial (b j)))))
: ∀ q : ℚ, q > 0 → isquotprodprimefact q := by
Problem: putnam_2009_b2
Category: analysis, algebra

A game involves jumping to the right on the real number line. If $a$ and $b$ are real numbers and $b > a$, the cost of jumping from $a$ to $b$ is $b^3-ab^2$. For what real numbers $c$ can one travel from $0$ to $1$ in a finite number of jumps with total cost exactly $c$?

Solution: Prove that the possible costs are $1/3 < c \leq 1.$

Lean 4 formalization:
import Mathlib

open Topology MvPolynomial Filter Set

abbrev putnam_2009_b2_solution : Set ℝ := sorry
theorem putnam_2009_b2
: ({c : ℝ | ∃ s : ℕ → ℝ, s 0 = 0 ∧ StrictMono s ∧ (∃ n : ℕ, s n = 1 ∧ ((∑ i ∈ Finset.range n, ((s (i + 1)) ^ 3 - (s i) * (s (i + 1)) ^ 2)) = c))} = putnam_2009_b2_solution) := by
Problem: putnam_2009_b3
Category: number_theory

Call a subset $S$ of $\{1, 2, \dots, n\}$ \emph{mediocre} if it has the following property: Whenever $a$ and $b$ are elements of $S$ whose average is an integer, that average is also an element of $S$. Let $A(n)$ be the number of mediocre subsets of $\{1,2,\dots,n\}$. [For instance, every subset of $\{1,2,3\}$ except $\{1,3\}$ is mediocre, so $A(3) = 7$.] Find all positive integers $n$ such that $A(n+2) - 2A(n+1) + A(n) = 1$.

Solution: Show that the answer is $n = 2^k - 1$ for some integer $k$.

Lean 4 formalization:
import Mathlib

open Topology MvPolynomial Filter Set

abbrev putnam_2009_b3_solution : Set ℤ := sorry
theorem putnam_2009_b3
(mediocre : ℤ → Set ℤ → Prop)
(hmediocre : ∀ n S, mediocre n S ↔ (S ⊆ Icc 1 n) ∧ ∀ a ∈ S, ∀ b ∈ S, 2 ∣ a + b → (a + b) / 2 ∈ S)
(A : ℤ → ℤ)
(hA : A = fun n ↦ ({S : Set ℤ | mediocre n S}.ncard : ℤ))
: ({n : ℤ | n > 0 ∧ A (n + 2) - 2 * A (n + 1) + A n = 1} = putnam_2009_b3_solution) := by
Problem: putnam_2009_b4
Category: algebra, linear_algebra

Say that a polynomial with real coefficients in two variables, $x,y$, is \emph{balanced} if the average value of the polynomial on each circle centered at the origin is $0$. The balanced polynomials of degree at most $2009$ form a vector space $V$ over $\mathbb{R}$. Find the dimension of $V$.

Solution: Prove that the dimension of $V$ is $2020050$.

Lean 4 formalization:
import Mathlib

open intervalIntegral MvPolynomial Real

abbrev putnam_2009_b4_solution : ℕ := sorry
theorem putnam_2009_b4
    (IsBalanced : MvPolynomial (Fin 2) ℝ → Prop)
    (IsBalanced_def : ∀ P, IsBalanced P ↔ ∀ r > 0,
      (∫ t in (0 : ℝ)..(2 * π), eval ![r * cos t, r * sin t] P) / (2 * π * r) = 0)
    (V : Submodule ℝ (MvPolynomial (Fin 2) ℝ))
    (V_def : ∀ P, P ∈ V ↔ IsBalanced P ∧ P.totalDegree ≤ 2009) :
    Module.rank ℝ V = putnam_2009_b4_solution := by
Problem: putnam_2009_b5
Category: analysis

Let $f: (1, \infty) \to \mathbb{R}$ be a differentiable function such that
\[
 f'(x) = \frac{x^2 - f(x)^2}{x^2 (f(x)^2 + 1)}
\qquad \mbox{for all $x>1$.}
\]
Prove that $\lim_{x \to \infty} f(x) = \infty$.


Lean 4 formalization:
import Mathlib

open Topology MvPolynomial Filter Set Metric

theorem putnam_2009_b5
(f : ℝ → ℝ)
(hfdiff : DifferentiableOn ℝ f (Ioi 1))
(hf : ∀ x > 1, deriv f x = (x ^ 2 - (f x) ^ 2) / ((x ^ 2) * ((f x) ^ 2 + 1)))
: (Tendsto f atTop atTop) := by
Problem: putnam_2009_b6
Category: number_theory

Prove that for every positive integer $n$, there is a sequence of integers $a_0, a_1, \dots, a_{2009}$ with $a_0 = 0$ and $a_{2009} = n$ such that each term after $a_0$ is either an earlier term plus $2^k$ for some nonnegative integer $k$, or of the form $b\,\mathrm{mod}\,c$ for some earlier positive terms $b$ and $c$. [Here $b\,\mathrm{mod}\,c$ denotes the remainder when $b$ is divided by $c$, so $0 \leq (b\,\mathrm{mod}\,c) < c$.]


Lean 4 formalization:
import Mathlib

open Topology MvPolynomial Filter Set Metric

theorem putnam_2009_b6
  (n : ℕ) (npos : n > 0) :
  (∃ a : ℕ → ℤ,
    a 0 = 0 ∧ a 2009 = n ∧
    ∀ i : Icc 1 2009,
      ((∃ j k : ℕ, j < i ∧ a i = a j + 2 ^ k) ∨
      ∃ b c : ℕ, b < i ∧ c < i ∧ a b > 0 ∧ a c > 0 ∧ a i = (a b) % (a c))) := by
Problem: putnam_2010_a1
Category: algebra

Given a positive integer $n$, what is the largest $k$ such that the numbers $1,2,\dots,n$ can be put into $k$ boxes so that the sum of the numbers in each box is the same? [When $n=8$, the example $\{1,2,3,6\},\{4,8\},\{5,7\}$ shows that the largest $k$ is \emph{at least} $3$.]

Solution: Show that the largest such $k$ is $\lceil \frac{n}{2} \rceil$.

Lean 4 formalization:
import Mathlib

noncomputable abbrev putnam_2010_a1_solution : ℕ → ℕ := sorry
theorem putnam_2010_a1
    (n : ℕ)
    (kboxes : ℕ → Prop)
    (npos : n > 0)
    (hkboxes : ∀ k : ℕ, kboxes k =
      (∃ boxes : Finset.Icc 1 n → Fin k, ∀ i j : Fin k,
        ∑ x ∈ Finset.univ.filter (boxes · = i), (x : ℕ) =
        ∑ x ∈ Finset.univ.filter (boxes · = j), (x : ℕ))) :
    IsGreatest kboxes (putnam_2010_a1_solution n) := by
Problem: putnam_2010_a2
Category: analysis

Find all differentiable functions $f:\mathbb{R} \to \mathbb{R}$ such that
\[
f'(x) = \frac{f(x+n)-f(x)}{n}
\]
for all real numbers $x$ and all positive integers $n$.

Solution: The solution consists of all functions of the form $f(x) = cx+d$ for some real numbers $c,d$.

Lean 4 formalization:
import Mathlib

abbrev putnam_2010_a2_solution : Set (ℝ → ℝ) := sorry
theorem putnam_2010_a2
: {f : ℝ → ℝ | Differentiable ℝ f ∧
∀ x : ℝ, ∀ n : ℤ, n > 0 → deriv f x = (f (x + n) - f x)/n} = putnam_2010_a2_solution := by
Problem: putnam_2010_a3
Category: analysis

Suppose that the function $h : \mathbb{R}^2 → \mathbb{R}$ has continuous partial derivatives and satisfies the equation $h(x, y) = a \frac{\partial h}{\partial x}(x, y) +b \frac{\partial h}{\partial y}(x, y)$ for some constants $a, b$. Prove that if there is a constant $M$ such that $|h(x, y)| ≤ M$ for all $(x, y) ∈ \mathbb{R}^2$, then $h$ is identically zero.


Lean 4 formalization:
import Mathlib

theorem putnam_2010_a3
    (h : ℝ × ℝ → ℝ)
    (a b M : ℝ)
    (H : ContDiff ℝ 1 h)
    (H' : ∀ x, h x = a * (fderiv ℝ h x (1, 0)) + b * (fderiv ℝ h x (0, 1)))
    (H'' : ∀ x, |h x| ≤ M) : h = 0 := by
Problem: putnam_2010_a4
Category: number_theory

Prove that for each positive integer $n$, the number $10^{10^{10^n}} + 10^{10^n} + 10^n - 1$ is not prime.


Lean 4 formalization:
import Mathlib

theorem putnam_2010_a4
: ∀ n : ℕ, n > 0 → ¬Nat.Prime (10^10^10^n + 10^10^n + 10^n - 1) := by
Problem: putnam_2010_a5
Category: abstract_algebra, algebra

Let $G$ be a group, with operation $*$. Suppose that \begin{enumerate} \item[(i)] $G$ is a subset of $\mathbb{R}^3$ (but $*$ need not be related to addition of vectors); \item[(ii)] For each $\mathbf{a},\mathbf{b} \in G$, either $\mathbf{a}\times \mathbf{b} = \mathbf{a}*\mathbf{b}$ or $\mathbf{a}\times \mathbf{b} = 0$ (or both), where $\times$ is the usual cross product in $\mathbb{R}^3$. \end{enumerate} Prove that $\mathbf{a} \times \mathbf{b} = 0$ for all $\mathbf{a}, \mathbf{b} \in G$.


Lean 4 formalization:
import Mathlib

open scoped Matrix

theorem putnam_2010_a5
    (G : Type*) [Group G]
    (i : G ↪ (Fin 3 → ℝ))
    (h : ∀ a b, (i a) ⨯₃ (i b) = i (a * b) ∨ (i a) ⨯₃ (i b) = 0)
    (a b : G) :
    (i a) ⨯₃ (i b) = 0 := by
Problem: putnam_2010_a6
Category: analysis

Let $f:[0,\infty)\to \mathbb{R}$ be a strictly decreasing continuous function
such that $\lim_{x\to\infty} f(x) = 0$. Prove that
$\int_0^\infty \frac{f(x)-f(x+1)}{f(x)}\,dx$ diverges.


Lean 4 formalization:
import Mathlib

open Filter Topology Set

theorem putnam_2010_a6
(f : ℝ → ℝ)
(hf : (StrictAntiOn f (Ici 0) ∧ ContinuousOn f (Ici 0) ∧ Tendsto f atTop (𝓝 0)))
: ¬∃ y : ℝ, Tendsto (fun z : ℝ => ∫ x in Ico 0 z, ((f x) - f (x + 1))/(f x)) atTop (𝓝 y) := by
Problem: putnam_2010_b1
Category: analysis

Is there an infinite sequence of real numbers $a_1, a_2, a_3, \dots$ such that \[ a_1^m + a_2^m + a_3^m + \cdots = m \] for every positive integer $m$?

Solution: Show that the solution is no such infinite sequence exists.

Lean 4 formalization:
import Mathlib

open Filter Topology Set

abbrev putnam_2010_b1_solution : Prop := sorry
theorem putnam_2010_b1
: (∃ a : ℕ → ℝ, ∀ m : ℕ, m > 0 → ∑' i : ℕ, (a i)^m = m) ↔ putnam_2010_b1_solution := by
Problem: putnam_2010_b2
Category: geometry

Given that $A$, $B$, and $C$ are noncollinear points in the plane with integer coordinates such that the distances $AB$, $AC$, and $BC$ are integers, what is the smallest possible value of $AB$?

Solution: Show that the smallest distance is $3$.

Lean 4 formalization:
import Mathlib

open Filter Topology Set

abbrev putnam_2010_b2_solution : ℕ := sorry
theorem putnam_2010_b2
  (ABCintcoords ABCintdists ABCall: EuclideanSpace ℝ (Fin 2) → EuclideanSpace ℝ (Fin 2) → EuclideanSpace ℝ (Fin 2) → Prop)
  (hABCintcoords : ∀ A B C, ABCintcoords A B C ↔ (∀ i : Fin 2, A i = round (A i) ∧ B i = round (B i) ∧ C i = round (C i)))
  (hABCintdists : ∀ A B C, ABCintdists A B C ↔ (dist A B = round (dist A B) ∧ dist A C = round (dist A C) ∧ dist B C = round (dist B C)))
  (hABCall : ∀ A B C, ABCall A B C ↔ (¬Collinear ℝ {A, B, C} ∧ ABCintcoords A B C ∧ ABCintdists A B C)) :
  IsLeast {y | ∃ A B C, ABCall A B C ∧ y = dist A B} putnam_2010_b2_solution := by
Problem: putnam_2010_b3
Category: analysis

There are $2010$ boxes labeled $B_1, B_2, \dots, B_{2010}$, and $2010n$ balls have been distributed among them, for some positive integer $n$. You may redistribute the balls by a sequence of moves, each of which consists of choosing an $i$ and moving \emph{exactly} $i$ balls from box $B_i$ into any one other box. For which values of $n$ is it possible to reach the distribution with exactly $n$ balls in each box, regardless of the initial distribution of balls?

Solution: Prove that it is possible if and only if $n \geq 1005$.

Lean 4 formalization:
import Mathlib

open Filter Topology Set

abbrev putnam_2010_b3_solution : Set ℕ := sorry
theorem putnam_2010_b3
      (n : ℕ) (hn : n > 0)
      (trans : (ℕ → Fin 2010 → ℕ) → ℕ → Prop)
      (htrans : ∀ P T, trans P T ↔ ∀ t : ℕ, t < T → ∃ i j,
            i ≠ j ∧
            P t i ≥ i.1 + 1 ∧ P (t + 1) i = P t i - (i.1 + 1) ∧ P (t + 1) j = P t j + (i.1 + 1) ∧
            ∀ k : Fin 2010, k ≠ i → k ≠ j → P (t + 1) k = P t k) :
      (∀ B, ∑ i, B i = 2010 * n → ∃ᵉ (P) (T), P 0 = B ∧ trans P T ∧ ∀ i, P T i = n)
      ↔ n ∈ putnam_2010_b3_solution := by
Problem: putnam_2010_b4
Category: algebra

Find all pairs of polynomials $p(x)$ and $q(x)$ with real coefficients for which $p(x)q(x+1)-p(x+1)q(x)=1$.

Solution: Show that the pairs $(p,q)$ satisfying the given equation are those of the form $p(x)=ax+b,q(x)=cx+d$ for $a,b,c,d \in \mathbb{R}$ such that $bc-ad=1$.

Lean 4 formalization:
import Mathlib

open Filter Topology Set

abbrev putnam_2010_b4_solution : Set (Polynomial ℝ × Polynomial ℝ) := sorry
theorem putnam_2010_b4
(p q : Polynomial ℝ)
: (∀ x : ℝ, p.eval x * q.eval (x + 1) - p.eval (x + 1) * q.eval x = 1) ↔ (p, q) ∈ putnam_2010_b4_solution := by
Problem: putnam_2010_b5
Category: analysis

Is there a strictly increasing function $f: \mathbb{R} \to \mathbb{R}$ such that $f'(x) = f(f(x))$ for all $x$?

Solution: Show that the solution is no such function exists.

Lean 4 formalization:
import Mathlib

open Filter Topology Set

abbrev putnam_2010_b5_solution : Prop := sorry
theorem putnam_2010_b5 :
  (∃ f : ℝ → ℝ, StrictMono f ∧ Differentiable ℝ f ∧ (∀ x : ℝ, deriv f x = f (f x))) ↔ putnam_2010_b5_solution := by
Problem: putnam_2010_b6
Category: linear_algebra

Let $A$ be an $n \times n$ matrix of real numbers for some $n \geq 1$. For each positive integer $k$, let $A^{[k]}$ be the matrix obtained by raising each entry to the $k$th power. Show that if $A^k=A^{[k]}$ for $k=1,2,\dots,n+1$, then $A^k=A^{[k]}$ for all $k \geq 1$.


Lean 4 formalization:
import Mathlib

open Filter Topology Set

theorem putnam_2010_b6
(n : ℕ)
(npos : n ≥ 1)
(A : Matrix (Fin n) (Fin n) ℝ)
(Apow : ℕ → Matrix (Fin n) (Fin n) ℝ)
(hApow : ∀ k > 0, Apow k = (fun i j : Fin n => (A i j) ^ k))
: (∀ k ∈ Set.Icc 1 (n + 1), A ^ k = Apow k) → (∀ k ≥ 1, A ^ k = Apow k) := by
Problem: putnam_2011_a1
Category: geometry, algebra

Define a \emph{growing spiral} in the plane to be a sequence of points with integer coordinates $P_0=(0,0),P_1,\dots,P_n$ such that $n \geq 2$ and:
\begin{itemize}
\item the directed line segments $P_0P_1,P_1P_2,\dots,P_{n-1}P_n$ are in the successive coordinate directions east (for $P_0P_1$), north, west, south, east, etc.;
\item the lengths of these line segments are positive and strictly increasing.
\end{itemize}
How many of the points $(x,y)$ with integer coordinates $0 \leq x \leq 2011,0 \leq y \leq 2011$ \emph{cannot} be the last point, $P_n$ of any growing spiral?

Solution: Show that there are $10053$ excluded points.

Lean 4 formalization:
import Mathlib

abbrev putnam_2011_a1_solution : ℕ := sorry
theorem putnam_2011_a1
  (IsSpiral : List (Fin 2 → ℤ) → Prop)
  (IsSpiral_def : ∀ P, IsSpiral P ↔ P.length ≥ 3 ∧ P[0]! = 0 ∧
  (∃ l : Fin (P.length - 1) → ℕ, (∀ i, 0 < l i) ∧ StrictMono l ∧ (∀ i : Fin (P.length - 1),
    (i.1 % 4 = 0 → (P[i] 0 + l i = P[i.1 + 1]! 0 ∧ P[i] 1 = P[i.1 + 1]! 1)) ∧
    (i.1 % 4 = 1 → (P[i] 0 = P[i.1 + 1]! 0 ∧ P[i] 1 + l i = P[i.1 + 1]! 1)) ∧
    (i.1 % 4 = 2 → (P[i] 0 - l i = P[i.1 + 1]! 0 ∧ P[i] 1 = P[i.1 + 1]! 1)) ∧
    (i.1 % 4 = 3 → (P[i] 0 = P[i.1 + 1]! 0 ∧ P[i] 1 - l i = P[i.1 + 1]! 1))))) :
  {p | 0 ≤ p 0 ∧ p 0 ≤ 2011 ∧ 0 ≤ p 1 ∧ p 1 ≤ 2011 ∧ ¬∃ spiral, IsSpiral spiral ∧ spiral.getLast! = p}.encard = putnam_2011_a1_solution := by
Problem: putnam_2011_a2
Category: analysis

Let $a_1,a_2,\dots$ and $b_1,b_2,\dots$ be sequences of positive real numbers such that $a_1 = b_1 = 1$ and $b_n = b_{n-1} a_n - 2$ for$n=2,3,\dots$. Assume that the sequence $(b_j)$ is bounded. Prove tha \[ S = \sum_{n=1}^\infty \frac{1}{a_1...a_n} \] converges, and evaluate $S$.

Solution: Show that the solution is $S = 3/2$.

Lean 4 formalization:
import Mathlib

open Topology Filter

noncomputable abbrev putnam_2011_a2_solution : ℝ := sorry
theorem putnam_2011_a2
(a b : ℕ → ℝ)
(habn : ∀ n : ℕ, a n > 0 ∧ b n > 0)
(hab1 : a 0 = 1 ∧ b 0 = 1)
(hb : ∀ n ≥ 1, b n = b (n-1) * a n - 2)
(hbnd : ∃ B : ℝ, ∀ n : ℕ, |b n| ≤ B)
: Tendsto (fun n => ∑ i : Fin n, 1/(∏ j : Fin (i + 1), (a j))) atTop (𝓝 putnam_2011_a2_solution) := by
Problem: putnam_2011_a3
Category: analysis

Find a real number $c$ and a positive number $L$ for which $\lim_{r \to \infty} \frac{r^c \int_0^{\pi/2} x^r\sin x\,dx}{\int_0^{\pi/2} x^r\cos x\,dx}=L$.

Solution: Show that $(c,L)=(-1,2/\pi)$ works.

Lean 4 formalization:
import Mathlib

open Topology Filter

noncomputable abbrev putnam_2011_a3_solution : ℝ × ℝ := sorry
theorem putnam_2011_a3
: putnam_2011_a3_solution.2 > 0 ∧ Tendsto (fun r : ℝ => (r ^ putnam_2011_a3_solution.1 * ∫ x in Set.Ioo 0 (Real.pi / 2), x ^ r * Real.sin x) / (∫ x in Set.Ioo 0 (Real.pi / 2), x ^ r * Real.cos x)) atTop (𝓝 putnam_2011_a3_solution.2) := by
Problem: putnam_2011_a4
Category: linear_algebra

For which positive integers $n$ is there an $n \times n$ matrix with integer entries such that every dot product of a row with itself is even, while every dot product of two different rows is odd?

Solution: Show that the answer is $n$ odd.

Lean 4 formalization:
import Mathlib

open Topology Filter Matrix

abbrev putnam_2011_a4_solution : Set ℕ := sorry
theorem putnam_2011_a4
    (nmat : ℕ → Prop)
    (hnmat : ∀ n, nmat n ↔
      ∃ A : Matrix (Fin n) (Fin n) ℤ,
        (∀ r, Even ((A r) ⬝ᵥ (A r))) ∧
        Pairwise fun r1 r2 ↦ Odd ((A r1) ⬝ᵥ (A r2)))
    (n : ℕ) (npos : 0 < n) :
    nmat n ↔ n ∈ putnam_2011_a4_solution := by
Problem: putnam_2011_a5
Category: analysis

Let $F:\mathbb{R}^2 \to \mathbb{R}$ and $g:\mathbb{R} \to \mathbb{R}$ be twice continuously differentiable functions with the following properties:
\begin{itemize}
\item $F(u,u)=0$ for every $u \in \mathbb{R}$;
\item for every $x \in \mathbb{R}$, $g(x)>0$ and $x^2g(x) \leq 1$;
\item for every $(u,v) \in \mathbb{R}^2$, the vector $\nabla F(u,v)$ is either $\mathbf{0}$ or parallel to the vector $\langle g(u),-g(v) \rangle$.
\end{itemize}
Prove that there exists a constant $C$ such that for every $n \geq 2$ and any $x_1,\dots,x_{n+1} \in \mathbb{R}$, we have $\min_{i \neq j} |F(x_i,x_j)| \leq \frac{C}{n}$.


Lean 4 formalization:
import Mathlib

open Topology Filter Matrix

theorem putnam_2011_a5
(F : (Fin 2 → ℝ) → ℝ)
(g : ℝ → ℝ)
(vec : ℝ → ℝ → (Fin 2 → ℝ))
(Fgrad : (Fin 2 → ℝ) → (Fin 2 → ℝ))
(parallel : (Fin 2 → ℝ) → (Fin 2 → ℝ) → Prop)
(hparallel : parallel = (fun u v : Fin 2 → ℝ => ∃ c : ℝ, u = c • v))
(Fgdiff : ContDiff ℝ 2 F ∧ ContDiff ℝ 2 g)
(prop1 : ∀ uu : Fin 2 → ℝ, uu 0 = uu 1 → F uu = 0)
(prop2 : ∀ x : ℝ, g x > 0 ∧ x ^ 2 * g x ≤ 1)
(hvec : ∀ x y : ℝ, (vec x y) 0 = x ∧ (vec x y) 1 = y)
(hFgrad : ∀ uv : Fin 2 → ℝ, Fgrad uv 0 = deriv (fun x : ℝ => F (vec x (uv 1))) (uv 0) ∧ Fgrad uv 1 = deriv (fun y : ℝ => F (vec (uv 0) y)) (uv 1))
(prop3 : ∀ uv : Fin 2 → ℝ, Fgrad uv = 0 ∨ parallel (Fgrad uv) (vec (g (uv 0)) (-g (uv 1))))
: ∃ C : ℝ, ∀ n ≥ 2, ∀ x : Fin (n + 1) → ℝ, sInf {Fxx : ℝ | ∃ i j : Fin (n + 1), i ≠ j ∧ Fxx = |F (vec (x i) (x j))|} ≤ C / n := by
Problem: putnam_2011_a6
Category: abstract_algebra, linear_algebra

Let $G$ be an abelian group with $n$ elements, and let $\{g_1=e,g_2,\dots,g_k\} \subsetneq G$ be a (not necessarily minimal) set of distinct generators of $G$. A special die, which randomly selects one of the elements $g_1,g_2,\dots,g_k$ with equal probability, is rolled $m$ times and the selected elements are multiplied to produce an element $g \in G$. Prove that there exists a real number $b \in (0,1)$ such that $\lim_{m \to \infty} \frac{1}{b^{2m}} \sum_{x \in G} (\text{Prob}(g=x)-\frac{1}{n})^2$ is positive and finite.


Lean 4 formalization:
import Mathlib

open Topology Filter Matrix

theorem putnam_2011_a6
(G : Type*) [CommGroup G] [Fintype G]
(n : ℕ)
(gset : Set G)
(k : ℕ)
(mgprob : ℕ → G → ℝ)
(hmgprob : mgprob = (fun (m : ℕ) (x : G) => ({f : Fin m → gset | (∏ i : Fin m, (f i).1) = x}.ncard : ℝ) / k ^ m))
(hn : n = (Fintype.elems : Finset G).card)
(hk : gset.encard = k)
(hgsetprop : k < n)
(hgset1 : 1 ∈ gset)
(hgsetgen : Subgroup.closure gset = ⊤)
: ∃ b ∈ Set.Ioo (0 : ℝ) 1, ∃ C > 0, Tendsto (fun m : ℕ => (1 / b ^ (2 * m)) * (∑ x : G, (mgprob m x - 1 / n) ^ 2)) atTop (𝓝 C) := by
Problem: putnam_2011_b1
Category: algebra

Let $h$ and $k$ be positive integers. Prove that for every $\epsilon>0$, there are positive integers $m$ and $n$ such that $\epsilon<|h\sqrt{m}-k\sqrt{n}|<2\epsilon$.


Lean 4 formalization:
import Mathlib

open Topology Filter Matrix

theorem putnam_2011_b1
(h k : ℤ)
(hkpos : h > 0 ∧ k > 0)
: ∀ ε > 0, ∃ m n : ℤ, m > 0 ∧ n > 0 ∧ ε < |h * Real.sqrt m - k * Real.sqrt n| ∧ |h * Real.sqrt m - k * Real.sqrt n| < 2 * ε := by
Problem: putnam_2011_b2
Category: number_theory

Let $S$ be the set of all ordered triples $(p,q,r)$ of prime numbers for which at least one rational number $x$ satisfies $px^2+qx+r=0$. Which primes appear in seven or more elements of $S$?

Solution: Show that only the primes $2$ and $5$ appear seven or more times.

Lean 4 formalization:
import Mathlib

open Topology Filter Matrix

abbrev putnam_2011_b2_solution : Set ℕ := sorry
theorem putnam_2011_b2
  (S : Set (Fin 3 → ℕ))
  (t : ℕ)
  (hS : S = {s : Fin 3 → ℕ | (s 0).Prime ∧ (s 1).Prime ∧ (s 2).Prime ∧ ∃ x : ℚ, (s 0) * x ^ 2 + (s 1) * x + (s 2) = 0}) :
  (t.Prime ∧ ({s ∈ S | ∃ i : Fin 3, s i = t}.encard ≥ 7))
  ↔ t ∈ putnam_2011_b2_solution := by
Problem: putnam_2011_b3
Category: analysis

Let $f$ and $g$ be (real-valued) functions defined on an open interval containing $0$, with $g$ nonzero and continuous at $0$. If $fg$ and $f/g$ are differentiable at $0$, must $f$ be differentiable at $0$?

Solution: Prove that $f$ is differentiable.

Lean 4 formalization:
import Mathlib

open Topology Filter Matrix

abbrev putnam_2011_b3_solution : Prop := sorry
theorem putnam_2011_b3 :
  ((∀ f g : ℝ → ℝ,
    g 0 ≠ 0 → ContinuousAt g 0 →
    DifferentiableAt ℝ (fun x ↦ f x * g x) 0 →
    DifferentiableAt ℝ (fun x ↦ f x / g x) 0 →
    (DifferentiableAt ℝ f 0))
  ↔ putnam_2011_b3_solution) := by
Problem: putnam_2011_b4
Category: linear_algebra

In a tournament, $2011$ players meet $2011$ times to play a multiplayer game. Every game is played by all $2011$ players together and ends with each of the players either winning or losing. The standings are kept in two $2011 \times 2011$ matrices, $T=(T_{hk})$ and $W=(W_{hk})$. Initially, $T=W=0$. After every game, for every $(h,k)$ (including for $h=k$), if players $h$ and $k$ tied (that is, both won or both lost), the entry $T_{hk}$ is increased by $1$, while if player $h$ won and player $k$ lost, the entry $W_{hk}$ is increased by $1$ and $W_{kh}$ is decreased by $1$. Prove that at the end of the tournament, $\det(T+iW)$ is a non-negative integer divisible by $2^{2010}$.


Lean 4 formalization:
import Mathlib

open Topology Filter Matrix

theorem putnam_2011_b4
(games : Fin 2011 → Fin 2011 → Bool)
(T W : Matrix (Fin 2011) (Fin 2011) ℂ)
(hT : T = (fun p1 p2 => ({g | games g p1 = games g p2}.ncard : ℂ)))
(hW : W = (fun p1 p2 => ({g | games g p1 ∧ !games g p2}.ncard - {g | !games g p1 ∧ games g p2}.ncard : ℂ)))
: ∃ n : ℕ, (T + Complex.I • W).det = n ∧ (2 ^ 2010) ∣ n := by
Problem: putnam_2011_b5
Category: analysis

Let $a_1, a_2, \dots$ be real numbers. Suppose that there is a constant $A$ such that for all $n$,
\[
\int_{-\infty}^\infty \left( \sum_{i=1}^n \frac{1}{1 + (x-a_i)^2} \right)^2\,dx \leq An.
\]
Prove there is a constant $B>0$ such that for all $n$,
\[
\sum_{i,j=1}^n (1 + (a_i - a_j)^2) \geq Bn^3.
\]


Lean 4 formalization:
import Mathlib

open Topology Filter Matrix

theorem putnam_2011_b5
  (a : ℕ → ℝ)
  (h : ∃ A : ℝ, ∀ n : ℕ, ∫ x : ℝ, ((∑ i : Finset.range n, 1 / (1 + (x - a i) ^ 2)) ^ 2) ≤ A * n) :
  ∃ B : ℝ, B > 0 ∧
    ∀ n : ℕ, ∑' i : Finset.range n, ∑' j : Finset.range n, (1 + (a i - a j) ^ 2) ≥ B * n ^ 3 := by
Problem: putnam_2011_b6
Category: number_theory

Let $p$ be an odd prime. Show that for at least $(p+1)/2$ values of $n$ in $\{0,1,2,\dots,p-1\}$,
\[
\sum_{k=0}^{p-1} k! n^k \qquad \mbox{is not divisible by $p$.}
\]


Lean 4 formalization:
import Mathlib

open Topology Filter Matrix Set

theorem putnam_2011_b6
(p : ℕ)
(hp : Odd p ∧ Nat.Prime p)
: {n ∈ Finset.range p | ¬ p ∣ ∑ k : Finset.range p, Nat.factorial k * n^(k : ℕ)}.card ≥ (p + 1)/2 := by
Problem: putnam_2012_a1
Category: geometry, algebra

Let $d_1,d_2,\dots,d_{12}$ be real numbers in the open interval $(1,12)$. Show that there exist distinct indices $i,j,k$ such that $d_i,d_j,d_k$ are the side lengths of an acute triangle.


Lean 4 formalization:
import Mathlib

open Matrix

theorem putnam_2012_a1
(d : Fin 12 → ℝ)
(hd : ∀ i, d i ∈ Set.Ioo 1 12)
: ∃ i j k, i ≠ j ∧ i ≠ k ∧ j ≠ k ∧ d k ≥ d i ∧ d k ≥ d j ∧ (d i) ^ 2 + (d j) ^ 2 > (d k) ^ 2 := by
Problem: putnam_2012_a2
Category: abstract_algebra

Let $*$ be a commutative and associative binary operation on a set $S$. Assume that for every $x$ and $y$ in $S$, there exists $z$ in $S$ such that $x*z=y$. (This $z$ may depend on $x$ and $y$.) Show that if $a,b,c$ are in $S$ and $a*c=b*c$, then $a=b$.


Lean 4 formalization:
import Mathlib

open Matrix

theorem putnam_2012_a2
(S : Type*) [CommSemigroup S]
(a b c : S)
(hS : ∀ x y : S, ∃ z : S, x * z = y)
(habc : a * c = b * c)
: a = b := by