Combinatorics #3

by anantmudgal09, Sep 1, 2017, 10:12 AM

A while ago, Utkarsh showed me the cool maximal matching trick. Here's another really cool problem using it.

(PuMac 2013) Let $G$ be a graph with more than $2(k-1)^2$ edges. Prove that at least one of the following holds:

$G$ has a vertex of degree at least $k$ ;
$G$ has a matching of size at least $k$ .

solution

Combinatorics #2

by utkarshgupta, Feb 18, 2017, 10:46 AM

Problem (ISL 2004 C5) :
$A$ and $B$ play a game, given an integer $N$ , $A$ writes down $1$ first, then every player sees the last number written and if it is $n$ then in his turn he writes $n+1$ or $2n$ , but his number cannot be bigger than $N$ . The player who writes $N$ wins. For which values of $N$ does $B$ win?

Proposed by A. Slinko & S. Marshall, New Zealand

Idea of Solution

combinatorics

ISL 2004

2004

Combinatorics #1

by utkarshgupta, Feb 17, 2017, 1:57 PM

JEE preps are adversely impacting my thinking ability.
So I will try and do something that I didn't even do when I was actually preparing for the olympiads

Actually think !
It's trivial I know I know...
But it was fun !

Problem (ISL 2015 C1) :
In Lineland there are $n\geq1$ towns, arranged along a road running from left to right. Each town has a left bulldozer (put to the left of the town and facing left) and a right bulldozer (put to the right of the town and facing right). The sizes of the $2n$ bulldozers are distinct. Every time when a left and right bulldozer confront each other, the larger bulldozer pushes the smaller one off the road. On the other hand, bulldozers are quite unprotected at their rears; so, if a bulldozer reaches the rear-end of another one, the first one pushes the second one off the road, regardless of their sizes.

Let $A$ and $B$ be two towns, with $B$ to the right of $A$ . We say that town $A$ can sweep town $B$ away if the right bulldozer of $A$ can move over to $B$ pushing off all bulldozers it meets. Similarly town $B$ can sweep town $A$ away if the left bulldozer of $B$ can move over to $A$ pushing off all bulldozers of all towns on its way.

Prove that there is exactly one town that cannot be swept away by any other one.

Solution :
Let the statement be true for $k \le n$ .

Let the towns be labelled $T_i$ from left to right and their left and right bulldozer $l_i,r_i$ respectively.

Now we have to prove the statement for $n+1$ towns..
Consider the rightmost town $T_{n+1}$ and let some $r_j$ collide with $l_{n+1}$

Then there are two cases :
$l_{n+1}$ derails all such $r_j$ . Then obviously $T_{n+1}$ is the new winner town !

If some $r_j$ derails $l_{n+1}$ . Then obviously since there is no other bulldozer between this point and $T_{n+1}$ ,
$r_j$ sweeps $T_{n+1}$
Since there are no bulldozers between $T_j$ and $T_{n+1}$ , The first $j$ towns live unaffected by the remaining towns. And hence by inducton we are done.

ISL

2015

combinatorics

Random Random FE

by utkarshgupta, Feb 16, 2017, 2:09 AM

Problem :
Find all functions $f : Let$ $f:\mathbb{R}\to \mathbb{R}$ such that
$f(x^{2}+y+f(y))=2y+f(x)^2$

Okay....
Here it goes...

Solution :
Let $P(x,y)$ be the assertion
$f(x^{2}+y+f(y))=2y+f(x)^2.$
And let $k=\frac{-f(0)^2}{2}$
$P(0,k) \implies f(k)=0$
Now let if possible, there exist some $a \neq k$ such that $f(a)=0$ ,
$P(0,a) \implies f(a) = f(0)^2 + 2a \neq 0$

A contradiction !

Hence $f(t) = 0 \implies t = k$ .

Let $f(0)=c$ then $k = \frac{-c^2}{2}$ .

$P(k,0) \implies f(k^2+f(0)) = f(k)^2 = 0$ $\implies k^2 + c = k$ $\implies c = 0,2$
Let if possible $c=2 \implies k=-2$
Then $P(0,0) \implies f(2) = 4$
$P(0,k) \implies f(2) = 0$

A contradiction !

$\boxed {f(0) = 0}$ And there exists no $a \neq 0$ such that $f(a)=0$

$P(x,\frac{-f(x)^2}{2}) \implies f(x^2 + \frac{-f(x)^2}{2} + f(\frac{-f(x)^2}{2})) = 0$ $\implies x^2 + \frac{-f(x)^2}{2} + f(\frac{-f(x)^2}{2}) = 0$
Thus if $f(a) = f(b)$ then $a^2 = b^2$

