b. (Medium) Find $x$ for $x^5 ≡ 64 \mod 97$.
c. (Hard) Find $x$ for $x^7 ≡ 1337 \mod 2015$.
Source: Original
2. $x,y,z$ are complex numbers such that $$x+y+z=1$$ $$x^2+y^2+z^2=2$$ $$x^3+y^3+z^3=3$$ Find $x^4+y^4+z^4$.
Source: Dummit and Foote Abstract Algebra, Exercise 14.6.23(a)
3. Find necessary and sufficient conditions for $z∈ℂ$ so that $$\sum_{n=1}^∞ \dfrac{1}{1+z^n}$$ converges.
Source: Walter Rudin Principles of Mathematical Analysis, Exercise 3.6(d)
4. A number with prime factorization $p_1^{α_1}p_2^{α_2}...p_n^{α_n}$ is said to be $B$-powersmooth if $p_i^{α_i} ≤ B$ for all $i$. If $γ(B)$ is the set of all positive $B$-powersmooth numbers, prove $$\sum_{k∈γ(B)} \dfrac{1}{k} ≤ \dfrac{B+1}{2}$$ Source: Original ($B$-powersmoothness, however, is an established term)
Source: Original/maintstream
6. Let $B$ be the unit ball of complex numbers (i.e. complex numbers $α$ for which $|α| ≤ 1$), and let $f : B→B$ be a continuous map such that $|α-β| > |f(α)-f(β)|$ for all distinct complex numbers $α,β∈ℂ$. Show there exists a unique complex number $x$ such that $f(x)=x$.
Source: Banach fixed point theorem on $ℂ$ as a metric space
7. Show the function $f(x) = \sum_{k=1}^∞ kx^k$ is well defined and continuous on the interval $(-1,1)$. Source: James Munkres Topology, Exercise 7.46.5
8. A countably infinite number of party-goers will be playing a game. The game will start by every guest donning either a red- or blue-colored hat, and though they will see the colors of every other guest's hat, they will not know their own. Without allowing time for communication, they will then be simultaneously ushered into private rooms and be made to guess the color of their own hats. If all but finitely many guests guess correctly, they win. Is there an a priori strategy the guests can formulate so that they always win?
Source: Mainstream
Fixing a pair of IBSs $X=\{x_1,x_2\}$, does there always exist another IBS uncorrelated to them both? What about if $X$ is an arbitrary finite collection of IBSs? Or an arbitrary countable collection?
Source: Original
10. Let $Γ$ be an arbitrary sequence of vectors $$Γ : ℕ→ℝ^m$$ such that $|Γ(n)| ≤ 1$ for all $n∈ℕ$. Does there always exist a sequence of scalars $β : ℕ→\{-1,1\}$ such that $\lim_{n→∞} \dfrac{\sum_{i=1}^n β(i)·Γ(i)}{n} = 0$? What about such that the sequence $|\sum_{i=1}^n β(i)·Γ(i)|$ is bounded?
Source: Original. Note that I don't yet have an answer for the latter question.
11. A $3$-sided die is rolled and its value $A$ is recorded. Then $A$ $5$-sided dice are rolled and their sum $B$ is recorded. Finally, $B$ $7$-sided dice are rolled and their sum $C$ is recorded. Find the standard deviation of $C$ as a random variable.
Source: Euler Project Problem Take on #389
12. If $G$ is a graph whose edges are labeled with integers, let $ε(G)$ denote the sum of all those integers. If $G$ is a connected graph, then let $ε'(G) = \min \{ε(H)\}$, where $H$ ranges over the connected subgraphs of $G$. If $G$ is the graph depicted below, then calculate $ε'(G)$ and demonstrate proof.
Source: Euler Problem Take on #107. Image modified from here.
13. You are blindfolded, then given a deck of $52$ cards in which $3$ of the cards have been flipped up, then inserted into the deck randomly. Without taking the blindfold off, rearrange the deck into two stacks such that both stacks have the same number of up-flipped cards. (You are allowed to flip as many cards as you please.)
Source: Mainstream
14. There are $n$ balls rolling along a line in one direction and $k$ balls rolling along the same line in the opposite direction. The speeds of the balls in the first group and in the second group are equal. Initially the two groups of balls are separated from one another and at some point the balls start colliding. The collisions are assumed to be elastic. How many collisions will there be?
Source: Mainstream
15. There are $30$ students in a class. The teacher has written every student's name on a stick, shuffled them, and handed them out randomly to each student. If a sequence of students is made by the process of selecting a random student $a$, then continuing to the student $b$ whose name is on $a$'s stick, and so forth until a student is repeated in the sequence, what is the probability that the entire class will be in the sequence generated?
Source: Original
16. Simplify $$\sqrt{2+\sqrt{3}}$$ Source: Mainstream
17. If $f$ is an arbitrary polynomial in $n$ variables, show that the number of distinct polynomials that arise from permuting these variables always divides $n!$. (For example, the permutation swapping $x$ and $y$ in $x+y-z$ doesn't achieve another polynomial, while the permutation sending $x↦y$, $y↦z$, and $z↦x$ results in $z+x-y≠x+y-z$)
Source: Classical result
18. Below is the finite projective plane known as the Fano plane. An automorphism of the Fano plane is a permutation of the vertices preserving all line incidences (for example, $1$ would need to remain on the unique line containing $2$ and $3$, and $5$ on the same line as $4$ and $1$). A simple example of an automorphism would be rotating the whole diagram by $120$ degrees. For any automorphism $σ$, does there always exist a point for which $σ(x)=x$?
Source: Original (no knowledge of projective geometry is expected)
19. There are $7^9$ $3×3$ matrices with values from the modular ring $ℤ/7ℤ$. How many of them are invertible over $ℤ/7ℤ$?
Source: Original
20. Let $A$ be an infinite collection of points on the unit circle. Show there exists a point $x$ on the circle such that for any $ε > 0$, there exists $a∈A$ of distance to $x$ strictly less than $ε$.
Source: Original/compactness of circle
21. Show that there exist no nontrivial integer solutions to the Diophantine equation $$x^2+y^2=3z^2$$ Source: Mainstream
22. Fix $m∈ℤ$, and let $p(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0$ be a polynomial such that $\text{gcd}(a_n,a_{n-1},...,a_0,m) = 1$. Show that if $q(x)$ has the property that at least one of its coefficients is not divisible by $m$, then so too does $p(x)·q(x)$.
Source: Dummit and Foote Abstract Algebra, Exercise 7.2.2 (decontextualized)
23. You have $13$ differently colored beads and a lace of string. There are $5$ pairs of colors that you either consider gaudy or too similar to display next to one another. Prove that you can still make a full bracelet of these colors while avoiding these unfavorable adjacencies.
Source: Original
24. We say $a > 0$ is a universal chord if for every continuous function $f : [0,1]→ℝ$ such that $f(0)=f(1)$, there exists $x∈[0,1-a]$ such that $f(x)=f(x+a)$. Show that the universal chords are exactly $1/n$ for all $n∈ℕ$.
Source: Original
25. Let $p(x)$ be an arbitrary $n^{\text{th}}$ degree polynomial with natural coefficients.
(a) If you are allowed to ask for the value of $p(α)$ for any natural $α$, how many evaluations will you need at maximum in order to determine $p(x)$?
(b) If you are allowed to ask for the value of $p(α)$ for any real $α$, how many evaluations will you need at maximum in order to determine $p(x)$?
Source: Original
26. (a) You have one fairly weighted coin. Determine a game to play with this coin (that will end with probability $1$) whose odds of winning are exactly $1/3$.
(b) If you instead define "game" more strictly to mean "there is no sequence of coin flips (no matter how infinitesimal the likelihood) that will indefinitely prolong the game," prove that there exists no game you can play whose odds of winning are exactly $1/3$.
Source: (a) Old Putnam problem (b) Original take on Putnam problem
27. Prove that the polynomial $$x^6-23x^4+135x^2-225$$ has a root modulo $p$ for every prime $p$, but has no roots in $ℤ$.
Source: Dummit and Foote Abstract Algebra, Exercise 14.3.7.
28. Write the numbers from $1$ to $64$ on a checkerboard, with numbers $8(n-1)+1,...,8(n-1)+8$ occupying the $n^{\text{th}}$ row from left to right. For each coloring of the squares either white or black satisfying the condition that each row and each column contain exactly four white squares and four black squares, show that the sum of the white squares is equal to the sum of the black squares.
Source: Putnam Exam 2001, B-1
29. Let $f(x)$ be a nonconstant polynomial with positive integer coefficients. If $n$ is a positive integer, prove $f(n)$ divides $f(f(n)+1)$ if and only if $n=1$.
Source: Putnam Exam 2007, B-1
30. Suppose $X$ is a random variable taking on non-negative integers, such that $E[X]=1$, $E[X^2]=2$, and $E[X^3]=5$, where $E[Y]$ is the expected value of the variable $Y$. Determine the smallest possible probability of the event $X=0$.
Source: Putnam Exam 2014, A-4
31. There are $7$ different medals in the Arstotzkan army, which may be awarded multiple times to indicate glory. For any two distinct collections of medals, one is decisively more glorious than the other. However, the bureaucratic rules for determining exactly which of the two is more glorious is unreasonably complicated. All you know is that "more glorious" is a transitive relation, and that if one soldier has as many or more medals of every type than another (and has strictly more of \textit{some} type), he is a greater glory to Arstotzka than the other.
Prove that every (potentially infinite) regiment of Arstotzkan soldiers has a least glorious member.
Source: Original, based off Hilbert basis theorem/monomial orderings
32. Find the set of natural numbers that appear at the beginning of a positive integral power of $2$ (written in base $10$). Proof is easy log 10.
33. Something something hexachordal theorem?
34. You start with a thousand dollars, and continue to play the following game for as long as you are not bankrupt: You flip a coin, and win a dollar if it is heads, and lose a dollar if it is tails. (a) If you play with a fair coin, what is the probability you will eventually go bankrupt? (b) If you play with a slightly fixed coin with probability of heads being $0.501$, what is the probability you will eventually go bankrupt?
Source: Original
35. Let $a_n$ be the sequence defined by $a_0 = 1$ and $a_{n+1} = 2^{a_n}$. Prove that, modulo $m$, this sequence stabilizes after at most $m$ terms: $a_{m-1} \equiv a_m \equiv a_{m+1} \equiv ~...~ \text{mod }m$. Note: This sequence must be constructed in the integers, and only then reduced mod $m$; you cannot recursively define $a_{n+1}$ only in terms of the $m$-modular residue of $a_n$, because $a \equiv b~\text{mod }m$ does not necessarily imply $x^a \equiv x^b~\text{mod m}$.
Solution: Prove that if $a, b \geq \phi(m)$ and $a \equiv b ~\text{mod }\phi(m)$, where $\phi$ is Euler's totient function, then $x^a \equiv x^b ~\text{mod }m$ (reduce via Chinese remainder theorem to the case $m=p^r$, and treat $p=2$ as a special case). Then stabilization of $a_n$ after at most $m-1$ terms modulo $\phi(m)$ implies stabilization of $a_n$ after at most $m$ terms modulo $m$.
Source: Putnam B5, 1997
36. Killing hydras.
37. Cuckoo's egg/look-and-say puzzle
38. Prove $22$ is the only number whose look-and-say sequence does not grow indefinitely.
39. Take a chess knight, and restrict his movement pattern to a particular 2 squares (instead of his usual 8). Place him on a toroidal 100x100 grid. After 1 move, he may be in 2 different locations. After 2 moves, he may be in 3 different locations. After a sufficiently long time, what is the maximal number of different locations he may be in? Does it depend on which two 2 squares of movement he is restricted to?
Source: Original
40. If the knight may also choose to sit still for a given turn, how many turns until the knight may potentially be anywhere on the torus? Assume the two nontrivial movements are not opposites of each other.
41. Random points/geodesics on the surface of the sphere.
Source: Original
42. Fifth-arc robot meanderings (Euler project problem 208). Prove that any walk back home must consist of a multiple of five arcs, and return the robot to its original northward-facing position.
43. Josephus suicide problem (solution: even/odd recursive formula). (a) If you are the $1337^\text{th}$ soldier of a group of $2018$, who do you give the knife to? (b) Prove $n+f(n)$ is injective, where $f(n)$ is the survivor in a group of $n$ soldiers. Solve $n$ in $n+f(n)=2018$ (solution: $1355$).
Source: (b) is original.
44. Rotationally distinct colorings of a dodecahedron.
45. Suppose that early in the universe, two planets are a mere hundred million kilometers apart. A rocket launches from one toward the other at a constant speed of 10km/s. Ordinarily, the rocket would reach its destination in three to four months. However, this universe is expanding uniformly, so that the distance between the two planets is increasing at the speed of light (300,000km/s), or even faster. Show that despite this expansion, the rocket will eventually reach the other planet. (Solution: If the speed of the rocket is $1$ compared to the expansion rate of $k$ and initial planetary distance $d$, then if $f(t)$ is the distance traveled from the planet, then we have the differential equation $f' = k \dfrac{f}{d+kt} + 1$. Solve this. Hint: $x \text{log}(x)$)
Source: Ant on a rope problem
46. Show that if $a | b^2 | a^3 | b^4 | a^5 | ...$ ad infinitum, then $a=b$.
47. Let $a,b$ be whole numbers. Show that if $ab+1$ divides $a^2+b^2$, then their quotient is a square number. Hint: Introduce a variable $N$, and rewrite the problem as solving for positive triples satisfying $(ab+1)N = a^2+b^2$. This can be interpreted as a quadratic in $a$. And when polynomials have one solution, they typically have another... what's up with that?
48. "Windmill" problem, IMO 2011 C3
49. (a) If a coin is flipped $2n$ times, let $P(n)$ be the probability that you get exactly $n$ heads and $n$ tails (the most likely distribution). Prove that $P(n) \to 0$ as $n \to \infty$
(b) Let $P_m(n)$ be the probability that the sum of $n$ rolled dice is $m$, and let $\displaystyle P(n) = \max_m P_m(n)$. Prove that $P(n) \to 0$ as $n \to \infty$.
(Proof of (a): Stirling's approximation. Proof of (b) Stirling's approximation + ???, or Central Limit Theorem)
50. Suppose $2n$ coins of different denominations (repetitions allowed) are lined up in a row. Players A and B take turns snatching a coin on either the leftmost or rightmost end of the line. Prove that when playing optimally, Player A will never lose to Player B, no matter the starting coin pattern. (Proof: Player A can always force a final snatch pattern of $ABABA...AB$ or $BABAB...BA$. Force the one that favors him.)
51. Let $e(x)$ be a continuous family of idempotent matrices. Show that the column rank of $e(x)$ is constant at all points $x$. (Serre-Swan stuff. Proof: $1-e(x)$ is another such family whose column spaces are orthogonal and generate the entire space; since the max column rank is an open set, and min column rank a closed set, this implies the theorem)
52. Characterize the one-parameter subgroups of $\text{GL}_n(\mathbb{C})$. Proof
53. The director of a prison offers 300 death row prisoners, who are numbered from 1 to 300, a last chance. A room contains a cupboard with 300 drawers. The director randomly puts one prisoner's number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 200 drawers in any order. All drawers are closed again afterwards. If, during this search, each prisoner finds his number in one of the drawers, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner enters to look in the drawers.
If all prisoners guess randomly, the chance they survive is less than the chance of correctly guessing a preferred atom from every single atom comprising one thousand Earths (less than one in $10^{53}$). However, if they're smart, the prisoners can formulate a strategy with a survival probability of ~60%; can you find it? Source: 100 prisoners problem
54. (a) Let $f(x)$ be any degree $n-1$ polynomial, and let $g(x) = (x-1)(x-2)...(x-n)$. Show that $f(x)$ may be written as a linear combination of the polynomials $g_m(x) := \frac{g(x)}{x-m}$ for $1 \leq m \leq n$.
(b) Let $M$ be any complex-valued matrix. Show that there exists a nonzero polynomial $f(x)$ with real coefficients such that $f(M) = 0$.
55. (a) A gnat is lost in 3D space, and calls you (situated at the origin) for help. He tells you that from his perspective, the line segments $v$ and $w$ look like equal-length segments of the same straight line. What is the gnat's position? (Equal length is one dimension; parallel is another dimension; lying on the same line is the final dimension). (b) A different gnat is lost and disoriented. The line segment $v$ appears to have length $\alpha$ and points straight "up." The line segment $w$ appears to have length $\beta$ and points $30$ degrees down of left. What is the gnat's position? (3D space + orientation is four variables; each line segment's length + angle constitutes two-dimensional reduction) (c) Another gnat is lost. Three line segments $u,v,w$ float in space, and from the gnat's perspective they constitute a triangle. What is the gnat's position? (Will need to choose third line segment a little specifically)
56. 100 students are taking an oral exam that’s structured a little unusually. The professor asks each student, in turn, the following question: “How many of the 100 students will get a “pass” grade by the time the exam is finished?” Each student must reply with some number, from 0 to 100. The professor then immediately grades the student either “pass” or “fail” and announces the grade out loud – all the remaining students hear it. Then the next student is asked the same question, and so on.
After everyone’s had their turn, an inspector examines all the answers and the grades. If there’s any student who answered correctly (i.e. exactly that number of students passed), but was failed by the professor, all the failing grades are changed to passing, and so all students pass the exam. If there’s no such instance of unfair failing, there are no changes.
Can the students come up with a strategy that will guarantee everyone will pass the exam? Source: Slate Star Codex, Open Thread 145 comments
57. A musical instrument can produce 9 distinct tones. A "beat" is a permutation of these tones in some order. A "transition" is a pair of beats where the first is related to the last by a single adjacent transposition of tones. A "song" is a sequence of transitions, e.g. 1234 - 1324 - 3124. Does there exist a song that includes every transition (forward or backward) exactly once?
58. Solve all $f : \mathbb{Z} \to \mathbb{Z}$ with $2f(a) = f(2b) = f(f(a+b))$ for all $a,b$. (Proof: $a=0$ gives us a way to simplify any $f(f(...))$ expression; applying to $b=0$ gives us a way to reduce any $f(2a)$ expression; applying this to the hypothesis tells us $f(a+b) = f(a) + f(b) - f(0)$, which implies $f$ is affine. Then the characterization $f(n) = 0$ or $f(n) = 2n + C$ follows)
59. Find the covariance matrix of $(x,y)$ distributed uniformly randomly over the unit equilateral Sierpinski triangle. (Answer: 1/18 times the identity. Source: Jane Street advertisement on SSC)
60. In the land of Humilia, a game is played between two players with 101 stones in a pot between them. On each turn, a player may take 1-5 stones from the pot, and nominally, the winner is whoever winds up with the most stones in the end. However, modesty is valued above all in Humilia, and if a player wins by more than three stones in the end, they will be shunned and disqualified from the tournament. Under perfect play, do you choose to be the player who plays first, or second?
61. A 64-player binary tournament bracket is about to start. You plan to free up your schedule in advance to watch some of the matchups (meaning, you can plan to watch the second semifinal, for example, but you cannot decide to watch one game or another based on the results of previous matches and teams seen). What is the minimum number of matches you must plan to see in order to definitely answer any (well-posed) question of the form, "Who won in the match between Team X and Team Y?" Solution: 21
62. You and your friend's new favorite game is "topological nim": You take your favorite compact metric space $X$, and Player 1 chooses a number $r$ less than the diameter of $X$. Starting with Player 1, each removes a closed disk of radius $r$ from the space $X$ on their turn, until one player—the winner—removes what remains of the space on his turn.
For each $n$, who wins topological nim on $S^n$ with the standard metric (easy)? The p-adics (slightly harder)? $\mathbb{RP}^n$ (tough)?
63. Separating axis theorem for polygons, statement that faces are enough. (In 3d, need cross products of edges.)
64. What is the diameter of the intersection of two unit balls in $\mathbb{R}^n$, each positioned on the boundary of the other?
