ChristianZ97/putnambench-satp-v4.27 huggingface dataset:
Problem: putnam_2014_b2
Category: analysis

Suppose that \( f \) is a function on the interval \([1,3]\) such that \(-1 \leq f(x) \leq 1\) for all \( x \) and \( \int_{1}^{3} f(x) \, dx = 0 \). How large can \(\int_{1}^{3} \frac{f(x)}{x} \, dx \) be?

Solution: Show that the solution is log (4 / 3).

Lean 4 formalization:
import Mathlib

open Topology Filter Nat

noncomputable abbrev putnam_2014_b2_solution : ℝ := sorry
theorem putnam_2014_b2 :
  IsGreatest {t | ∃ f : ℝ → ℝ,
    (∀ x : Set.Icc (1 : ℝ) 3, -1 ≤ f x ∧ f x ≤ 1) ∧
    (∫ x in Set.Ioo 1 3, f x = 0) ∧
    (∫ x in Set.Ioo 1 3, (f x) / x) = t}
  putnam_2014_b2_solution := by
Problem: putnam_2014_b3
Category: linear_algebra, number_theory

Let $A$ be an $m \times n$ matrix with rational entries. Suppose that there are at least $m+n$ distinct prime numbers among the absolute values of the entries of $A$. Show that the rank of $A$ is at least 2.


Lean 4 formalization:
import Mathlib

open Topology Filter Nat

theorem putnam_2014_b3
(m n : ℕ)
(A : Matrix (Fin m) (Fin n) ℚ)
(mnpos : 0 < m ∧ 0 < n)
(Aprime : {p : ℕ | p.Prime ∧ ∃ (i : Fin m) (j : Fin n), |A i j| = p}.encard ≥ m + n)
: A.rank ≥ 2 := by
Problem: putnam_2014_b4
Category: algebra

Show that for each positive integer \( n \), all the roots of the polynomial $ \sum_{k=0}^{n} 2^k(n-k)x^k $ are real numbers.


Lean 4 formalization:
import Mathlib

open Topology Filter Nat

theorem putnam_2014_b4
(n : ℕ)
(P: Polynomial ℂ)
(npos : n > 0)
(Px : P.degree = n ∧ ∀ k ∈ Set.Icc 0 n, P.coeff k = 2 ^ (k * (n - k)))
: ∀ r ∈ P.roots, r.im = 0 := by
Problem: putnam_2014_b6
Category: analysis, number_theory

Let $f: [0,1] \to \mathbb{R}$ be a function for which there exists a constant $K>0$ such that $\left| f(x) - f(y) \right| \leq K \left| x - y \right|$ for all $x,y \in [0,1]$. Suppose also that for each rational number $r \in [0,1]$, there exist integers $a$ and $b$ such that $f(r) = a + br$. Prove that there exist finitely many intervals $I_1, \dots, I_n$ such that $f$ is a linear function on each $I_i$ and $[0,1] = \bigcup_{i=1}^n I_i$.


Lean 4 formalization:
import Mathlib

open Topology Filter Nat Set Interval

theorem putnam_2014_b6
(f : ℝ → ℝ)
(hlip : ∃ K > 0, ∀ x ∈ Icc 0 1, ∀ y ∈ Icc 0 1, |f x - f y| ≤ K * |x - y|)
(hrat : ∀ r ∈ Icc (0 : ℚ) 1, ∃ a b : ℤ, f r = a + b * r)
: (∃ I : Finset (Interval ℝ), (∀ Ii ∈ I, ∃ m c : ℝ, ∀ x ∈ coeHom Ii, f x = c + m * x) ∧ Icc 0 1 = ⋃ Ii ∈ I, coeHom Ii) := by
Problem: putnam_2015_a1
Category: geometry, analysis

Let $A$ and $B$ be points on the same branch of the hyperbola $xy=1$. Suppose that $P$ is a point lying between $A$ and $B$ on this hyperbola, such that the area of the triangle $APB$ is as large as possible. Show that the region bounded by the hyperbola and the chord $AP$ has the same area as the region bounded by the hyperbola and the chord $PB$.


Lean 4 formalization:
import Mathlib

