Betal marks $2021$ points on the plane such that no three are collinear, and draws all possible segments joining these. He then chooses any $1011$ of these segments, and marks their midpoints. Finally, he chooses a segment whose midpoint is not marked yet, and challenges Vikram to construct its midpoint using only a straightedge. Can Vikram always complete this challenge? Note. A straightedge is an infinitely long ruler without markings, which can only be used to draw the line joining any two given distinct points. Proposed by Prithwijit De and Sutanay Bhattacharya
Problem
Source: INMO 2021 Problem 3
Tags: geometry, construction, INMO
07.03.2021 14:11
My solution (terser than the official):
07.03.2021 14:29
Kinda straightforward. But I liked this one. We will be using our weapons Parallelo456 and Midsegmento789 from here. Notice that if there $n$ odd points in the plane, and there are $\frac{(n+1)}{2}$ line segments joining some of the $n$ points, then atleast two of the line segments have a common vertex. So we are just left to prove this famous fact. $\textbf{FACT:}$ $ABC$ be a triangle with midpoints $BC,CA,AB$ marked, then for any segment $PQ$ in the plane we can find its midpoint only using a straightedge.
$\quad\blacksquare$
07.03.2021 14:32
More (similar) ruler constructions can be found here Edit: A similar idea was used in solving Sharygin P21 this year as pointed by amar_04
07.03.2021 14:35
$ $
07.03.2021 14:47
How to draw parallel line using only straightedge ?
07.03.2021 14:50
I think you didn't considered the case when four points form a trapezium with midpoint marked on opposite sides . With use of straightedge you can find midpoint of other 2 sides and diagonals of that figure
07.03.2021 16:23
Here's another (a little complicated for no reason at all) sol. We know we have a triangle and we can prove that we can convert any connected component into a clique. Now we prove that Given a triangle ABC, with midpoints DEF, we can connect BP for any P. To see this let PC meet EF at G. Then notice that the line connecting $CF \cap DE$ and $BE \cap DF$ is parallel and midway between EF and BC. let this intersect DG at M, then if M intersects DG at K and K intersect EF at S, then SGCD is a parallelogram and so just extend DS to meet PB at its midpoint. Now if we connect everything to B, its all connected so boom.
07.03.2021 16:38
anantmudgal09 wrote: My solution (terser than the official):
I did prove the lemma that you mentioned and showed and used php, can I expect at least 3 marks?
07.03.2021 18:12
How can one draw a parallel line using only a straightedge? Thanks @below
07.03.2021 18:28
spicemax wrote: How can one draw a parallel line using only a straightedge?
This is how we do it. The red segment $AB$ and its midpoint $M$ are given and we want to draw a line through $P$ parallel to $AB$. Take $X$ to be a point on $AP$. Let $XM\cap BP=V$ and let $AV\cap XB=Q$. By Ceva's Theorem we get $\frac{XP}{PA}\cdot\frac{AM}{MB}\cdot\frac{BQ}{QA}=1$ and as $AM=MB$ we have $\frac{XP}{PA}=\frac{XQ}{QB}$. Hence, by Thales we have $PQ\parallel AB$.
07.03.2021 18:59
The statement of this theorem felt slightly scam, since all we really need is that there are points $A,B,C$ such that the midpoint of $AB = M$ and midpoint of $AC = N$. With the above configuration, one can find the midpoint of any segment $UV$. Observe by PHP that we indeed do have a structure similar to what is above described. Even so, I really liked the problem. The following two claims are crucial. [having seen them before helped :p] Claim 1: Given segment $AB$ with midpoint $M$, once can construct a line parallel to $AB$ Proof: Pick arbitrary $C$, $X$ on $CM$ and let $AX, BX$ meet $BC, AC$ at $Y, Z$. By Ceva's $YZ$ is the desired line. Claim 2: Given segment $AB$ and parallel line $YZ$, one can construct the midpoint of $BC$ Proof: Let $AY$ meet $BZ$ at $X$ and let $AZ$ meet $BY$ at $C$. By Ceva's $CX$ passes through the midpoint of $AB$. Main proof: We use this rewording: The statement of this theorem felt slightly scam, since all we really need is that there are points $A,B,C$ such that the midpoint of $AB = M$ and midpoint of $AC = N$. With the above configuration, find the midpoint of any segment $UV$. Let $X, Y$ be the midpoints of $MB$ and $NC$. By claim 1 we can draw line parallel to $AB\AC$ and by claim 2 we can draw in $X, Y$. Let $BC$, $XY$ and $MN$ meet $UV$ at $I, J$ and $K$. Observe that $J$ is the midpoint of $IK$. By claim 1 draw a line parallel to $IK$, and by claim $2$ draw in the midpoint of $UV$.
07.03.2021 20:35
How can we draw parallel lines using a straight edge only (we don't even have a compass) ??
07.03.2021 20:37
guptaamitu1 wrote: How can we draw parallel lines using a straight edge only (we don't even have a compass) ?? read the solution immediately above this post of yours.
07.03.2021 20:49
Lemma: Given a segment $AB$.And another segment $CD$ parallel to $AB$ and midpoint $M$ of $CD$.Then it is possible to construct midpoint of $AB$ using straightedge.
Proof. At least one of $AC\cap BD$,$AD\cap BC$ will not be a point at infinity.Wlog, $AD\cap BC=X\ne P_{\infty}$.Then $XM$ bisects $AB$.$\quad\square$ Now given $n$ points [$n$ odd] and $\frac{n+1}{2}$ segments each with end point from the $n$ points. Then we can find 2 segments which are not parallel. Indeed, among $n$ points there can be at most $\frac{n-1}{2}$ segments parallel to a particular direction. Let We want to bisect $AB$. Suppose there is a segment parallel to $AB$ whose midpoint is marked. Then using the lemma we are done.Otherwise, assume no segment with marked midpoint is parallel to $AB$.Suppose $XY$,$MN$ are 2 segment such that midpoint of $XY$ and $MN$ is marked and $XY$ and $MN$ are not parallel.
[asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(12.cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = 2., xmax = 14., ymin = -3., ymax = 4.; /* image dimensions */ pen ffqqff = rgb(1.,0.,1.); /* draw figures */ draw((4.6,2.7)--(9.02,2.72), linewidth(0.8)); draw((4.24,-0.14)--(8.86,-2.12), linewidth(0.8) + blue); draw((11.56,2.02)--(12.62,-0.44), linewidth(0.8) + ffqqff); draw((6.106445534619243,4.342777344185527)--(8.06642323558925,-0.20585015051845357), linewidth(0.8) + linetype("4 4") + ffqqff); draw((8.346582673653696,4.282836436615007)--(10.994514438621918,-1.8623636971791737), linewidth(0.8) + ffqqff); draw((4.6,2.7)--(10.031680911680908,0.37213675213675307), linewidth(0.8) + blue); /* dots and labels */ dot((4.6,2.7),linewidth(2.pt) + dotstyle); label("$A$", (4.7066,2.7994), NE * labelscalefactor); dot((9.02,2.72),linewidth(2.pt) + dotstyle); label("$B$", (9.111,2.8236), NE * labelscalefactor); dot((4.24,-0.14),linewidth(2.pt) + dotstyle); label("$X$", (4.3436,-0.032), NE * labelscalefactor); dot((8.86,-2.12),linewidth(2.pt) + dotstyle); label("$Y$", (8.9658,-2.0164), NE * labelscalefactor); dot((11.56,2.02),linewidth(2.pt) + dotstyle); label("$M$", (11.652,2.1218), NE * labelscalefactor); dot((12.62,-0.44),linewidth(2.pt) + dotstyle); label("$N$", (12.7168,-0.3466), NE * labelscalefactor); dot((10.031680911680908,0.37213675213675307),linewidth(2.pt) + dotstyle); label("$K$", (10.1274,0.4762), NE * labelscalefactor); dot((7.315840455840454,1.5360683760683767),linewidth(2.pt) + dotstyle); label("$G$", (7.417,1.6378), NE * labelscalefactor); dot((9.525840455840454,1.5460683760683767),linewidth(2.pt) + dotstyle); label("$R$", (9.6192,1.6378), NE * labelscalefactor); dot((6.81,2.71),linewidth(2.pt) + dotstyle); label("$C$", (6.9088,2.7994), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] So draw a parallel line of $XY$ through $A$,draw a parallel line of $MN$ through $B$.[This can be done since mid-point of $XY$,$MN$ is marked.] Let them intersects at $K$.By the lemma it is possible to find mid-point $G$ of $KA$,midpoint $R$ of $KB$ [Since,$KA||XY$ and mid-point of $XY$ is given,$KB||MN$,midpoint of $MN$ is given. Now again it is possible to draw a parallel line to $BK$ through $G$ since midpoint of $BK$ is $R$.This line passes through midpoint of $AB$.
07.03.2021 21:58
Vikram Betal. (Old Bengali Cartoon ).Next time Nonte and fonte pls or maybe motu patlu.
08.03.2021 16:41
anantmudgal09 wrote: My solution (terser than the official):
You cannot draw parallel lines, as stated in the problem, you can only draw lines bw two known, given points
08.03.2021 16:58
@anantmudgal09 Sir, I think my solution is a bit easier. As no 3 are collinear we can form a triangle between any 3 of the points I use a single marked line to get the midpoints for all the other lines. I take an unmarked line AB and a marked line CD (Midpoint be P). In triangle ACD with base as AD then as we know the midpoint of CD, I place the straight edge on AD and translate it until it touches P without changing its orientation. Mark its intersection point with AC as Q. Now we have the midpoint of AC. Now repeat the same with triangle ABC with BC as the base, we get the midpoint of AB. If we repeat this process many times then we can find the midpoint of all the lines
08.03.2021 17:03
@anantmudgal09 Sir, Could you please tell me how much can I fetch.
08.03.2021 17:26
@above sorry for being rude but that’s a clear 0. EDIT: because translation is not allowed
09.03.2021 04:37
@above I am sorry, but I think the solution that Mr. Anant Mudgal and @amar_04 have proposed is based on the fact that we can draw a parallel line. Then how isn't it the same case as mine. And also it is a ruler In practical situations we can translate it without changing its direction.
09.03.2021 06:57
Consider a case in which the distance between some two points is $1$ Million Trillion light years.... So how are you going to translate it?
09.03.2021 07:09
Also, how can you translate a straightedge without altering its orientation even slightly?
09.03.2021 10:23
N1RAV wrote: Consider a case in which the distance between some two points is $1$ Million Trillion light years.... So how are you going to translate it? I can't tell if you're being serious or not.
09.03.2021 15:16
biomathematics wrote: N1RAV wrote: Consider a case in which the distance between some two points is $1$ Million Trillion light years.... So how are you going to translate it? I can't tell if you're being serious or not. I meant that the proof in #18 is wrong
09.03.2021 18:23
@above Please note that it is an infinite ruler.
09.03.2021 18:24
@L567 It is an ideal case. Just like a frictionless surface and an infinite ruler.
09.03.2021 18:25
CrazyBoy2.0 wrote: @above Please note that it is an infinite ruler. unfortunately it's not correct anyway. you can't "hand-translate" a straightedge. a proof cannot be an experimental idea with human error. When we mean straightedge, we mean that given any two points on the plane we can make a line through them. that's all the power that a straightedge has.
09.03.2021 18:29
CrazyBoy2.0 wrote: @L567 It is an ideal case. Just like a frictionless surface and an infinite ruler. The question itself specifies..., that it can only be used to draw the line between any two points, thats it, you cant translate it and draw parallel lines
09.03.2021 18:52
Infinite ruler means we can draw points at infinity along with the line at infinity
09.03.2021 19:56
@biomathematics You can't take human error in an ideal condition.
09.03.2021 19:59
@L567 Nevertheless it is a ruler. I will just modify its purpose. You can translate a scale without changing its direction. Why not an infinite one?
09.03.2021 20:37
Don't treat it as a physical ruler. Just imagine that Vikram can join two points and extend it both sides infinitely. Also, besides the problem, I really want to know how you can translate an unmarked scale and keep it parallel. idk how to explain any further.
09.03.2021 20:46
CrazyBoy2.0 wrote: @L567 Nevertheless it is a ruler. I will just modify its purpose. You can translate a scale without changing its direction. Why not an infinite one? Because the problem clearly states that all you can use it for is to draw a line between two points, thats it, you cant do any more with it
10.03.2021 03:53
@biomathematics I know I shouldn't use vector algebra in INMO. But I am going to use it now. Consider the base vector as AK(bar). If you place a ruler on it then it is going to represent that vector multiplied by scalar (As I don't know the length of ruler and vector). Now we have assumed that the ruler is a vector. According to the definition of free vector, A free vector can be translated anywhere in the space without changing its magnitude and direction. So I translate it to another point in space without changing its direction.(Magnitude unknown). Now we get a parallel vector. You can verify it practically by using my solution.(It's gonna be an example of the practical application)
10.03.2021 05:04
CrazyBoy2.0 wrote: I know I shouldn't use vector algebra in INMO. But I am going to use it now You can, if I am not wrong CrazyBoy2.0 wrote: Now we have assumed that the ruler is a vector..So I translate it to another point in space without changing its direction.(Magnitude unknown). Ummm, no you can't do that
10.03.2021 10:20
@CrazyBoy2.0 Arguing here wont help anyhow... and definitely your solution is wrong according to me and if you don't get a 17 for this problem, then kindly read all these posts again and try to understand the meaning of the words used in the question
10.03.2021 14:49
@Dr.Vex He is asking practically. See the second paragraph.
10.03.2021 17:12
To modify the purpose of the straightedge (especially when its purpose is clearly stated!) is quite simply put, absurd. It is as if someone wrote the following solution to IMO 2017 P3 (Hunter and Rabbit): "We modify the tracking device such that it always reports the exact location of the rabbit. Then the hunter can always move to the rabbit's location and clearly guarantee it stays close enough to the rabbit. QED"
10.03.2021 18:13
IAmTheHazard wrote: To modify the purpose of the straightedge (especially when its purpose is clearly stated!) is quite simply put, absurd. It is as if someone wrote the following solution to IMO 2017 P3 (Hunter and Rabbit): "We modify the tracking device such that it always reports the exact location of the rabbit. Then the hunter can always move to the rabbit's location and clearly guarantee it stays close enough to the rabbit. QED" haha, that corresponds to $-7$ on the IMO @39 tbh @Dr_Vex is correct and you are wrong, and still if you think you are correct, you keep you explanation with yourself (Sorry if I sound rude), and I request all others not to reply Thanks
12.03.2021 15:21
@Abhaysingh2003 For God's sake I just have 2 accounts and this is created 'cause I forgot my password to the old one and my email is unavailable that time. Now my primary account is gone.
02.07.2022 00:43
Cool problem The answer is yes. By PHP we see that there is a pair of segments with marked midpoints share and endpoint. Let these segments be $PA$ and $PB$ with midpoints $M_B$ and $M_A$, respectively. Given any other point $C$, we claim we construct the midpoint of $PC$. Indeed, mark the point $X$ which is the intersection of $AP$ and $BC$. Notice that in any triangle with two marked midpoints, we can mark the third midpoint by marking the centroid and drawing the line between the last vertex and the centroid, call this fact $(\star)$. By $(\star)$ on $PAB$ we can mark the midpoint $M_P$ of $AB$. Extending $M_PM_A$ intersects $BX$ at it's midpoint $N$. By $( \star )$ on $BPX$, we can mark the midpoint $K$ of $PX$. Finally, the midpoint of $PC$ is the intersection of $KM_A$ and $PC$. Thus, we can construct the midpoints of a segment with endpoint $P$. Doing this quickly increases the number of midpoints, and repeatedly doing the process above yields every possible midpoint between any two of the $2021$ points.
Attachments:

29.07.2024 13:08
Claim I: Given 2 segments $AB$ and $AC$ with their midpoints, the midpoints of BC can also be constructed using a straightedge. Claim II: Given a segment $AB$, its midpoint , and any point C, a parallel line can be drawn through $C$ Claim III: Given 2 non-parallel segments $AB, BC$ with their midpoints $M, N$, midpoint of any other segment $DE$ can be constructed using a straight-edge. After proving these claims you can easily move by contradiction because if no 2 segments will share an endpoint, then we will have 2022 endpoints, which is false, so at least 2 segments can have their midpoints marked, if those two segments are AB and BC, they cannot be parallel