Let if possible $f(a) = f(-a)$ for some $a \neq 0$
$f(a + f(a)) = 2a = -f(-a + f(-a))$
Hence $f((a+f(a))^2) = f((-a+f(a))^2)$ Since $x^2 > 0$ ...
We must have $a^2+f(a)^2+2af(a) = a^2 + f(a)^2 - 2af(a)$
That is either $a= 0$ or $f(a) = 0$
A contradiction !

Hence $f$ is injective.

$P(x,0) \implies f(x^2) = f(x)^2 \ge 0$ $P(0,y) \implies f(y+f(y)) = 2y$
Let $z^2 - y^2 + f(z^2) - f(y^2) = x^2$ (assume greater than zero or else we can assume it to be equal to $-x^2$ )
$P(x^2,y^2) \implies f(x^2+y^2 + f(y^2)) = f(x^2) + 2y^2$ $P(0,z^2) \implies f(z^2+f(z^2)) = 2z^2$ $\implies f(x^2 + f(z^2) - f(y^2)) = 2(y^2-z^2) = f(x^2 + f(x^2))$ Since $f$ is injective
$f(x^2+y^2) = f(x^2) + f(y^2)$ .
We also have $-f(x) = f(-x)$ and $f(x^2) > 0$
So by Cauchy we are done !

That is $\boxed {f(x)=x}$ is the only solution !

This post has been edited 2 times. Last edited by utkarshgupta, Feb 16, 2017, 4:31 AM

functional equation

AoPS

Slick Projectives!

by anantmudgal09, Sep 4, 2016, 6:15 PM

Dedicated to Utkarsh, a one-line proof of the isogonality lemma.

Lemma: Let $A,B,C,X,Y$ be five points in the general position in the plane. Suppose that $AX,AY$ are isogonal lines in angle $BAC$ and $P=BX \cap CY$ and $Q=CX \cap BY$ . Then, $AP,AQ$ are isogonal in angle $BAC$ .

Proof (communicated to me by user liberator):- By applying the dual of Desrague's involution theorem on the quadruple $\{PX,XQ,QY,YP\}$ we conclude that an involution swaps $AB \rightarrow AC$ , $AX \rightarrow AY$ and $AP \rightarrow AQ$ . Since $AX,AY$ are isogonal, the involution is in fact the reflection in the bisector of angle $BAC$ and the result follows.

I will try looking for more applications of this idea. There is a somewhat longer but projectively insightful proof using dynamic, but let's save it for another blog post.

Matrices :D :D :D

by utkarshgupta, Jul 4, 2016, 3:56 AM

Long time people

This sure is nice and I wouldn't have been able to solve it without first solving the $3 \times 3$ version.

Problem (Romanian Mathematical Olympiad Grade XI) :
Let $A=(a_{ij})_{1\leq i,j\leq n}$ be a real $n\times n$ matrix, such that $a_{ij} + a_{ji} = 0$ , for all $i,j$ . Prove that for all non-negative real numbers $x,y$ we have $\det(A+xI_n)\cdot \det(A+yI_n) \geq \det (A+\sqrt{xy}I_n)^2.$
Solution :
Let $f(x)=det(A+xI_{n})$
Obviously $f$ is a polynomial.
So we have to show that $f(x)f(y) \ge f(\sqrt{xy})^2$

But the above result will follow directly once we establish that all the coefficients of $f$ are positive.
$f(0)=0$ obviously.

I will call the kind of matrices asked in the question as ski matrix.
To show this I will use induction on the order of the matrix.
Let the result be true for all such $n-1 \times n-1$ ski matrices.

Now consider any $n \times n$ such ski matrix and call it $f_n(x)$ .
Then,
$f_n(x) = \int^{x}_{0} f_{n}^{'}(x)$ But obviously since $f_{n}^{'}(x)$ is a sum of determinants of ski matrices of the order $n-1 \times n-1$ , all it's coefficients by the induction hypothesis are positive and hence so are it's integrals (except the constants which we have already established as zero).

Hence $f(x)$ has all it's coefficients positive and hence by Cauchy Schwartz inequality, we are done.

linear algebra

Matrices

romanian mathematical olympiad

Bad news for the Isogonal Lemma

by anantmudgal09, May 25, 2016, 8:24 PM

Lol, it turns out that some Russians knew of it since much before we used it; this exact Lemma was a problem in the 2004 Saint Petersburg Math Olympiad Round 2 given to ninth graders as problem 6/8 (meaning they think it is easy synthetically

)

