Special Problem Marathon

Discussion on Bangladesh National Math Camp
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Re: Problem 8

Unread post by Anindya Biswas » Sun Jun 06, 2021 3:33 pm

rah4927 wrote:
Sun Jun 06, 2021 4:13 am
There is a game show with $100$ contestants labelled $1, 2, \ldots, 100$. There are $100$ doors in this game show, each having a distinct hidden number from the set $\{1, \ldots, 100\}$. The contestants are not allowed to communicate with each other during the game. During the game, each contestant's objective is to find the door with their own label behind it. They are allowed to do the following things:

1. Contestant $i$ is allowed to open one door at a time, up to a total of $50$ doors. In particular, this means that they do not have to guess all $50$ doors prior to opening them. If one of the opened doors contains the number $i$ behind it, then contestant $i$ wins.

2. None of the other contestants are privy to what contestant $i$ saw behind the doors. In particular, this means that after the game begins, the contestants cannot communicate with each other.

However, Ipshita, who is in charge of the doors, has bet her friend that all $100$ contestants can win this game. But in order to make this happen, she is allowed to exchange the numbers behind two doors (and she can do this operation exactly once). Devise a strategy for Ipshita and the $100$ contestants so that they can all win the game show.

Note: Ipshita can see the numbers behind the doors, but once she does so she is not allowed to communicate with the contestants.
Let's assume door $i$ contains the hidden number $\sigma(i)$ where $\sigma:\{1,2,3,\cdots,100\}\to\{1,2,3,\cdots,100\}$ is a bijective function.
Contestant's strategy : They will have to search in cycles. $i$th contestant will search the doors $i, \sigma(i),\sigma^2(i),\cdots, \sigma^{49}(i)$. Where they would find the hidden numbers $\sigma(i),\sigma^2(i),\sigma^3(i),\cdots,\sigma^{50}(i)$ respectively. This strategy guarantees the highest probability of finding their number.
Ipshita's Strategy : In order to get things work, she must do something so that each cycle has a length of at most $50$. Since the sum of the length of the cycles is always $100$, the number of cycles of length greater then $50$ is at most $1$. So, if there is a cycle of length more than $50$, Ipshita would choose door number from that cycle and swap the numbers in the doors $\sigma^{49}(i), \sigma^{-1}(i)$. Thus, we will have $\sigma^{50}(i)=i$ which is contained in a cycle of length $50$. So, the other cycles will have a length of at most $50$. So Ipshita's job is done in this case.
However, if there is no cycle of length more than $50$, then she would try to find a cycle of length at least $2$, and swap two numbers from door numbers in that cycle. This won't affect the othe cycles. So this cycle length won't increase.
If $\sigma(i)=i$ for all $i\in\{1,2,3,\dots,100\}$, then swapping any two random numbers is sufficient.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Problem 09

Unread post by Anindya Biswas » Sun Jun 06, 2021 3:59 pm

Let $n\geq3$ be a fixed positive integer. A function $f:\mathbb{R}^2\to\mathbb{R}$ has the property that for any points $P_1, P_2,\cdots,P_n$ which are vertices of a regular $n$-gon, we have \[\sum_{i=1}^{n}f(P_i)=0\]
Prove that $f(P) = 0$ for all points $P\in\mathbb{R}^2$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

thczarif
Posts:21
Joined:Mon Sep 25, 2017 11:27 pm
Location:Dhaka,Bangladesh

Re: Problem 09

Unread post by thczarif » Mon Jun 07, 2021 12:52 pm

Anindya Biswas wrote:
Sun Jun 06, 2021 3:59 pm
Let $n\geq3$ be a fixed positive integer. A function $f:\mathbb{R}^2\to\mathbb{R}$ has the property that for any points $P_1, P_2,\cdots,P_n$ which are vertices of a regular $n$-gon, we have \[\sum_{i=1}^{n}f(P_i)=0\]
Prove that $f(P) = 0$ for all points $P\in\mathbb{R}^2$.
Let the vertices of a regular $n$ gon be $\{A_{1,k}\}_{k=1}^{n}$ in clockwise order.

Now fix the point $A_{1,1}$ in its place and rotate the polygon by $\theta= \left(\frac{360}{n} \right)^\circ$ and let the new points be defined as $\{A_{2,k}\}_{k=1}^{n}$ such that $A_{1,i} \to A_{2,i}$. Now rotate the polygon total $n-1$ times by angle $\theta$ and define those polygons as $\{A_{i,j}\}_{j=1}^{n}$ where it is the $i$ polygon. Now we can easily check that,

\[\sum_{j=1}^{n}f(A_{i,j})=0 \quad \forall i\]

And the polygons $\{A_{i,j}\}_{i=1}^{n}$ where $2 \leq j \leq n$ are also regular with center $A_{1,1}$. So,

