DIVIDEN - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester 1: Minako Kojima
Tester 2: Shiplu Hawlader
Editorialist: Pawel Kacprzak

DIFFICULTY:

MEDIUM

PREREQUISITES:

Geometry, Binary search, Angles

PROBLEM:

You are given an integer 0 < N < 360 denoting an angle. Your task is to decide if it is possible to divide this angle using only a straightedge and compass into N equal angles of size 1 degree. If it is possible, then you have to provide this contruction.

BONUS

If you want to watch a very nice video about constructing using only a straightedge and compass, please look here.

QUICK EXPLANATION:

First we want to decide if it is possible to do this construction. Using a well-known fact, we argue that it is only impossible to do this if N 3 == 0. In order to prove that, we will show how to construct an angle of size 1 degree if N 3 != 0. Moreover, knowing when it is possible can lead us to an easier construction based on dividing the original angle until we construct an angle of size 1 with sufficient precision.

EXPLANATION:

Based on a well known result that trisecting an arbitrary angle is impossible we argue that the only case when the construction is impossible is when N % 3 == 0.

If N % 3 == 0, then construction is impossible because it implies that we can trisect the angle of size 3 - contradiction.

So we assume that N % 3 != 0. We will show that in that case we can construct an angle of size 1 which implies that we can divide the angle of size N into N equal angles of size 1.

First construct an angle of size 36.

Next, construct an angle of size 60 and bisect it in order to get an angle of size 30.

Using these two angles construct an angle of size 6 using subtraction 36 - 30 = 6.

Next, use bisection to divide an angle of size 6 into in order to get an angle of size 3.

Finally, since N 3 != 0, we can construct an angle of size 1 using an angle of size N and an angle of size 3 - because you can construct an angle of size N - 1 if N 3 == 2 or you can construct an angle of size N + 1 if N % 3 == 1. In any case, you can use subtraction to construct an angle of size 1.

It is clear that if you have an angle of size 1, you can “fill” the orginal angle of size N with N angles of size 1.

Ok, we proved that it is possible to construct an angle of size 1 if N % 3 != 0. We can implement this construction proof in order to output the exact steps, but it is quite complicated. The second method which was widely used by contestants is to bisect an angle of size N until you construct an angle of size 1 with sufficient precision, which is a lot easier to implement.

AUTHOR’S AND TESTER’S SOLUTIONS:

To be uploaded soon.

RELATED PROBLEMS:

To be uploaded soon.

2

My solution is a bit different from this, it’s based on the following fact:

If you have an angle of size N and N is coprime to 360, 720 operations is sufficient to divide the whole plane into 360 angles of size 1.

That’s because you can construct angles of size 2N, 3N, …, 360N (modulo 360). If N is coprime to 360, {N, 2N, 3N, …, 360N} is a complete residue system modulo 360.

Then you can easily find out all the points you need.

If the initial N isn’t coprime to 360,

  1. If N 2 = 0, you can bisect it again and again until N 2 != 0;

  2. If N % 5 = 0, you can construct an angle of size 36 and use addition.

1 Like
3

Finally, since N % 3 == 0, we can construct an angle of size 1

should be N % 3 != 0, right?

4

What was meant by

The second method which was widely used by contestants is to bisect an angle of size N until you construct an angle of size 1 with sufficient precision, which is a lot easier to implement.

If I understood it properly, it’s binary search to find angle 1°, but we can use the same for N%3 == 0 as I described here.

5

I couldnt attempt this problem due to end sems :. However in whatever time I could give it, I found this - http://archive.maths.nuim.ie/staff/sbuckley/Papers/divide_angle.pdf
which says that “For positive integer n there exists a construction by straightedge and
compasses to divide an arbitrary angle into n equal parts if and only if n is a power
of 2”. As per the editorial n%3 != 0 so n could be 7 but the proof doesnt allow n=7. It would be great for someone to clear this to me.

6

But one additional thing you have in your hands is this first angle. So at the beginning you have the angle on 7° and you just need to divide it. As shown above, you can do 7 - 3 - 3 = 1 :wink:

1 Like
7

Ok I mixed up the two Ns. One is n parts and other n is the angle.

8

Took a lot of submissions but finally got it. Pretty much same as what is done in the editorial. Take one edge, create a 60 degree angle from it (equilateral triangle), then create a pentagon such that the same side bisects one of the angles of the pentagon. You get a 12 degree angle. Bisect it twice, get a 3 degree angle. Replicate it all over the plane. If the angle given initially is a multiple of 3, no answer. If it is not, you will get an angle of 1 from the earlier replication. Replicate it again all over the plane and display the answer.

Never been happier than this to get an AC. :slight_smile: Great question.

9

You can try, but actually it is not possible to construct the EXACT 1 degree angle if N 3 == 0 based on the fact that it is given in the editorial. The bottom line is that, the answer for this case is NO, but in practice you can construct an angle as close to 1 degree as you want in any case (but not exactly 1 degree if N 3 == 0).

10

I know, that it’s not possible to create exactly 1 degree angle…

…and just now I realized there is:

The first line of the output should contain a single word: YES or NO - whether it is theoretically possible to perform the construction described above with a straightedge and compass only.

That answers my question :wink:

11

Is there an easy way to perform “angle copy” operation? Or maybe in general two circles intersection calculation?

I was kind of lazy to calculate circle and line intersection so I did bisection that way:

  1. let say we have AVB angle and |AV| = |VB|
  2. vector b for bisecting AVB is VA + VB
  3. when we multiply the vector b in such way (getting b’ as a new vector), that |b’| = |AV| then intersection point is V + b’

Something similarly easy?

This was first time I used OOP in competition, having Vector, Point, Circle and Line classes :smiley:

12

There does exist a simple way to perform “angle copying”.

Given an N degree angle AOB.

1.Construct a circle with center at point O, and radius equal to |OA|.

2.Construct a circle with center at point B, and radius equal to |BA|.

Then the intersection point of the two circles C is what we need, and it’s trivial that |OA| = |OC|, angle AOC is 2N degrees.

Just rotate point A 2N degrees around point O, you can also get point C. So the calculation is much easier.

1 Like
13

Thanks I got it, this rotation seems like easy thing in Java - http://stackoverflow.com/a/9985640/384674

14

Right, it’s now fixed.