So much for our joint venture in August last year....

A line through an orthocenter.

by anantmudgal09, May 22, 2016, 7:54 PM

Ok, since Utkarsh is probably busy catching up on his JEE prep, I shall post the following nice problem.

In equilateral triangle $ABC$ , let $l$ be a line through $B$ not intersecting the interior of the triangle. Let circles $\omega_1,\omega_2$ be tangent to base $AC$ and line $l$ and to sides $BA,BC$ at points $C',A'$ respectively and their centres being points $O_1,O_2$ . Prove that if $H$ is the orthocenter of triangle $A'BC'$ then points $H,O_1,O_2$ are on a line.

Sketch

ISL 2009 G4

by utkarshgupta, Apr 25, 2016, 11:51 AM

This proof is for Anant who asked me for a coordinate bash in the shouts

I wasn't able to solve it synthetically (at least last year

)

Problem : (ISL 2009)
Given a cyclic quadrilateral $ABCD$ , let the diagonals $AC$ and $BD$ meet at $E$ and the lines $AD$ and $BC$ meet at $F$ . The midpoints of $AB$ and $CD$ are $G$ and $H$ , respectively. Show that $EF$ is tangent at $E$ to the circle through the points $E$ , $G$ and $H$ .

Proposed by David Monk, United Kingdom

Solution :
We will work in the Cartesian plane.
$X=(x,y)$ will mean that the $x$ , $y$ coordinates of the point $X$ are $x_1,y_1$ respectively.
The slope of a line $l$ will be denoted by $m_l$ .

Without loss of Generality,
$E=(0,0)$ ,
$A=(1,0)$ ,
$C=(-pq,0)$
Let $m_{BD}=\tan{\theta}$

So set
$B=(p\cos{\theta},p\sin{\theta})$
Using $B,D$ lie on the opposite sides of $AC$ , and $EB \cdot ED = EA \cdot EC$ .

$D=(-q\cos{\theta},-q\cos{\theta})$
Now easy calculations yield
$F = AD \cap BC$
$F = (\frac{q(p+q+\cos{\theta})+pq\cos{\theta}}{q^2-1},\frac{q\sin{\theta}(1+pq)}{q^2-1})$ $G= (\frac{1+p\cos{\theta}}{2},\frac{p\sin{\theta}}{2})$ $H= (\frac{-pq-q\cos{\theta}},\frac{-q\sin{\theta}}{2})$
Observe that the given problem is equivalent to proving directed angles, $\angle FEG = \angle EHG$

That is $\frac{m_{GH}-m_{EH}}{1+m_{GH}m_{EH}} = \frac{m_{GE}-m_{EF}}{1+m_{GE}m_{EF}}$

Now this is just easy calculations (they are actually easy as most of the things cancel out).

This post has been edited 3 times. Last edited by utkarshgupta, Apr 25, 2016, 11:54 AM

geometry

ISL 2009

coordinate

A Hard Geometry

by utkarshgupta, Apr 16, 2016, 5:54 AM

It took me so long to solve. Only if I knew a few projective theorems.

Problem : (RMM 2013 Problem 3)
Let $ABCD$ be a quadrilateral inscribed in a circle $\omega$ . The lines $AB$ and $CD$ meet at $P$ , the lines $AD$ and $BC$ meet at $Q$ , and the diagonals $AC$ and $BD$ meet at $R$ . Let $M$ be the midpoint of the segment $PQ$ , and let $K$ be the common point of the segment $MR$ and the circle $\omega$ . Prove that the circumcircle of the triangle $KPQ$ and $\omega$ are tangent to one another.

Solution :

Let $O$ be the center of $\odot ABCD$ .
Let $Q'=\odot PAD \cap PBC$ and $R' = \odot RCD \cap \odot RAB$ .
Let $M'$ be the reflection of $P$ in $Q'$

Lemma : $\angle OQ'P = \angle OR'P = 90$
Proof :
Well known

Obviously, $PRR'$ is a straight line (radical axis are concurrent).
Let $OR \cap PQ = Q_1$
Then, since $PQ$ is the polar od $R$ , $OQ_1 \perp PQ$
$\implies Q' = Q_1$

Thus $PRR'$ and $ORQ'$ are straight lines..

We know that $OL'Q'K'$ and $OR'Q'P$ are cyclic quadrilaterals.
$\implies RK' \cdot RL' = RO \cdot RQ' = RR' \cdot RP$