\[\sum_{i=1}^{n}f(A_{i,j})=0 \quad \forall j \ s.t. 2 \leq j \leq n\]

Now, we have that,

\begin{align*}
\sum_{i=1}^{n}\sum_{j=1}^{n}f(A_{i,j}) &= nf(A_{1,1})+\sum_{j=2}^{n}\sum_{i=1}^{n}A_{i,j}\\
\Rightarrow nf(A_{1,1})&=0\\
\Rightarrow f(A_{1,1})&=0
\end{align*}



So, $f(P)=0$ for all $P \in \mathbb{R}^2$

thczarif
Posts:21
Joined:Mon Sep 25, 2017 11:27 pm
Location:Dhaka,Bangladesh

Problem 10

Unread post by thczarif » Mon Jun 07, 2021 12:58 pm

Define a function $f: \mathbb N \to \mathbb N$ by $f(1) = 1$, $f(n+1) = f(n) + 2^{f(n)}$ for every positive integer $n$. Prove that $f(1), f(2), \cdots, f(3^{2013})$ leave distinct remainders when divided by $3^{2013}$.
USA TSTST 2013 P8

User avatar
FuadAlAlam
Posts:30
Joined:Wed Sep 16, 2020 11:10 am
Location:Dhaka, Bangladesh
Contact:

Problem 11

Unread post by FuadAlAlam » Mon Jun 14, 2021 7:13 pm

In a $\triangle ABC$, $D$ and $E$ are respectively on $AB$ and $AC$ such that $DE\parallel BC$. $P$ is the intersection of $BE$ and $CD$. $M$ is the second intersection of $(APD)$ and $(BCD)$, $N$ is the second intersection of $(APE)$ and $(BCE)$. $w$ is the circle passing through $M$ and $N$ and tangent to $BC$. Prove that the lines tangent to $w$ at $M$ and $N$ intersect on $AP$.

NujhatDisha
Posts:2
Joined:Thu Dec 03, 2020 11:07 pm

Solution of Problem 11

Unread post by NujhatDisha » Wed Jun 16, 2021 12:56 am

Let $AP \cap BC=L$

$LM\cap AC=F$

$LM \cap DE=K$

$LN\cap AB=Q$

$LN\cap DE=J$

Let $\measuredangle$ denote directed angle.

$\underline{Claim:}$ Circle $MNL$ is tangent to $BC$ at $L$ that is $w$ is tangent to $BC$ at $L$.

$\underline{Proof:}$ Clearly $M,N$ are the centers of spiral similarity sending $AP$ to $BC$ and $CB$ respectively.

$\measuredangle BPN = \measuredangle BLN = \measuredangle EJN \Rightarrow AJNPE$ is cyclic.

Similarly $ADPKM$ is cyclic.

$\therefore LN.LJ=LP.LA=LK.LM \Rightarrow JNKM$ is cyclic.

$\measuredangle LMN=\measuredangle KJL=\measuredangle BLN$

$\therefore$Circle $ MNL$ is tangent to $BC$ at $L$ $\blacksquare$

$\underline{Claim:}$ $AL$ bisects $JK$.

$\underline{Proof:}$ We can easily show that $L$ is the midpoint if $BC$.

$\measuredangle FAN= \measuredangle BLN = \measuredangle LMN \Rightarrow AMNF$ is cyclic

Similarly $AMNQ$ is cyclic $\Rightarrow AMNFQ$ is cyclic.

$\measuredangle FQN=\measuredangle FAN= \measuredangle EJN \Rightarrow QF\parallel DE \parallel BC$

Since $BL=LC$, by lenght chasing we can show $JD=EK$

But $AL$ bisects $DE \Rightarrow AL$ bisects $JK$ $\blacksquare$

Now $\triangle LJK \sim \triangle LMN$

$LA$ is the $L$-median of $\triangle LJK$

$\therefore LA$ is the $L$-symmedian of$\triangle LMN$

$\therefore$ Tangents to $w$ at $M,N$ intersect on $AP$.

NujhatDisha
Posts:2
Joined:Thu Dec 03, 2020 11:07 pm

Problem 12

Unread post by NujhatDisha » Wed Jun 16, 2021 4:31 pm

Given an acute triangle $ABC$, point $D$ is chosen on the side $AB$ and a point $E$ is chosen on the extension of $BC$ beyond $C$. It became known that the line through $E$ parallel to $AB$ is tangent to the circumcircle of $\triangle ADC$. Prove that one of the tangents from $E$ to the circumcircle of $\triangle BCD$ cuts the angle $\angle ABE$ in such a way that a triangle similar to $\triangle ABC$ is formed.

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Problem 12

Unread post by Anindya Biswas » Thu Jun 17, 2021 10:53 pm

