CHDOGS - Editorial

editorial
, , , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

simple

PREREQUISITES

symmetry, rate of approach, trigonometry

PROBLEM

There are three points on equilateral triangle of side s. Each point is moving constant velocity v towards the point on the right of it. You need to find the time at which these three points will meet.

QUICK EXPLANATION

The answer is \frac{2}{3} \frac{s}{v}.

EXPLANATION

This question can be solved in a lot of the ways. Actually, this problem was easily search-able on web. The intent of giving this problem was to familiarize the readers with various different ways of solving the problem.

Where will the points meet?

By symmetry, we can say that the points will meet at the centroid of the triangle. In fact, the triangle formed by the three points at any install during their journey will also stay equilateral.

Velocity of approach based solutions.

Let us consider the points A, B, C, at some instant. The point A is moving towards B. B is moving towards C, and C towards A. Let us find our rate of approach of points A and B towards each other. A is moving towards B, so its velocity vector v will contribute completely in the rate of approach. Velocity vector of B is directed towards C, so its component v cos(60) towards A will only contribute in the rate of approach. So rate of approach of A and B towards each other will be v + v cos(60) = \frac{3 v}{2}.

By symmetry, we can say that rate of approach will be same for A, B, A, C and B, C all three pairs.

Initially the distance between A, B is s. So, total time taken in meeting will be

\frac{s}{\frac{3 v}{2}} = \frac{2 s}{3 v}

You can also see this beautiful written answer on stackexchange too.

By solving the expression for separation vs time

You can solve this question by rigorously working out expressions of separation vs time. This solution can be found here.

Simulation based solution

You can say that the time will be proportional to side of equilateral triangle s, inversely proportional to speed.

t \propto \frac{s}{v}

The proportional relation should not depend on values of s and v, so it will be a constant.

t = c \cdot \frac{s}{v}

Finding the constant c can be done experimentally by a simulating the motion of points by taking dt (change in time) as low as possible. You will see that the constant will approach towards \frac{2}{3}.

Interesting readings.

This Stackexchange answer very beautifully explain finding the location of meeting of points without using the symmetry argument directly.

In the same context, this answer is also worth reading.

This Quora answer gives an idea of solving the problem for any general regular polygon.

Time complexity of all these solutions at the end are constant time (\mathcal{O}(1).

EDITORIALIST’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes
2

Why the acuraccy had changed after contest

3

how to do this using centroid of triangle ?

4 
#include <bits/stdc++.h>
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
using namespace std;//coded by abhijay mitra
#define watch(x) cout << (#x) << " is " << (x) << endl
int main()
{
    ibs;cti;
    int t;cin>>t;cout<<"\n";
    while(t--){
        long double s,v;cin>>s>>v;
        cout<<std::fixed<<std::setprecision(9)<<2*s/3/v<<std::showpoint<<"\n";
    }
    return 0;
}

This is a famous problem first posed by IE IRODOV
SOLUTIONS TO I E IRODOV BY RKH: problem 1.12 for solution

1 Like
5

I made a guess about the answer from the test cases and got lucky. I knew that it had something to do with breaking one velocity into it’s components (at \cos{60\degree}) but couldn’t arrive at the final expression.