theorem putnam_2015_a1
  (hyperbola : Set (Fin 2 → ℝ))
  (hhyperbola : hyperbola = {p | p 1 = 1 / p 0 ∧ p 0 > 0})
  (A B P : Fin 2 → ℝ)
  (PPline : (Fin 2 → ℝ) → (Fin 2 → ℝ) → (ℝ → ℝ))
  (hAB : A ∈ hyperbola ∧ B ∈ hyperbola ∧ A 0 < B 0)
  (hP : P ∈ hyperbola ∧ A 0 < P 0 ∧ P 0 < B 0 ∧ (∀ P', (P' ∈ hyperbola ∧ A 0 < P' 0 ∧ P' 0 < B 0) → MeasureTheory.volume (convexHull ℝ {A, P', B}) ≤ MeasureTheory.volume (convexHull ℝ {A, P, B})))
  (hPPline : ∀ P1 P2, P1 0 ≠ P2 0 → PPline P1 P2 = (fun x : ℝ => ((P2 1 - P1 1) / (P2 0 - P1 0)) * (x - P1 0) + P1 1)) :
  ∫ x in Set.Ioo (A 0) (P 0), (PPline A P) x - 1 / x = ∫ x in Set.Ioo (P 0) (B 0), (PPline P B) x - 1 / x := by
Problem: putnam_2015_a2
Category: number_theory

Let $a_0=1$, $a_1=2$, and $a_n=4a_{n-1}-a_{n-2}$ for $n \geq 2$. Find an odd prime factor of $a_{2015}$.

Solution: Show that one possible answer is $181$.

Lean 4 formalization:
import Mathlib

abbrev putnam_2015_a2_solution : ℕ := sorry
theorem putnam_2015_a2
(a : ℕ → ℤ)
(abase : a 0 = 1 ∧ a 1 = 2)
(arec : ∀ n ≥ 2, a n = 4 * a (n - 1) - a (n - 2))
: Odd putnam_2015_a2_solution ∧ putnam_2015_a2_solution.Prime ∧ ((putnam_2015_a2_solution : ℤ) ∣ a 2015) := by
Problem: putnam_2015_a3
Category: number_theory, algebra

Compute $\log_2 \left( \prod_{a=1}^{2015}\prod_{b=1}^{2015}(1+e^{2\pi iab/2015}) \right)$. Here $i$ is the imaginary unit (that is, $i^2=-1$).

Solution: Show that the answer is $13725$.

Lean 4 formalization:
import Mathlib

abbrev putnam_2015_a3_solution : ℂ := sorry
theorem putnam_2015_a3 :
    Complex.log (∏ a : Fin 2015, ∏ b : Fin 2015, (1 + Complex.exp (2 * Real.pi * Complex.I * (a.1 + 1) * (b.1 + 1) / 2015))) / Complex.log 2 = putnam_2015_a3_solution := by
Problem: putnam_2015_a4
Category: analysis

For each real number $x$, let
\[
f(x) = \sum_{n\in S_x} \frac{1}{2^n},
\]
where $S_x$ is the set of positive integers $n$ for which $\lfloor nx \rfloor$ is even. What is the largest real number $L$ such that $f(x) \geq L$ for all $x \in [0,1)$? (As usual, $\lfloor z \rfloor$ denotes the greatest integer less than or equal to $z$.)

Solution: Prove that $L = \frac{4}{7}$.

Lean 4 formalization:
import Mathlib

noncomputable abbrev putnam_2015_a4_solution : ℝ := sorry
theorem putnam_2015_a4
(S : ℝ → Set ℤ)
(f : ℝ → ℝ)
(p : ℝ → Prop)
(hS : S = fun (x : ℝ) ↦ {n : ℤ | n > 0 ∧ Even ⌊n * x⌋})
(hf : f = fun (x : ℝ) ↦ ∑' n : S x, 1 / 2 ^ (n : ℤ))
(hp : ∀ l, p l ↔ ∀ x ∈ Set.Ico 0 1, f x ≥ l)
: IsGreatest p putnam_2015_a4_solution := by
Problem: putnam_2015_a5
Category: number_theory

Let $q$ be an odd positive integer, and let $N_q$ denote the number of integers $a$ such that $0<a<q/4$ and $\gcd(a,q)=1$. Show that $N_q$ is odd if and only if $q$ is of the form $p^k$ with $k$ a positive integer and $p$ a prime congruent to $5$ or $7$ modulo $8$.


Lean 4 formalization:
import Mathlib

theorem putnam_2015_a5
(q : ℕ)
(Nq : ℕ)
(qodd : Odd q)
(qpos : q > 0)
(hNq : Nq = {a : ℕ | 0 < a ∧ a < (q : ℝ) / 4 ∧ Nat.gcd a q = 1}.encard)
: Odd Nq ↔ ∃ p k : ℕ, q = p ^ k ∧ k > 0 ∧ p.Prime ∧ (p % 8 = 5 ∨ p % 8 = 7) := by
Problem: putnam_2015_a6
Category: linear_algebra

Let $n$ be a positive integer. Suppose that $A$, $B$, and $M$ are $n \times n$ matrices with real entries such that $AM = MB$, and such that $A$ and $B$ have the same characteristic polynomial. Prove that $\det(A-MX)=\det(B-XM)$ for every $n \times n$ matrix $X$ with real entries.


Lean 4 formalization:
import Mathlib

theorem putnam_2015_a6
(n : ℕ)
(A B M : Matrix (Fin n) (Fin n) ℝ)
(npos : n > 0)
(hmul : A * M = M * B)
(hpoly : Matrix.charpoly A = Matrix.charpoly B)
: ∀ X : Matrix (Fin n) (Fin n) ℝ, (A - M * X).det = (B - X * M).det := by
Problem: putnam_2015_b1
Category: analysis

Let $f$ be a three times differentiable function (defined on $\mathbb{R}$ and real-valued) such that $f$ has at least five distinct real zeros. Prove that $f+6f'+12f''+8f'''$ has at least two distinct real zeros.


Lean 4 formalization:
import Mathlib

theorem putnam_2015_b1
(f : ℝ → ℝ)
(nzeros : (ℝ → ℝ) → ℕ → Prop)
(fdiff : ContDiff ℝ 2 f ∧ Differentiable ℝ (iteratedDeriv 2 f))
(hnzeros : ∀ f' : ℝ → ℝ, ∀ n : ℕ, nzeros f' n = ({x : ℝ | f' x = 0}.encard ≥ n))
(fzeros : nzeros f 5)
: nzeros (f + 6 * deriv f + 12 * iteratedDeriv 2 f + 8 * iteratedDeriv 3 f) 2 := by
Problem: putnam_2015_b2
Category: number_theory

Given a list of the positive integers $1,2,3,4,\dots$, take the first three numbers $1,2,3$ and their sum $6$ and cross all four numbers off the list. Repeat with the three smallest remaining numbers $4,5,7$ and their sum $16$. Continue in this way, crossing off the three smallest remaining numbers and their sum, and consider the sequence of sums produced: $6,16,27,36,\dots$. Prove or disprove that there is some number in the sequence whose base $10$ representation ends with $2015$.

Solution: Show that such a number does exist.

Lean 4 formalization:
import Mathlib

abbrev putnam_2015_b2_solution : Prop := sorry
theorem putnam_2015_b2
(sets : ℕ → Set ℕ)
(Smin3 : Set ℕ → (Fin 3 → ℕ))
(sums : ℕ → ℕ)
(hsets0 : sets 0 = Set.Ici 1)
(hmin3 : ∀ S : Set ℕ, S.encard ≥ 3 → ((Smin3 S) 0 = sInf S ∧ (Smin3 S) 1 = sInf (S \ {(Smin3 S) 0}) ∧ (Smin3 S) 2 = sInf (S \ {(Smin3 S) 0, (Smin3 S) 1})))
(hsums : ∀ n : ℕ, sums n = (Smin3 (sets n)) 0 + (Smin3 (sets n)) 1 + (Smin3 (sets n)) 2)
(hsetsn : ∀ n : ℕ, sets (n + 1) = sets n \ {(Smin3 (sets n)) 0, (Smin3 (sets n)) 1, (Smin3 (sets n)) 2, sums n})
: (∃ n : ℕ, List.IsPrefix [5, 1, 0, 2] (Nat.digits 10 (sums n))) ↔ putnam_2015_b2_solution := by
Problem: putnam_2015_b3
Category: linear_algebra

Let $S$ be the set of all $2 \times 2$ real matrices $M=\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ whose entries $a,b,c,d$ (in that order) form an arithmetic progression. Find all matrices $M$ in $S$ for which there is some integer $k>1$ such that $M^k$ is also in $S$.

Solution: Show that matrices of the form $\alpha A$ or $\beta B$, where $A=\left(\begin{smallmatrix} 1 & 1 \\ 1 & 1 \end{smallmatrix}\right)$, $B=\left(\begin{smallmatrix} -3 & -1 \\ 1 & 3 \end{smallmatrix}\right)$, and $\alpha,\beta \in \mathbb{R}$, are the only matrices in $S$ that satisfy the given condition.

Lean 4 formalization:
import Mathlib

abbrev putnam_2015_b3_solution : Set (Matrix (Fin 2) (Fin 2) ℝ) := sorry
theorem putnam_2015_b3
  (M : Matrix (Fin 2) (Fin 2) ℝ)
  (S : Set (Matrix (Fin 2) (Fin 2) ℝ))
  (hS : S = {M' | (M' 0 1 - M' 0 0 = M' 1 0 - M' 0 1) ∧ (M' 1 0 - M' 0 1 = M' 1 1 - M' 1 0)}) :
  (M ∈ S ∧ (∃ k > 1, M ^ k ∈ S)) ↔ M ∈ putnam_2015_b3_solution := by
Problem: putnam_2015_b4
Category: algebra

Let $T$ be the set of all triples $(a,b,c)$ of positive integers for which there exist triangles with side lengths $a,b,c$. Express
\[
\sum_{(a,b,c) \in T} \frac{2^a}{3^b 5^c}
\]
as a rational number in lowest terms.

Solution: The answer is $17/21$.

Lean 4 formalization:
import Mathlib

abbrev putnam_2015_b4_solution : ℤ × ℕ := sorry
theorem putnam_2015_b4
(quotientof : ℚ → (ℤ × ℕ))
(hquotientof : ∀ q : ℚ, quotientof q = (q.num, q.den))
: quotientof (∑' t : (Fin 3 → ℤ), if (∀ n : Fin 3, t n > 0) ∧ t 0 < t 1 + t 2 ∧ t 1 < t 2 + t 0 ∧ t 2 < t 0 + t 1
then 2^(t 0)/(3^(t 1)*5^(t 2)) else 0) = putnam_2015_b4_solution := by
Problem: putnam_2015_b5
Category: algebra

Let $P_n$ be the number of permutations $\pi$ of $\{1,2,\dots,n\}$ such that
\[
|i-j| = 1 \mbox{ implies } |\pi(i) -\pi(j)| \leq 2
\]
for all $i,j$ in $\{1,2,\dots,n\}$. Show that for $n \geq 2$, the quantity
\[
P_{n+5} - P_{n+4} - P_{n+3} + P_n
\]
does not depend on $n$, and find its value.

Solution: Prove that answer is $4$.

Lean 4 formalization:
import Mathlib

open Function

abbrev putnam_2015_b5_solution : ℕ := sorry
theorem putnam_2015_b5
(P : ℕ → ℕ)
(hP : P = fun n ↦ {pi : Finset.Icc 1 n → Finset.Icc 1 n | Bijective pi ∧ ∀ i j : Finset.Icc 1 n, Nat.dist i j = 1 → Nat.dist (pi i) (pi j) ≤ 2}.ncard)
: (∀ n : ℕ, n ≥ 2 →
    (P (n + 5) : ℤ) - (P (n + 4) : ℤ) - (P (n + 3) : ℤ) + (P n : ℤ) = putnam_2015_b5_solution) := by
Problem: putnam_2015_b6
Category: analysis, number_theory

For each positive integer $k$, let $A(k)$ be the number of odd divisors of $k$ in the interval $[1,\sqrt{2k})$. Evaluate $\sum_{k=1}^\infty (-1)^{k-1}\frac{A(k)}{k}$.

Solution: Show that the sum converges to $\pi^2/16$.

Lean 4 formalization:
import Mathlib

open Filter Topology

noncomputable abbrev putnam_2015_b6_solution : ℝ := sorry
theorem putnam_2015_b6
    (A : ℕ → ℕ)
    (hA : ∀ k > 0, A k = {j : ℕ | Odd j ∧ j ∣ k ∧ j < Real.sqrt (2 * k)}.encard) :
    Tendsto (fun K : ℕ ↦ ∑ k ∈ Finset.Icc 1 K, (-1 : ℝ) ^ ((k : ℝ) - 1) * (A k / (k : ℝ)))
      atTop (𝓝 putnam_2015_b6_solution) := by
Problem: putnam_2016_a1
Category: algebra, number_theory

Find the smallest positive integer $j$ such that for every polynomial $p(x)$ with integer coefficients and for every integer $k$, the integer \[ p^{(j)}(k) = \left. \frac{d^j}{dx^j} p(x) \right|_{x=k} \] (the $j$-th derivative of $p(x)$ at $k$) is divisible by 2016.

Solution: Show that the solution is $8$.

Lean 4 formalization:
import Mathlib

open Polynomial Filter Topology Real Set Nat

abbrev putnam_2016_a1_solution : ℕ := sorry
theorem putnam_2016_a1 :
  IsLeast {j : ℕ | 0 < j ∧ ∀ P : ℤ[X], ∀ k : ℤ, 2016 ∣ (derivative^[j] P).eval k} putnam_2016_a1_solution := by
Problem: putnam_2016_a2
Category: analysis

Given a positive integer $n$, let $M(n)$ be the largest integer $m$ such that
\[
\binom{m}{n-1} > \binom{m-1}{n}.
\]
Evaluate
\[
\lim_{n \to \infty} \frac{M(n)}{n}.
\]

Solution: Show that the answer is $\frac{3 + \sqrt{5}}{2}$.

Lean 4 formalization:
import Mathlib

open Polynomial Filter Topology Real Set Nat

noncomputable abbrev putnam_2016_a2_solution : ℝ := sorry
theorem putnam_2016_a2
    (M : ℕ → ℕ)
    (hM : ∀ n > 0, IsGreatest {m | 0 < m ∧ (m - 1).choose n < m.choose (n - 1)} (M n)) :
    Tendsto (fun n ↦ M n / (n : ℝ)) atTop (𝓝 putnam_2016_a2_solution) := by
Problem: putnam_2016_a3
Category: analysis

Suppose that $f$ is a function from $\mathbb{R}$ to $\mathbb{R}$ such that
\[
f(x) + f\left( 1 - \frac{1}{x} \right) = \arctan x
\]
for all real $x \neq 0$. (As usual, $y = \arctan x$ means $-\pi/2 < y < \pi/2$ and $\tan y = x$.) Find
\[
\int_0^1 f(x)\,dx.
\]

Solution: Prove that the answer is $\frac{3\pi}{8}$.

Lean 4 formalization:
import Mathlib

open Polynomial Filter Topology Real Set Nat

noncomputable abbrev putnam_2016_a3_solution : ℝ := sorry
theorem putnam_2016_a3
(f : ℝ → ℝ)
(hf : ∀ x : ℝ, x ≠ 0 → f x + f (1 - 1 / x) = arctan x)
: (∫ x in (0)..1, f x = putnam_2016_a3_solution) := by
Problem: putnam_2016_a5
Category: abstract_algebra

Suppose that $G$ is a finite group generated by the two elements $g$ and $h$, where the order of $g$ is odd. Show that every element of $G$ can be written in the form
\[
g^{m_1} h^{n_1} g^{m_2} h^{n_2} \cdots g^{m_r} h^{n_r}
\]
with $1 \leq r \leq |G|$ and $m_1, n_1, m_2, n_2, \ldots, m_r, n_r \in \{-1, 1\}$.
(Here $|G|$ is the number of elements of $G$.)


Lean 4 formalization:
import Mathlib

open Polynomial Filter Topology Real Set Nat List

theorem putnam_2016_a5
(G : Type*) [Group G]
(Gfin : Fintype G)
(g h : G)
(ghgen : Subgroup.closure {g, h} = ⊤ ∧ ¬Subgroup.closure {g} = ⊤ ∧ ¬Subgroup.closure {h} = ⊤)
(godd : Odd (orderOf g))
(S : Set G)
(hS : S = {g * h, g⁻¹ * h, g * h⁻¹, g⁻¹ * h⁻¹})
: (∀ x : G, ∃ mn : List G, 1 ≤ mn.length ∧ mn.length ≤ Gfin.card ∧ ∀ i : Fin mn.length, mn.get i ∈ S ∧ x = List.prod mn) := by
Problem: putnam_2016_a6
Category: algebra

Find the smallest constant $C$ such that for every real polynomial $P(x)$ of degree $3$ that has a root in the interval $[0,1]$,
\[
\int_0^1 \left| P(x) \right|\,dx \leq C \max_{x \in [0,1]} \left| P(x) \right|.
\]

Solution: Prove that the smallest such value of $C$ is $\frac{5}{6}$.

Lean 4 formalization:
import Mathlib

open Polynomial Filter Topology Real Set Nat List

noncomputable abbrev putnam_2016_a6_solution : ℝ := sorry
theorem putnam_2016_a6
  (p : ℝ → Prop)
  (hp : ∀ c, p c ↔
          ∀ P : Polynomial ℝ, P.degree = 3 →
          (∃ x ∈ Icc 0 1, P.eval x = 0) →
          ∫ x in (0)..1, |P.eval x| ≤ c * (sSup {y | ∃ x ∈ Icc 0 1, y = |P.eval x|})) :
  IsLeast p putnam_2016_a6_solution := by
Problem: putnam_2016_b1
Category: analysis

Let $x_0,x_1,x_2,\dots$ be the sequence such that $x_0=1$ and for $n \geq 0$,
\[
x_{n+1} = \ln(e^{x_n} - x_n)
\]
(as usual, the function $\ln$ is the natural logarithm). Show that the infinite series
\[
x_0 + x_1 + x_2 + \cdots
\]
converges and find its sum.

Solution: The sum converges to $e - 1$.

Lean 4 formalization:
import Mathlib

open Polynomial Filter Topology Real Set Nat List

noncomputable abbrev putnam_2016_b1_solution : ℝ := sorry
theorem putnam_2016_b1
(x : ℕ → ℝ)
(hx0 : x 0 = 1)
(hxn : ∀ n : ℕ, x (n + 1) = log (exp (x n) - (x n)))
: (∑' n : ℕ, x n = putnam_2016_b1_solution) := by
Problem: putnam_2016_b2
Category: analysis

Define a positive integer $n$ to be \emph{squarish} if either $n$ is itself a perfect square or the distance from $n$ to the nearest perfect square is a perfect square. For example, $2016$ is squarish, because the nearest perfect square to $2016$ is $45^2 = 2025$ and $2025 - 2016 = 9$ is a perfect square. (Of the positive integers between $1$ and $10$, only $6$ and $7$ are not squarish.)

For a positive integer $N$, let $S(N)$ be the number of squarish integers between $1$ and $N$,
inclusive. Find positive constants $\alpha$ and $\beta$ such that
\[
\lim_{N \to \infty} \frac{S(N)}{N^\alpha} = \beta,
\]
or show that no such constants exist.

Solution: Prove that the limit exists for $\alpha = \frac{3}{4}$ and equals $\beta = \frac{4}{3}$.

Lean 4 formalization:
import Mathlib

open Classical Polynomial Filter Topology Real Set Nat List

noncomputable abbrev putnam_2016_b2_solution : ℝ × ℝ := sorry
theorem putnam_2016_b2
(squarish : ℤ → Prop)
(hsquarish : ∀ n, squarish n ↔ IsSquare n ∨ ∃ w : ℤ, IsSquare |n - w ^ 2| ∧ ∀ v : ℕ, |n - w ^ 2| ≤ |n - v ^ 2|)
(S : ℤ → ℕ)
(hS : S = fun n ↦ {i ∈ Finset.Icc 1 n | squarish i}.card)
(p : ℝ → ℝ → Prop)
(hp : ∀ α β, p α β ↔ α > 0 ∧ β > 0 ∧ Tendsto (fun N ↦ S N / (N : ℝ) ^ α) atTop (𝓝 β))
: ((∀ α β : ℝ, ((α, β) = putnam_2016_b2_solution ↔ p α β)) ∨ ¬∃ α β : ℝ, p α β) := by
Problem: putnam_2016_b3
Category: geometry

Suppose that $S$ is a finite set of points in the plane such that the area of triangle $\triangle ABC$ is at most $1$ whenever $A$, $B$, and $C$ are in $S$. Show that there exists a triangle of area $4$ that (together with its interior) covers the set $S$.


Lean 4 formalization:
import Mathlib

open Polynomial Filter Topology Real Set Nat List

theorem putnam_2016_b3
(S : Finset (Fin 2 → ℝ))
(hS : ∀ A ∈ S, ∀ B ∈ S, ∀ C ∈ S, MeasureTheory.volume (convexHull ℝ {A, B, C}) ≤ 1)
: ∃ A' B' C' : Fin 2 → ℝ, MeasureTheory.volume (convexHull ℝ {A', B', C'}) = 4 ∧ convexHull ℝ {A', B', C'} ⊇ S := by
Problem: putnam_2016_b4
Category: linear_algebra, probability

Let $A$ be a $2n \times 2n$ matrix, with entries chosen independently at random. Every entry is chosen to be $0$ or $1$, each with probability $1/2$. Find the expected value of $\det(A-A^t)$ (as a function of $n$), where $A^t$ is the transpose of $A$.

Solution: Show that the expected value equals $\frac{(2n)!}{4^nn!}$.

Lean 4 formalization:
import Mathlib

open Real Set Nat

noncomputable abbrev putnam_2016_b4_solution : ℕ → ℝ := sorry
theorem putnam_2016_b4
  (n : ℕ) (npos : n ≥ 1)
  (mats01 : Set (Matrix (Fin (2 * n)) (Fin (2 * n)) ℝ))
  (hmats01 : mats01 = {A | ∀ i j : Fin (2 * n), A i j = 0 ∨ A i j = 1}) :
  (∑' A : mats01, (A.1 - (Matrix.transpose A)).det) / mats01.ncard = putnam_2016_b4_solution n := by
Problem: putnam_2016_b5
Category: algebra

Find all functions $f$ from the interval $(1,\infty)$ to $(1,\infty)$ with the following property: if $x,y \in (1,\infty)$ and $x^2 \leq y \leq x^3$, then $(f(x))^2 \leq f(y) \leq (f(x))^3$.

Solution: Show that the only such functions are the functions $f(x)=x^c$ for some $c>0$.

Lean 4 formalization:
import Mathlib

open Polynomial Filter Topology Real Set Nat List

abbrev putnam_2016_b5_solution : Set (Set.Ioi (1 : ℝ) → Set.Ioi (1 : ℝ)) := sorry
theorem putnam_2016_b5
  (f : Set.Ioi (1 : ℝ) → Set.Ioi (1 : ℝ)) :
  f ∈ putnam_2016_b5_solution ↔
    (∀ x y : Set.Ioi (1 : ℝ), ((x : ℝ) ^ 2 ≤ y ∧ y ≤ (x : ℝ) ^ 3) → ((f x : ℝ) ^ 2 ≤ f y ∧ f y ≤ (f x : ℝ) ^ 3)) := by
Problem: putnam_2016_b6
Category: analysis

Evaluate $\sum_{k=1}^\infty \frac{(-1)^{k-1}}{k} \sum_{n=0}^\infty \frac{1}{k2^n+1}$.

Solution: Show that the desired sum equals $1$.

Lean 4 formalization:
import Mathlib

open Polynomial Filter Topology Real Set Nat List

abbrev putnam_2016_b6_solution : ℝ := sorry
theorem putnam_2016_b6 :
  ∑' k : ℕ, ((-1 : ℝ) ^ ((k + 1 : ℤ) - 1) / (k + 1 : ℝ)) * ∑' n : ℕ, (1 : ℝ) / ((k + 1) * (2 ^ n) + 1) = putnam_2016_b6_solution := by
Problem: putnam_2017_a1
Category: number_theory

Let $S$ be the smallest set of positive integers such that (a) $2$ is in $S$, (b) $n$ is in $S$ whenever $n^2$ is in $S$, and (c) $(n+5)^2$ is in $S$ whenever $n$ is in $S$. Which positive integers are not in $S$?.

Solution: Show that all solutions are in the set $\{x \in \mathbb{Z}\, |\, x > 0 \land (x = 1 \lor 5 \mid x)\}

Lean 4 formalization:
import Mathlib

abbrev putnam_2017_a1_solution : Set ℤ := sorry
theorem putnam_2017_a1
    (IsQualifying : Set ℤ → Prop)
    (IsQualifying_def : ∀ S, IsQualifying S ↔
      (∀ n ∈ S, 0 < n) ∧
      2 ∈ S ∧
      (∀ n > 0, n ^ 2 ∈ S → n ∈ S) ∧
      (∀ n ∈ S, (n + 5) ^ 2 ∈ S))
    (S : Set ℤ)
    (hS : IsLeast IsQualifying S) :
    Sᶜ ∩ {n | 0 < n} = putnam_2017_a1_solution := by
Problem: putnam_2017_a2
Category: algebra

Let $Q_0(x)=1$, $Q_1(x)=x$, and $Q_n(x)=\frac{(Q_{n-1}(x))^2-1}{Q_{n-2}(x)}$ for all $n \geq 2$. Show that, whenever $n$ is a positive integer, $Q_n(x)$ is equal to a polynomial with integer coefficients.


Lean 4 formalization:
import Mathlib

open Polynomial

theorem putnam_2017_a2
    (Q : ℕ → RatFunc ℚ)
    (hQbase : Q 0 = 1 ∧ Q 1 = (X : ℚ[X]))
    (hQn : ∀ n, Q (n + 2) = (Q (n + 1) ^ 2 - 1) / Q n)
    (n : ℕ) (hn : 0 < n) :
    ∃ P : ℤ[X], Q n = P.map (Int.castRingHom ℚ) := by
Problem: putnam_2017_a3
Category: analysis

Let $a$ and $b$ be real numbers with $a<b$, and let $f$ and $g$ be continuous functions from $[a,b]$ to $(0,\infty)$ such that $\int_a^b f(x)\,dx=\int_a^b g(x)\,dx$ but $f \neq g$. For every positive integer $n$, define $I_n=\int_a^b \frac{(f(x))^{n+1}}{(g(x))^n}\,dx$. Show that $I_1,I_2,I_3,\dots$ is an increasing sequence with $\lim_{n \to \infty} I_n=\infty$.


Lean 4 formalization:
import Mathlib

open Topology Filter

theorem putnam_2017_a3
(a b : ℝ)
(f g : ℝ → ℝ)
(I : ℕ → ℝ)
(altb : a < b)
(fgcont : ContinuousOn f (Set.Icc a b) ∧ ContinuousOn g (Set.Icc a b))
(fgimg : f '' (Set.Icc a b) ⊆ Set.Ioi 0 ∧ g '' (Set.Icc a b) ⊆ Set.Ioi 0)
(fgint : ∫ x in Set.Ioo a b, f x = ∫ x in Set.Ioo a b, g x)
(fneg : ∃ x : Set.Icc a b, f x ≠ g x)
(hI : ∀ n > 0, I n = ∫ x in Set.Ioo a b, ((f x) ^ (n + 1)) / ((g x) ^ n))
: (∀ n > 0, I (n + 1) > I n) ∧ Tendsto I atTop atTop := by
Problem: putnam_2017_a4
Category: algebra

A class with $2N$ students took a quiz, on which the possible scores were $0,1,\dots,10$. Each of these scores occurred at least once, and the average score was exactly $7.4$. Show that the class can be divided into two groups of $N$ students in such a way that the average score for each group was exactly $7.4$.


Lean 4 formalization:
import Mathlib

open Topology Filter

theorem putnam_2017_a4
(N : ℕ)
(score : Fin (2 * N) → Fin 11)
(hsurj : ∀ k : Fin 11, ∃ i : Fin (2 * N), score i = k)
(havg : (∑ i : Fin (2 * N), (score i : ℝ)) / (2 * N) = 7.4)
: (∃ s : Finset (Fin (2 * N)), s.card = N ∧ (∑ i ∈ s, (score i : ℝ)) / N = 7.4 ∧ (∑ i ∈ sᶜ, (score i : ℝ)) / N = 7.4) := by
Problem: putnam_2017_b1
Category: geometry

Let $L_1$ and $L_2$ be distinct lines in the plane. Prove that $L_1$ and $L_2$ intersect if and only if, for every real number $\lambda \neq 0$ and every point $P$ not on $L_1$ or $L_2$, there exist points $A_1$ on $L_1$ and $A_2$ on $L_2$ such that $\overrightarrow{PA_2}=\lambda \overrightarrow{PA_1}$.


Lean 4 formalization:
import Mathlib

open Topology Filter

theorem putnam_2017_b1
  (lines : Set (Set (Fin 2 → ℝ)))
  (L1 L2 : Set (Fin 2 → ℝ))
  (L1L2lines : L1 ∈ lines ∧ L2 ∈ lines)
  (L1L2distinct : L1 ≠ L2)
  (hlines : lines = {L | ∃ v w : Fin 2 → ℝ, w ≠ 0 ∧ L = {p | ∃ t : ℝ, p = v + t • w}}) :
  L1 ∩ L2 ≠ ∅ ↔ (∀ lambda : ℝ, lambda ≠ 0 →
    ∀ P, (P ∉ L1 ∧ P ∉ L2) → ∃ A1 A2, A1 ∈ L1 ∧ A2 ∈ L2 ∧ (A2 - P = lambda • (A1 - P))) := by
Problem: putnam_2017_b2
Category: algebra

Suppose that a positive integer $N$ can be expressed as the sum of $k$ consecutive positive integers
\[
N = a + (a+1) +(a+2) + \cdots + (a+k-1)
\]
for $k=2017$ but for no other values of $k>1$. Considering all positive integers $N$ with this property, what is the smallest positive integer $a$ that occurs in any of these expressions?

Solution: Prove that the smallest value of $a$ is $16$.

Lean 4 formalization:
import Mathlib

open Topology Filter

abbrev putnam_2017_b2_solution : ℕ := sorry
theorem putnam_2017_b2
  (S : ℤ → ℕ → ℤ)
  (p : ℤ → ℕ → Prop)
  (q : ℤ → Prop)
  (hS : S = fun (a : ℤ) k ↦ ∑ i ∈ Finset.range k, (a + i))
  (hp : ∀ N k, p N k ↔ ∃ a > 0, S a k = N)
  (hq : ∀ N, q N ↔ p N 2017 ∧ ∀ k : ℕ, k > 1 → k ≠ 2017 → ¬p N k) :
  IsLeast {a : ℤ | q (S a 2017)} putnam_2017_b2_solution := by