Help the Doctor (Puzzle 1)

Points : 17

DockOck(Dr.Octupus from Spiderman) for a change has done something productive. He invented a rare kind of nanobot which can destroy a cancer cell. He discovered that a body cell is actually covered by a cell wall of N sides (N may vary).These N parts of the cell wall can be semi-permeable or rigid.

When a nanobot attacks a wall which is semi-permeable then the wall becomes rigid and vice-versa. A nanobot cannot determine by any means whether the part is semi-permeable or rigid. One nanobot can attack only one part of the wall at a time, but m bots can attack m wall parts at the same time. After such an attack, if all the parts of this cancer cell wall become rigid, or all become semi-permeable, this cancer cell is destroyed, otherwise the cancer cell wall may or may not change its orientation such that the cyclic order of the walls remains the same. After this the nanobots can again attempt to attack the cancer cell wall.

But DockOck being a more of a doctor and less of a mathematician is not able to arrive at the conclusion that what are the minimum number of nanobot that should be assigned to one affected cell (cell with cancer cell wall around it) such that they destroy the cancer cell wall.

Help DockOck!

Solution

Before solving the puzzle for 4 sided cell let us solve this problem for 2 sided cell i.e think of the cell as being a line with two ends. In the two sided wall problem either both of the walls are in the same state or one may be different then other. So the move requires that hit any of the wall so that they come into same state. Therefore the number of bots required is 1.Now think of a four sided cell wall. Decide on the minimum number of cellwalls that are to be hit so as to bring all the walls in the same state. If we arrange the cell walls in binary configuration say w1,w2,w3,w4 then the number of moves can be

• Hitting only one wall.(no of nanobots required = 1)
• Hitting any two consecutive walls.(no of nanobots required =2)
• Hitting any two non consecutive walls.( no of nanobots required =2)
• Hitting three consecutive or non consecutive walls. This move corresponds to the first move i.e since we can win by either 0000 or 1111 states of the wall. Therefore this corresponds to the first case.

Therefore to destroy the cell wall completely for a four sided cellwall atleast two nanobots must be assigned to a cell.
Therefore no of nanobots required for a four sided cell = 2.
The problem of generalizing the case for a N sided cell is more complicated and requires some complex geometry.
For N sided cell, the minimum no of nanobots required to completely destroy the cell is [(p-1)*N/p] where p is the largest prime divisor of N.

For the proof it is convenient to think of the n sided cell as a regular n-gon(n sided polygon) between two players one is you with n0 < n nanobots and the other is fate, who initially decides the states of the walls of a cell and who at all times knows the state of every wall.

To show that [(p-1)/p]N hands are necessary we will be needing some terminology. For any integer k with 1<=k<=n, an [n,k]-gon is obtained by choosing every k-th vertex(clockwise) of regular n-gon beginning and ending with the same vertex (which may require several trips around the n-gon). Two vertices of [n,k] are said to be successive if one is followed immediately by the other in the order in which [n,k]-gon is traversed. An [n,k]-gon has n/(k,n) vertices where (k,n) denotes the greatest common divisor of k and n.

A [10,4]-gon in the 10-gon is shown below:

Let n be any natural number and let p be the largest prime divisor of n , and let n0 be any natural number less than [(p-1)/p]n. Then we will prove that the game cannot be won by a player with n0 nanobots.

Suppose first that n is prime. Fate will begin by setting the states of walls in such a way so that not all are in the same state. Since the player has n-2 (or fewer) nanobots his intended attack of nanobots will include two unchecked walls of the cell. Fate notes these for the current move and that one is located say k sides clockwise from the other where(l<=k<n). Since n and k are relatively prime the(n,k)-gon includes all the n walls of the polygon. Since not all the walls are in the same state, two successive walls of the (n,k) polygon will differ.Fate rotates the cell to place these walls in the unchecked positions in the player's turn, thus preventing a win on this, or indeed any move.

If now n = p.l where p is a prime and the player has less than (p-1).l nanobots, fate initially set the states of the walls such that so that they are not in the same state.Since n = p.l , there are l distinct (n,l)-gons each with p vertices, thus any move of the player with leave atleast two unchecked walls in some (n,l)-gon Q. But the (n,l)-gons are all regular p-gons so fate can rotate the cell such as to make P and Q coincide in such a manner that, as before ,the two unchecked walls are in the different states.

For more references check->
http://www.jstor.org/stable/pdfplus/2690109.pdf

Points Distribution

• 6 points for determining the minimum number of nanobots for N=4 and providing its explanation.
• 11 points for determining the formula for N nanobots and providing its explanation.

For any query post your question below.