NujhatDisha wrote:
Wed Jun 16, 2021 4:31 pm
Given an acute triangle $ABC$, point $D$ is chosen on the side $AB$ and a point $E$ is chosen on the extension of $BC$ beyond $C$. It became known that the line through $E$ parallel to $AB$ is tangent to the circumcircle of $\triangle ADC$. Prove that one of the tangents from $E$ to the circumcircle of $\triangle BCD$ cuts the angle $\angle ABE$ in such a way that a triangle similar to $\triangle ABC$ is formed.
Click here for the figure

Let $F$ be the point on $\circ ADC$ such that $EF$ is tangent to $\odot ADC$.
Let $G$ be the intersection point of $FD$ and $\odot BDC$ other than $D$.
Here, $\measuredangle FGC=\measuredangle DGC=\measuredangle DBC=\measuredangle FEC$ (By the properties of cyclic quadrilateral $DBCG$ and parallel lines $DB$ and $FE$)
$\therefore FECG$ is concyclic.
$\therefore \measuredangle CEF=\measuredangle CGD$
By alternate segment theorem, $\measuredangle EFC=\measuredangle GDC$
$\therefore \triangle CEF\sim\triangle CGD$
By Spiral similarity,
$\triangle CEG\sim\triangle CFD$
$\therefore \measuredangle EGC=\measuredangle GDC$
By alternate segment theorem, $EG$ is tangent to $\odot BDC$.

Let $H$ be the intersection point of $FA,\odot CEF$ other than $F$.
Here $\measuredangle AHC=\measuredangle FHC=\measuredangle FGC=\measuredangle DBC=\measuredangle ABC$.
So, $A,B,H,C$ concyclic.
$\therefore \measuredangle CHB=\measuredangle CAB$.
Here, $\measuredangle HAC=\measuredangle FAC=\measuredangle FDC=\measuredangle GDC$
and $\measuredangle CHA=\measuredangle CBA=\measuredangle CBD=\measuredangle CGD$
So, $\triangle CHA\sim \triangle CGD$
By Spiral similarity,
$\triangle CHG\sim\triangle CAD$.
$\therefore \measuredangle CHG=\measuredangle CAD=\measuredangle CAB=\measuredangle CHB$
So, $H,G,B$ collinear.
Let $I=EG\cap AB$.
$\therefore \measuredangle BEI=\measuredangle CHB=\measuredangle CAB$
$\therefore \triangle CAB\sim BEI$ and $EI$ is tangent to $\odot BDC$.
$\text{Q.E.D.}$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Problem 13

Unread post by Anindya Biswas » Thu Jun 17, 2021 11:42 pm

Let $k$ be a fixed positive integer. Let $\mathbb{N}$ be the set of all positive integers. A function $f:\mathbb{N}\to\mathbb{N}$ satisfies the condition \[\sum_{i=1}^{k}f^i(n)=kn\] For all $n\in\mathbb{N}$. Here $f^i(n)$ is the $i$-th iteration of $f$. Prove that $\forall n\in\mathbb{N}, f(n)=n$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

thczarif
Posts:21
Joined:Mon Sep 25, 2017 11:27 pm
Location:Dhaka,Bangladesh

Re: Problem 13

Unread post by thczarif » Sat Jun 19, 2021 12:31 pm

Anindya Biswas wrote:
Thu Jun 17, 2021 11:42 pm
Let $k$ be a fixed positive integer. Let $\mathbb{N}$ be the set of all positive integers. A function $f:\mathbb{N}\to\mathbb{N}$ satisfies the condition \[\sum_{i=1}^{k}f^i(n)=kn\] For all $n\in\mathbb{N}$. Here $f^i(n)$ is the $i$-th iteration of $f$. Prove that $\forall n\in\mathbb{N}, f(n)=n$.
We will prove this by induction.

Claim 1: $f$ is injective.

If $f(a)=f(b)$ for some $a,b \in \mathbb{N}$ then $f^i(a)=f^i(b)$ for all $i\in \mathbb{N}$. So,

\[ka=\sum_{i=1}^kf^i(a)=\sum_{i=1}^kf^i(b)=kb \Rightarrow a=b\]

Claim 2: $f(1)=1$

If for some $i$ $f^i(1)>1$ then,

\[\sum_{i=1}^kf^i(1) >k\]

So, $f^i(1)=1$ for all $i$ so, $f(1)=1$.

Claim 3: $f(i)=i$ for all $i\in \mathbb{N}$

Lets assume that $f(i)=i$ for all $1 \leq i \leq m$. Now, $f(m+1) \nleq m$ since $f$ is injective. If $f(m+1) \neq m+1$ then $f(m+1) >m+1$. And so, $f^i(m+1) \nleq m$ for any $i$ because of injectivity. Now,

\[\sum_{i=1}^kf^i(m+1) > k(m+1)\]

which is a contradiction. So, $f(m+1)=m+1$. $ \blacksquare$

Post Reply