Remove the minimum number of blades

Question

Recently, I came across this problem on Timus online judge. For people reluctant to click on the link. The question is as follows:

Experienced participants of the Ural Championship come to Yekaterinburg in advance to get accustomed to the severe weather conditions, walk around the city, and, of course, visit the “Limpopo” Water Park. Not many people know that there is Plant No. 404 near the water park, and this plant is called “Error 404” by the locals. The plant is not easy to find indeed, and it is still more difficult to learn what is happening there. Fortunately, one can watch the plant from a nearby pedestrian bridge. Because of the seeming stillness and desolation of the plant, one may think that it is out of operation, but this is not so. The main work area of the plant is the repair of aviation engines. Some time ago the plant received an order to repair a broken gas turbine engine. It turned out that some blades were torn off, which resulted in an excess load on the engine shaft. Experts at the plant have decided that the engine could be repaired quickly by removing some of the intact blades so that the center of masses of the remaining blades would be on the rotation axis once again. To keep the engine power as large as possible, a minimum number of blades should be removed. At least one blade must be left, otherwise the engine would not work at all. The experts assert that when all the blades were intact their endpoints formed a regular n-gon. Tell them which blades should be removed.

> Input The first line contains the initial number of blades in the
> turbine n and the number of torn blades k (3 ≤ n ≤ 20000; 1 ≤ k ≤ n −
> 1). The integer n has at most two distinct prime divisors. The next
> line contains k integers, which are the numbers of the torn blades in
> ascending order. The blades are numbered from 1 to n clockwise. 
Output
> In the first line output the minimum number of blades that should be
> removed. In the second line output the numbers of these blades in any
> order separated with a space. If several answers are possible, output
> any of them. If it is impossible to repair the engine by removing some
> of the blades, output “−1”. 
> 

I am having trouble setting up this problem. My initial thought is that since the center of mass needs to be recovered, a broken blade needs to be surrounded of equal number of non-broken blades.

So if we represent a broken blade as 0 and an unbroken blade as 1, a particular configuration can be represented as: 011

I am not sure if I am on the right track and some feedback will be awesome in trying to understand this problem.

Thanks

Answer 1

The tips of the blades originally formed a regular n-gon. Visualize them as complex numbers. Without loss of generality, the radius is 1, the axis is on the origin and the tip of the blade with number n is on 1.

The tips of the blades are the n-th roots of unity, the tip of blade k is at

z_k = e^(2\pi i * k/n)

The center of mass after removing blades k1, ... , kr is on the rotation axis if and only if

z_k1 + z_k2 + ... + z_kr = 0

Now let 1 < d < n be a divisor of n. The blades k1 + m*d, 0 <= m < n/d form the vertices of a regular n/d-gon. Thus removing them all leaves the center of mass on the rotation axis.

The strategy is to try to cover the list of indices of the broken blades by a set of disjoint regular d_i-gons, where d_i is a divisor of n. So, in the list, find pairs whose indices differ by a divisor of n.

Answer 2

My initial thought is that since the center of mass needs to be recovered, a broken blade needs to be surrounded of equal number of non-broken blades.

No. The propeller must be rotationally symmetric. If one blade is broken off of a 3-blade propeller, there's no way of recentering it.

The key points are:

1. The experts assert that when all the blades were intact their endpoints formed a regular n-gon.

2. The integer n has at most two distinct prime divisors.

Start with something simple that fits these two properties, such as a decagon. Ask yourself: how do polygons and symmetry relate? How do divisors of 10 then relate to polygons and symmetry? To simplify things, can you represent these polygons using scalars rather than two-dimensional points? Hint: modular arithmetic plays into the solution.

Pictures of blade configurations (both unfixed and fixed) should help. For example:

        2                     2                     2                   2           
    3       1                     1                                                 
  4           0         4           0         4           0       4           0     

  5           9         5                                 9       5           9     
    6       8             6       8             6       8                   8       
        7                     7                     7                   7           
   whole 10-gon        2 broken blades       3 broken blades     3 broken blades

There are two potential solutions to the 2 broken blades and first 3 broken blades, though only one is optimal for each. The second 3-broken has one solution. Look for the polygons.