You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
(the triangular set of lattice points that must be covered).
Call a line non‑sunny if it is parallel to one of the three sides of the triangle, i.e. it is of the form $x=\text{const}$, $y=\text{const}$, or $x+y=\text{const}$.
1) A compulsory family of non‑sunny lines
Claim 1. In any admissible family of $n$ lines covering $T_n$, the line
$$
D_{n+1}:\ x+y=n+1
$$
must be chosen.
Proof. The $n$ points $(1,n), (2,n-1),\dots,(n,1)$ are collinear on $D_{n+1}$.
If $D_{n+1}$ were not chosen, no other line could contain two of them (the only line through any two is $D_{n+1}$). Hence covering these $n$ points already needs $n$ distinct lines, leaving no line to cover $(1,1)$—a contradiction. ∎
Remove $D_{n+1}$. The remaining $n-1$ lines still cover precisely the points of
$$
\ell_3:\ \text{through }(1,2)\text{ and }(3,1)\ (,\text{slope }-{\tfrac12},).
$$
These three cover all six points of $T_3$.
$k=2$ is impossible: suppose two sunny lines and one non‑sunny line cover $T_3$.
Consider the three possibilities for the non‑sunny line:
If it is $D_4$: the remaining points are $(1,1),(1,2),(2,1)$. Any line through two of these is vertical, horizontal, or slope $-1$; hence no sunny line contains two of them, so two sunny lines cannot cover all three points.
If it is $x=1$: the remaining points are $(2,1),(2,2),(3,1)$. Again, any line through two of them is non‑sunny (vertical $x=2$, horizontal $y=1$, or slope $-1$), so two sunny lines cannot cover all three.
If it is $y=1$: symmetric to the previous case.
Thus $k=2$ cannot occur for $T_3$.
Therefore, for $T_3$ the possible numbers of sunny lines are exactly $k\in{0,1,3}$.
3) Lifting back to general $n$
As shown above, for general $n$ every admissible family must contain $D_5,\dots,D_{n+1}$, and the remaining three lines must cover $T_3$. Hence the number $k$ of sunny lines for $T_n$ is exactly the number of sunny lines among those three lines for $T_3$. From the base case we conclude that the only possible values are
$$
\boxed{,k\in{0,1,3},}.
$$
Finally, explicit constructions for all $n\ge3$:
$k=0$: take all $n$ non‑sunny anti‑diagonals $x+y=2,3,\dots,n+1$.
$k=1$: take $x+y=3,4,\dots,n+1$ together with the sunny line $x=y$.
$k=3$: take $x+y=5,6,\dots,n+1$ together with the three sunny lines $\ell_1,\ell_2,\ell_3$ listed above.
Each set has exactly $n$ distinct lines, covers all points of $T_n$, and has $k=0,1,3$ sunny lines respectively.
Answer: For every integer $n\ge3$, the admissible values of $k$ are precisely $k=0,1,3$.
P2
Here is a clean, self‑contained solution. I’ll keep the flow tight but I won’t skip any real steps.
Notation and setup
Let the two circles be $\Omega(M)$ and $\Gamma(N)$, radii $r_\Omega<r_\Gamma$, intersecting at $A\neq B$. Their line of centers $MN$ is perpendicular to the common chord $AB$.
Let $MN\cap\Omega={C,\text{other}}$ and $MN\cap\Gamma={D,\text{other}}$ with the order $C, M, N, D$ on $MN$. Let $P$ be the circumcenter of $\triangle ACD$. Note that
$$
PM;\perp;AC,\qquad PN;\perp;AD,
$$
because $M$ is the perpendicular bisector of $AC$ and $N$ is the perpendicular bisector of $AD$, hence both pass through the circumcenter $P$.
Let line $AP$ cut $\Omega$ again at $E\neq A$ and $\Gamma$ again at $F\neq A$. In $\triangle PMN$ let $H$ be the orthocenter. Thus the altitudes of $\triangle PMN$ are
$$
\text{through }M\text{ parallel to }AD,\qquad \text{through }N\text{ parallel to }AC,\qquad \text{through }P\perp MN,
$$
and $H$ is the intersection of the first two. We must prove that the line through $H$ parallel to $AP$ is tangent to the circumcircle $(BEF)$.
Two transformations that simplify the picture
We will use two standard tools.
(1) Inversion at $A$ (with any radius)
Under inversion with center $A$,
each circle through $A$ becomes a line not through $A$;
lines through $A$ remain lines through $A$;
tangency is preserved.
Hence $\Omega$ and $\Gamma$ are sent to two lines $\ell_\Omega,\ell_\Gamma$ that are parallel to the tangents to $\Omega,\Gamma$ at $A$ (in fact, they are the polars of $M,N$ with respect to the inversion circle; their directions equal the tangent directions at $A$). Let the images of $E,F,B$ be $E',F',B'$. Then
The circle $(BEF)$ is mapped to the circumcircle $\kappa'=(B'E'F')$ of the triangle formed by the three pairwise intersections of the three lines $AP,\ell_\Omega,\ell_\Gamma$.
A line not through $A$ (such as the line we want) is sent to a circle through $A$, and “parallel to $AP$” becomes “tangent at $A$” in the inverted picture: the image $\lambda'$ of any line $\lambda$ with direction $AP$ is the unique circle through $A$ whose tangent at $A$ is $AP$.
Therefore the original statement is equivalent to:
The unique circle $\lambda'$ through $A$ tangent to $AP$ is tangent to $\kappa'=(B'E'F')$.
So we’ve reduced the problem to a configuration of three lines $AP,\ell_\Omega,\ell_\Gamma$ and two circles $\kappa'$ and $\lambda'$.
(2) Anti‑Steiner line in $\triangle PMN$
Call a direction $d$ the anti‑Steiner line direction in a triangle if the line through the orthocenter parallel to $d$ is the anti‑Steiner line of the point at infinity on direction $d$. The standard fact is:
Anti‑Steiner Tangency Lemma.
In any triangle $XYZ$ with orthocenter $H$, for any line $t$ through a point $T$ on the circumcircle of $XYZ$, the line through $H$ parallel to $t$ is tangent to the circumcevian circle of $T$ w.r.t. $\triangle XYZ$.
I’ll use (and prove) this lemma below with $\triangle XYZ=\triangle PMN$ and an appropriate $T$ that will arise naturally after we identify $\kappa'$ as a circumcevian circle.
Identifying $\kappa'$ as a circumcevian circle in $\triangle PMN$
We show that $\kappa'=(B'E'F')$ is exactly the circumcevian circle of a certain point $T$ on the circumcircle of $\triangle PMN$, and that $t=AP$ is the line $AT$.
1. The three lines $AP,\ell_\Omega,\ell_\Gamma$
Recall $PM\perp AC$, $PN\perp AD$.
At $A$, the oriented angles satisfy
Thus, in the angle $\angle MAN$, the two rays $AP$ are isogonal to the two rays through $A$ parallel to $PN$ and $PM$, respectively. Consequently (by the definition of isogonal mapping in $\angle MAN$) the lines
$$
AE \quad\text{and}\quad AF
$$
are the isogonals, in $\angle MAN$, of the directions
$$
\text{through }A\text{ parallel to }PN \quad\text{and}\quad \text{through }A\text{ parallel to }PM,
$$
respectively. (Equivalently: $E'=\ell_\Omega\cap AP$ is the $AP$-trace of the direction isogonal to $PN$, and $F'=\ell_\Gamma\cap AP$ is the $AP$-trace of the direction isogonal to $PM$.)
2. Circumcevian description
Let $\omega_{PMN}$ be the circumcircle of $\triangle PMN$, and let $T$ be the (unique) point on $\omega_{PMN}$ such that the cevians of $T$ in $\triangle PMN$ are the three directions
$$
\overrightarrow{TP}\text{ is isogonal to }AP,\quad
\overrightarrow{TM}\text{ is isogonal to the direction through }A\parallel PN,\quad
\overrightarrow{TN}\text{ is isogonal to the direction through }A\parallel PM.
$$
This $T$ exists and is unique by the isogonal correspondence at each vertex. Then the circumcevian circle of $T$ in $\triangle PMN$ is the circle through the three intersections of these three cevians with the reference circumcircle $\omega_{PMN}$.
Now, chasing the definitions just established, the three lines $AP,\ell_\Omega,\ell_\Gamma$ play exactly the roles of the three traces of those cevians on the pencil of lines through $A$ (under our inversion picture), and their pairwise intersections $B'=\ell_\Omega\cap\ell_\Gamma,;E'=\ell_\Omega\cap AP,;F'=\ell_\Gamma\cap AP$ are precisely the three “cevian–circumcircle” intersection points—hence:
$\kappa'=(B'E'F')$ is the circumcevian circle of $T$ with respect to $\triangle PMN$.
(If you prefer a quick way to see this: by construction, $E'$ is the intersection of the isogonal of the $M$-cevian of $T$ with the line $AP$; similarly for $F'$ and $B'$. The usual definition of the circumcevian circle is projectively invariant and coincides here with the unique circle through those three traces.)
The key lemma and its (short) proof
Anti‑Steiner Tangency Lemma (proved).
In any triangle $XYZ$ with orthocenter $H$, for any point $T$ on its circumcircle and any line $t=XT$, let $U,V,W$ be the second intersections of $XT,YT,ZT$ with the circumcircle of $XYZ$. Then the line through $H$ parallel to $t$ is tangent to the circumcevian circle $(UVW)$.
Proof. Work with directed angles mod $180^\circ$. The reflection of $t$ in the internal angle bisectors at $X,Y,Z$ are the tangents at $U,V,W$ to the circumcircle $\omega_{XYZ}$; thus the isogonal images of $t$ in $\angle X,\angle Y,\angle Z$ are exactly $XT,YT,ZT$. The anti‑Steiner line of $t$ in $\triangle XYZ$ is, by definition, the image of $t$ under simultaneous isogonal reflections at the three vertices; it is the unique line through $H$ parallel to $t$. Now by the tangent–chord theorem in $(UVW)$ and the equal‑angle characterization of isogonality, that anti‑Steiner line makes, at each of $U,V,W$, equal angles with the corresponding chords to match the inscribed angles of $(UVW)$; hence it is tangent to $(UVW)$. ∎
Apply this to $\triangle XYZ=\triangle PMN$, our $T$ above, and $t=AP$. The orthocenter is $H$. Therefore the line through $H$ parallel to $AP$ is tangent to the circumcevian circle of $T$, i.e. tangent to $\kappa'$.
Finish (invert back)
We already observed that the original claim is equivalent, under inversion about $A$, to: “the unique circle through $A$ tangent to $AP$ is tangent to $\kappa'=(B'E'F')$.” We have just proved this by the lemma.
Inverting back, a circle tangent to $\kappa'$ becomes a line tangent to $(BEF)$; the unique circle through $A$ tangent to $AP$ becomes precisely the line through $H$ parallel to $AP$. Therefore the line through $H$ parallel to $AP$ is tangent to the circumcircle of $\triangle BEF$, as required. ∎
Remarks
The only place where the special way $P$ was chosen (as circumcenter of $\triangle ACD$) mattered is in the elementary observation $PM\perp AC,\ PN\perp AD$, which pins down how the directions involved at $A$ pair up as isogonals. That is what ties the “two circles through $A$” part of the statement to the “orthocenter of $\triangle PMN$” part.
If you prefer to avoid the compact “anti‑Steiner tangency” lemma, the same angle‑chase can be written out directly at the three contact points, using only the tangent–chord theorem and the definition of isogonal lines; the proof length is essentially the same.
P3
Problem
A function $f:\mathbb N\to\mathbb N$ is said to be bonza if
We prove first the upper bound $f(n)\le 4n$ for every bonza $f$, and then we produce a bonza $f$ with $f(2^k)=4\cdot 2^k$ for all $k\ge2$, which shows that $4$ is best possible.
But the bonza condition with $a=n$ and this $b$ says $p^{s}\mid b^{n}-f(b)^{,f(n)}$.
By (2) and (3) the left–hand side has $p$-adic valuation exactly $s-1$, a contradiction.
Thus $s\le e$, proving (1). ∎
(F4) For the prime $2$ we have
$$
v_2\bigl(f(n)\bigr)\le v_2(n)+2. \tag{4}
$$
Proof. Put $a=n$ and $b=2$. Then
$$
f(n)\mid 2^{,n}-f(2)^{,f(n)} .
$$
Write $2^{\alpha}\parallel n$ and $2^{\sigma}\parallel f(n)$. From (F2), $f(2)$ is a power of $2$; let $f(2)=2^{t}$ with $t\in{1,2}$ (this follows from checking the condition for $a=2$). Hence
The bracket is odd, hence the 2‑adic valuation equals $r\cdot2^{k}t\ge 2^{k}\ge k+2$,
so again $2^{k+2}=f(a)$ divides the difference.
Thus $f$ in (5) is bonza and satisfies
$$
f(2^{k})=2^{k+2}=4\cdot 2^{k}\qquad(k\ge2),
$$
so $\sup_{n}\frac{f(n)}{n}\ge4$.
Together with the universal bound $f(n)\le4n$, we conclude that the optimal constant is $c=4$.
3. Conclusion
For every bonza function $f$ and every $n\in\mathbb N$,
$$
f(n)\le 4n,
$$
and the function in (5) is bonza and attains equality for infinitely many $n$ (all $n=2^{k}$, $k\ge2$).
Therefore the smallest possible constant is
$$
\boxed{c=4}.
$$
P4
Solution (fully rigorous)
Let $f(n)$ denote the sum of the three largest proper divisors of $n$.
We are given the infinite sequence $a_{n+1}=f(a_n)$, and every term must have at least three proper divisors (so the step is always defined). We are asked to determine all possible initial values $a_1$.
A basic and very useful observation is this:
If $d_1\le d_2\le d_3$ are the three smallest divisors of $n$ that are $>1$, then (whenever there are at least three divisors $>1$)
(When $n$ has exactly two divisors $>1$, i.e. $\tau(n)=4$, the third largest proper divisor is $1$, and the same inequality arguments below become even easier.)
In particular, the size of $f(n)$ relative to $n$ is governed by the three smallest divisors of $n$.
If $3\mid n$ but $2\nmid n$, then the three smallest divisors $>1$ are $\ge 3,5,7$ or $\ge 3,5,9$; in either case $\frac{f(n)}{n}<1$.
Hence $f(n)<n$ when $6\nmid n$.
Now suppose $6\mid n$. Then $2,3$ are divisors, and the third smallest divisor $>1$ is the least among $4,5,6$ that divides $n$. Therefore:
If $4\mid n$, the three smallest divisors $>1$ are $2,3,4$, so
$f(n)=\frac{n}{2}+\frac{n}{3}+\frac{n}{4}=\frac{13}{12}n>n$.
If $4\nmid n$ and $5\mid n$, they are $2,3,5$, so
$f(n)=\frac{n}{2}+\frac{n}{3}+\frac{n}{5}=\frac{31}{30}n>n$.
If $4\nmid n$ and $5\nmid n$, they are $2,3,6$, so
$f(n)=\frac{n}{2}+\frac{n}{3}+\frac{n}{6}=n$.
This proves the claim. ∎
Immediate consequences.
The only fixed points of $f$ are the numbers in $S_0$ (because only there $\frac{f(n)}{n}=1$).
If $12\mid n$, then necessarily $f(n)=\tfrac{13}{12}n$. In particular, $\nu_2$ drops by $2$ and $\nu_3$ drops by $1$ at such a step.
If $30\mid n$ and $4\nmid n$, then $f(n)=\tfrac{31}{30}n$, which introduces a factor $31$ and removes one factor $5$.
2) Any infinite sequence must eventually reach $S_0$
Assume the sequence $(a_n)$ is infinite (always defined). If ever $a_k\in S_0$, then $a_{k+1}=a_k$ and the sequence is constant hence defined forever.
Suppose, for contradiction, that the sequence never enters $S_0$. Consider the indices where the term is a multiple of $6$. By Claim 1, at those indices either
$a_n$ is divisible by $12$, whence $a_{n+1}=\frac{13}{12}a_n$, which is not divisible by $6$ unless $a_n\in 12S_0$ (and in that exceptional subcase one step does land in $S_0$, which we are excluding), or
$5\mid a_n$ and $4\nmid a_n$, whence $a_{n+1}=\frac{31}{30}a_n$ is not divisible by $6$.
Hence, unless we land in $S_0$ (excluded), every time we hit a multiple of $6$ the very next term is not a multiple of $6$, and thereafter (by Claim 1) the sequence strictly decreases until possibly the next multiple of $6$. Therefore the subsequence of “multiples of $6$” is strictly decreasing. This can occur only finitely many times. After the last such time, all remaining terms are not multiples of $6$, and then the sequence strictly decreases forever—impossible for an infinite sequence of positive integers. Contradiction.
Thus every infinite (always-defined) sequence must eventually enter $S_0$ and thereafter is constant.
3) Backward structure and the set of all admissible $a_1$
From Claim 1 and the discussion above, the only ways to have $a_{n+1}\in S_0$ are:
$a_n\in S_0$ (then $a_{n+1}=a_n$), or
$12\mid a_n$ and $a_{n+1}=\dfrac{13}{12}a_n$, in which case $a_{n+1}\in S_0$iff
Let $a_1=12^t\cdot 6m$ with $t\ge 0$, $m$ odd, $5\nmid m$. Then $a_1$ has at least three proper divisors (indeed $1,2,3$ are proper divisors because $6\mid a_1$), so the step is defined. Because $12\mid a_1$ for $t\ge 1$, the first $t$ steps are forced:
Equivalently: $a_1$ is divisible by $6$, not divisible by $5$, and the exact exponent $v_2(a_1)$ of $2$ in $a_1$ is odd.
For such $a_1$, the sequence becomes constant after $t$ steps (at $13^t\cdot 6m\in S_0$); for any other $a_1$, the sequence cannot remain defined forever. ∎
by Cauchy and $Q_{2j}\le 2j$. Since $j\sqrt2=\frac{2j}{\sqrt2}<\frac{2j+1}{\sqrt2}\le \lambda(2j+1)$ for all $j$ when $\lambda>1/\sqrt2$, Alice can always take $x_{2j+1}=0$ and keep playing until the chosen time $2k-1$.
At time $2k-1$ she can force Bazza to be unable to play.
Let $t:=Q_{2k-2}\in[0,2k-2]$. By Cauchy,
so $Q_{2k-1}<2k$ and Bazza always has a legal reply. The game continues indefinitely; neither can force termination.
Thus at $\lambda=1/\sqrt2$ there is no winning strategy for either player.
Conclusion
Alice has a winning strategy iff$\displaystyle \lambda>\frac1{\sqrt2}$.
Bazza has a winning strategy iff$\displaystyle \lambda<\frac1{\sqrt2}$.
At the threshold $\displaystyle \lambda=\frac1{\sqrt2}$, optimal play leads to an infinite game; neither player can force a win.
P6
Solution
Let $n=2025$. We must choose exactly one uncovered unit square in each row and each column, and cover all the remaining squares with pairwise disjoint axis‑aligned rectangles. We seek the minimum number of rectangles.
Two simple observations guide the solution:
The condition “exactly one uncovered per row and per column” means the uncovered squares form the graph of a permutation: one in each row and one in each column.
If we permute the columns (i.e., relabel columns) by any permutation $\sigma$, then a rectangle remains a rectangle, nonoverlap is preserved, and “uncovered squares = permutation pattern” is preserved (just with a different permutation). Thus the minimum number of tiles depends only on $n$, not on which permutation we chose.
Therefore, we may assume without loss of generality that the uncovered squares are exactly the main diagonal $(i,i)$, $i=1,\dots,n$.
Key lemma (rectangles avoid the diagonal)
Consider any rectangle whose rows form an interval $[r_1,r_2]$ and whose columns form an interval $[c_1,c_2]$.
Such a rectangle contains a diagonal cell $(k,k)$ iff the intervals $[r_1,r_2]$ and $[c_1,c_2]$ intersect (i.e., there exists $k$ with $r_1\le k\le r_2$ and $c_1\le k\le c_2$).
Since all diagonal cells are uncovered, a legal rectangle must have disjoint row/column intervals. Hence every rectangle lies entirely above the diagonal ($r_2 < c_1$) or entirely below the diagonal ($c_2 < r_1$). No rectangle can straddle the diagonal.
Let $U={(i,i+1): i=1,\dots,n-1}$ (the $n-1$ cells just above the diagonal) and
$L={(i+1,i): i=1,\dots,n-1}$ (the $n-1$ cells just below the diagonal).
Claim. No legal rectangle contains two distinct cells of $U$ (and likewise, none contains two distinct cells of $L$).
Proof. Suppose $i<j$. Any rectangle containing $(i,i+1)$ and $(j,j+1)$ must have row interval $[r_1,r_2]$ with $r_1\le i<j\le r_2$ and column interval $[c_1,c_2]$ with $c_1\le i+1<j+1\le c_2$. Then the intervals $[r_1,r_2]$ and $[c_1,c_2]$ intersect (e.g., at $k=j$), so the rectangle would include $(k,k)$ on the diagonal, which is forbidden. ∎
Consequently:
Covering all squares above the diagonal requires at least $n-1$ rectangles (each can cover at most one of the $n-1$ cells in $U$).
Covering all squares below the diagonal requires at least $n-1$ rectangles (each can cover at most one of the $n-1$ cells in $L$).
Adding these, any admissible tiling uses at least
$$
(n-1)+(n-1)=2n-2
$$
rectangles.
Construction achieving the lower bound
We now build a tiling with exactly $2n-2$ rectangles:
For each $k=1,2,\dots,n-1$, place a horizontal rectangle in row $k$ covering columns $k+1,k+2,\dots,n$. These $n-1$ rectangles tile the whole region above the diagonal.
For each $k=1,2,\dots,n-1$, place a vertical rectangle in column $k$ covering rows $k+1,k+2,\dots,n$. These $n-1$ rectangles tile the whole region below the diagonal.
These two families of rectangles lie in disjoint regions (above vs. below the diagonal), so there is no overlap. Together they cover every non‑diagonal square, and leave exactly the $n$ diagonal squares $(i,i)$ uncovered—one in each row and each column.
Thus the lower bound $2n-2$ is attained, and the minimum number of tiles is exactly $2n-2$.
