Let $A_1B_1C_1D_1E_1$ be a regular pentagon.For $ 2 \le n \le 11$, let $A_nB_nC_nD_nE_n$ be the pentagon whose vertices are the midpoint of the sides $A_{n-1}B_{n-1}C_{n-1}D_{n-1}E_{n-1}$. All the $5$ vertices of each of the $11$ pentagons are arbitrarily coloured red or blue. Prove that four points among these $55$ points have the same colour and form the vertices of a cyclic quadrilateral.
Problem
Source:
Tags: combinatorics
TheDarkPrince
20.01.2019 16:56
PHP FTW. I got 5 is enough instead of 11
JRyno
20.01.2019 16:59
TheDarkPrince wrote: PHP FTW. I got 6 is enough instead of 11 No, it may be there that the 2 edges sharing the same coloured vertices are of different colour. So, there must me 3 parellel edges, so it should be$\geq11$
MathPassionForever
20.01.2019 17:00
TheDarkPrince wrote: PHP FTW. I got 6 is enough instead of 11 Your solution?
JRyno
20.01.2019 17:03
TheDarkPrince wrote: PHP FTW. I got 6 is enough instead of 11 I guess I know your solution, but I think that it should be 11 instead of 6. I may be wrong.
Math-wiz
20.01.2019 17:09
According to my solution, 9 are enough
Math-Ninja
20.01.2019 17:10
Math-wiz wrote: According to my solution... Can you show us?
JRyno
20.01.2019 17:11
Math-wiz wrote: According to my solution, 9 are enough No, way, still share the solution.
aadhitya
20.01.2019 17:27
EASY PHP (I guess....) Notice that some two adjacent vertices of every regular pentagon must be of the same color. Also by joining the mid points of a regular pentagon we get another regular pentagon whose sides are parallel to each other. Now, note that for any pentagon we have 5 pairs of adjacent vertices and 2 colors. Therefore, there are 10 possible colorings of the adjacent vertices. And since we have 11 pentagons ,the corresponding adjacent vertices of some two pentagons must be of the same color (by PHP). These four points form a monochromatic issosceles trapezium which is cyclic. Hence we are done!!!
TheDarkPrince
20.01.2019 18:43
Proof for $n=5$: (high chance its false). Notice that $A_iA_jB_iB_j$ is isosceles trapezium. If $A_nB_nC_nD_n$ are same color, we are done. WLOG, $A_1,B_1,C_1$ are red. Therefore for all $n\geq 2$, at least two of $A_n,B_n,C_n$ are blue. WLOG $A_2,B_2$ are blue. Now for $n=3,4,5$ by PHP at least one of $A_n,C_n$ and $B_n,C_n$ are blue for more than one $n$. Therefore we are done if $11$ is replaced by $5$ also.
monsterDJ
20.01.2019 18:53
I brute forced it and it got killed in n=3.
JRyno
20.01.2019 18:57
A counterexample with n=9, Sorry for my bad handwriting, but I am too lazy to latex this.
Attachments:
monsterDJ
20.01.2019 19:03
...........
TheDarkPrince
20.01.2019 19:04
^^ What's $D_4$? If it's $R_1$, $B_1D_1D_4B_4$ is cyclic and if it's $R_2$, $A_2D_2D_4A_4$.
ubermensch
20.01.2019 19:08
If anyone is trying to find a counterexample of any sorts, keep in mind that 2 consecutive pentagons(like a1b1c1d1e1 and a2b2c2d2e2) can't both have 3 vertices red or 3 vertices blue- it has to be alternating-this is easy to prove by some length casework.
Kitkat2207
20.01.2019 21:00
aadhitya wrote: EASY PHP (I guess....) Notice that some two adjacent vertices of every regular pentagon must be of the same color. Also by joining the mid points of a regular pentagon we get another regular pentagon whose sides are parallel to each other. Now, note that for any pentagon we have 5 pairs of adjacent vertices and 2 colors. Therefore, there are 10 possible colorings of the adjacent vertices. And since we have 11 pentagons ,the corresponding adjacent vertices of some two pentagons must be of the same color (by PHP). These four points form a monochromatic issosceles trapezium which is cyclic. Hence we are done!!! Why should two adjacent vertices of a regular Pentagon be of the same colour?
Kitkat2207
20.01.2019 21:06
If we can prove that then it follows that if AkBkCkDkEk has 2 red and 3 blues(WLOG) Then Ak+1Bk+1Ck+1Dk+1Ek+1 should have 3 red and two blue vertices (Which can be proved by taking cases) And the number of red and blue vertices alternates for Pentagon k and Pentagon k+1 WlOG assume A1B1C1D1E1 has 2 red and 3 blue Then out of the 55 vertices 28 should be red and 27 blue...But we wanted 22 red and 33 blue or 22 blue or 33 red... Q.e.d
Supercali
21.01.2019 11:16
I think $n=3$ suffices.
Each pentagon will have at least 4 monochromatic sides/diagonals. Each side/diagonal is parallel to one of the sides of the bigger pentagon, which we will label as $S_1,S_2,S_3,S_4,S_5$. Hence, each monochromatic side/diagonal can be labelled as $(R,S_i)$ or $(B,S_i)$ where $S_i$ denotes the bigger side to which the side/diagonal is parallel. Hence, there are only 10 diff labels but 12 monochromatic sides/diagonals. Hence we can use PHP.
Can anyone point out the mistake? Because this is (probably) wrong.
Allen4567
21.01.2019 11:22
@Supercali, Bravo!! Your solution works just fine and $n=3$ suffices.
AnArtist
21.01.2019 11:39
Supercali wrote: I think $n=3$ suffices.
Each pentagon will have at least 4 monochromatic sides/diagonals. Each side/diagonal is parallel to one of the sides of the bigger pentagon, which we will label as $S_1,S_2,S_3,S_4,S_5$. Hence, each monochromatic side/diagonal can be labelled as $(R,S_i)$ or $(B,S_i)$ where $S_i$ denotes the bigger side to which the side/diagonal is parallel. Hence, there are only 10 diff labels but 12 monochromatic sides/diagonals. Hence we can use PHP.
Can anyone point out the mistake? Because this is (probably) wrong. Yup l also think $n=3$ works. I case bashed all the possibilities.
Supercali
21.01.2019 13:42
Wow the original bound is way too weak. In fact, if we had 4 colours, the result would hold true for $n=21$ (because then each pentagon will have at least one monochromatic side/diagonal). @below: Edited, sorry
Allen4567
21.01.2019 17:16
@above, Are you sure? Because now you have $11$ colours and $4\times5=20$ labels. However, $3$ colours and 8 pentagons work as $2\times8>3\times5$.
TheDarkPrince
14.02.2019 07:46
TheDarkPrince wrote:
Proof for $n=5$:
Notice that $A_iA_jB_iB_j$ is isosceles trapezium. If $A_nB_nC_nD_n$ are same color, we are done. WLOG, $A_1,B_1,C_1$ are red. Therefore for all $n\geq 2$, at least two of $A_n,B_n,C_n$ are blue. WLOG $A_2,B_2$ are blue. Now for $n=3,4,5$ by PHP at least one of $A_n,C_n$ and $B_n,C_n$ are blue for more than one $n$. Therefore we are done if $11$ is replaced by $5$ also.
Does this work btw?
ayan.nmath
14.02.2019 08:13
TheDarkPrince wrote: Proof for $n=5$: Notice that $A_iA_jB_iB_j$ is isosceles trapezium. If $A_nB_nC_nD_n$ are same color, we are done. WLOG, $\color{red} A_1,B_1,C_1$ are red.Therefore for all $n\geq 2$, at least two of $A_n,B_n,C_n$ are blue. WLOG $A_2,B_2$ are blue. Now for $n=3,4,5$ by PHP at least one of $A_n,C_n$ and $B_n,C_n$ are blue for more than one $n$. Therefore we are done if $11$ is replaced by $5$ also. If I understand correctly, $ A_1,B_1,C_1$ are three consecutive vertices, but then how are you WLOG assuming this? Also you should clarify on how you are naming the vertices of the “inner” pentagons. @below. Your proof seems correct then
TheDarkPrince
14.02.2019 09:39
ayan.nmath wrote: If I understand correctly, $ A_1,B_1,C_1$ are three consecutive vertices, but then how are you WLOG assuming this? Also you should clarify on how you are naming the vertices of the “inner” pentagons. The naming is like: $A_{n+1}$ is the midpoint of $C_nD_n$, $E_{n+1}$ is midpoint of $B_nC_n$, and so on. Well, it doesn't matter if they are consecutive or not. Any three points have the same proof (as my proof never uses the fact of consecutive).
AhirGauss
16.06.2019 14:17
Well, it's pretty late now but here's the solution which fetched me 2/17 @below 31 (same as your post number)
Attachments:
INMO P2.pdf (146kb)
Math-wiz
16.06.2019 14:20
AhirGauss wrote: Well, it's pretty late now but here's the solution which fetched me 2/17 What was ur total?
ftheftics
30.11.2019 07:03
Since ,$A_1B_1C_1D_1E_1$..is a regular pentagon all $A_iB_iC_iD_iE_i ,2\le i\le11$ are regular pentagon . so internal angle of each pentagon is $108$° .Now if we continue the process to make new pentagons ...we should found that each side of $A_5B_5C_5D_5E_5$ are parallel to each sides of $A_1B_1C_1D1E_1$ on that order.So there exist $5$ different direction for the pentagons.since $72$°×$5=360$°.[as external angles of each pentagon ae 72°].
Now see, the vertices of pentagons whose side are parallel to another in same order should make a isoscelas trapizium.
Since,we are using two colours so each pentagon have at least two adjacent vertices having same colour.Let,call such sides(of pentagons) whose two end point have same colour is$ "good"$. So there is at least 11$ "good" $sides .
Now, we have proved before that pentagons are arranged in $5 $ different direction. so there is $3 $,$"good "$ lines parallel to each other among these at least 2 parallel$ "good "$ line contain same colour .
It, immediately implies that there exist at least 1 isoscelas trapizium having all vertices same colour . it's easy to see that isosceles trapizium is cyclic.
This complete our proof.$\boxed{\square}$.
........$\frac{\Delta \sum n}{\angle m}$...........
gabrupro
12.01.2020 13:43
monsterDJ wrote: I brute forced it and it got killed in n=3.
First of all, it is trivial that four points of the same colour cannot exist in the same pentagon. Now show by casework that if A1B1C1D1E1 has 3 red pts then A2B2C2D2E2 has 3 blue pts. Now show again by casework that if A1B1C1D1E1 has 3 red pts then A3B3C3D3E3 has 3 blue pts. These statements contradict each other and hence we have that between any three pentagons defined in the given way (the indices need not be consecutive) there exists at least one cyclic quadrilateral with all its vertices of the same colour
455264
05.02.2020 13:41
richardrichard wrote: monsterDJ wrote: I brute forced it and it got killed in n=3.
First of all, it is trivial that four points of the same colour cannot exist in the same pentagon. Now show by casework that if A1B1C1D1E1 has 3 red pts then A2B2C2D2E2 has 3 blue pts. Now show again by casework that if A1B1C1D1E1 has 3 red pts then A3B3C3D3E3 has 3 blue pts. These statements contradict each other and hence we have that between any three pentagons defined in the given way (the indices need not be consecutive) there exists at least one cyclic quadrilateral with all its vertices of the same colour
Which material do you use to prepare for combinatorial colouring theory? Please help as I am having problems with colouring problems