Hence $\boxed{R' \in \odot PK'L'}$

It is well known that $Q' \in PQ$
Since $Q'$ lies on the polar of $R$ ,
$R \in K'L'$
Also since $ORQ'$ is a straight line; $R$ is the midpoint of $K'L'$ and $K'L' || PQ$

Since $M'$ is the reflection of $P$ about $Q'$ , $M'$ is the reflection of $P$ about $OQ'$
Hence $L'P = K'M'$
That is $\boxed{M ' \in \odot PK'L'}$

Using the above results,
$PL'R'K'M'$ is a cyclic pentagon.

Now invert with radius $\sqrt{PB \cdot PA}$ and centre $P$ .

Obviously $Q' \to Q, M' \to M , R' \to R, \odot(ABCD) \to \odot{ABCD},K' \to K'', L' \to L''$
The cyclic pentagon implies, $K'',L'' \in MR$ and $K'',L'' \in \odot(ABCD)$

Thus one of $K'',L''$ maps to $K$ .
Since $QK',QL'$ are tangent to $\odot (ABCD)$ ;
$\odot K''PQ$ and $\odot L''PQ$ are tangent to $\odot(ABCD)$ .

QED.

Submit

Here goes first post of 2025! Great blog.
by math_holmes15, Jan 14, 2025, 8:53 AM
First post of 2024
by Yiyj1, Feb 8, 2024, 5:40 AM
First post of 2023
by HoRI_DA_GRe8, Jul 22, 2023, 7:45 AM
Nice blog ! Your isogonality lemma is really powerful !
by 554183, Oct 14, 2021, 8:55 AM
Post plss....
by samrocksnature, Apr 11, 2021, 10:12 PM
alas,this is ded
by Hamroldt, Mar 18, 2021, 4:13 PM
Thanks for the nice blog.
by Feridimo, Mar 6, 2020, 4:17 PM
I think this might be silly but ... when should we expect to have another post ?? I am very keen to see it
by gamerrk1004, Nov 4, 2019, 4:54 PM
Let's all echo what's written in the blog description - Stay Insane / 'Cause it's your labor, will and pain/ That takes you to the top of soda fountain
by Kayak, Oct 2, 2017, 7:18 PM
hey utkarsh jee is over now ... continue your elementary blog pleaseeeeeee!
by kk108, Jun 17, 2017, 11:19 AM
Congrats on becoming a contest moderator!
by Ankoganit, Mar 9, 2017, 5:22 AM
INTERSTING BLOG
by kk108, Feb 19, 2017, 2:04 PM
I have no plans for this blog right now....
No time here people !
But lets see....
I may try some combinatorics
by utkarshgupta, Feb 15, 2017, 12:47 PM
Thanks for the nice blog!
by Orkhan-Ashraf_2002, Feb 13, 2017, 6:34 PM
Revive it!!!
Best blog out there, for sure!
by rmtf1111, Jan 12, 2017, 6:02 PM
Oh you certainly will..
Bu I don't think I will
by achilles04, Feb 11, 2015, 6:24 PM
Thanks
Hope you are there too ...

And hope I get selected
by utkarshgupta, Feb 11, 2015, 11:14 AM
Nice blog ..
keep it up and you might one day become a mathematician lIke me
( just joking )
Btw don't forget us after going to imotc.
by achilles04, Feb 10, 2015, 4:49 PM
nice blog!!!!!
by pradhit, Feb 7, 2015, 11:51 AM
No ideas about the cut off but should be less than 60 according to me...
So you never know
by utkarshgupta, Feb 6, 2015, 4:06 PM
Hi utkarsh,
what do u expect the cutoff to be this year??

by kgdpsdurg, Feb 6, 2015, 12:41 PM
Hi utkarsh
How many did you clear in INMO 2015?
by moldevort, Feb 1, 2015, 3:59 PM
@ Anonymous Bunny
If we both (that should have included me) are lucky enough !
by utkarshgupta, Sep 17, 2014, 2:44 AM
Nice blog. Great job!

If I am lucky enough, hopefully we shall meet at IMOTC.
by AnonymousBunny, Sep 16, 2014, 8:08 PM
Thanx all !!

If anyone wish to contribute anything just pm !

I will add u to the contributors' list !
by utkarshgupta, Sep 16, 2014, 6:35 AM
doing good progress!! btw nice blog.
by rachitgoel, Sep 15, 2014, 4:21 PM
Nice blog.
by Kezer, Aug 5, 2014, 4:04 PM
Hi Utkarsh! Wonderful blog. Keep it up.
by YESMAths, Jul 20, 2014, 1:36 PM
I need some shouts and characters

by utkarshgupta, Jul 20, 2014, 4:22 AM