Home Page | Web Board | Problems | Standing | Status | Statistics | Award Contest |

**Contest - POJ Founder Monthly Contest – 2008.03.16**

Start time: 2008-03-16 12:00:00 End time: 2008-03-16 17:00:00

Current System Time: 2024-11-06 19:07:40.234 Contest Status:
Ended

Problem ID |
Title |

3527 Problem A |
Generalized Connect Four |

3528 Problem B |
Ultimate Weapon |

3529 Problem C |
Matrix Analysis |

3530 Problem D |
A Modular Arithmetic Challenge |

3531 Problem E |
Alternating Sum of Digits |

3532 Problem F |
Resistance |

3533 Problem G |
Light Switching Game |

3534 Problem H |
Escape of Life and Death |

[Standings] [Status] [Statistics]

Contest Report | ||||||||||||||||||||||||||||||||||||||

## Table of Contents- Generalized Connect Four
- Ultimate Weapon
- Matrix Analysis
- A Modular Arithmetic Challenge
- Alternating Sum of Digits
- Resistance
- Light Switching Game
- Escape of Life and Death
- References
## Problem A: |

0 |

1 |

2 |

101 11 2 |

202 12 2 |

1001011 021101 111121 201211 22 |

2002 012022 102112 122202 21222 |

10001 0011 002 |

10101 011 |

In the list above, underlined digits are preceded by plus signs in the summation while the others are preceded by minus signs; digits in red are the common prefixes shared by numbers in the same group. Next, we will focus on summation within a single group.

Summation within one group can be found by computing the sum over the common prefixes and that over the suffixes separately. Computing the former is intuitively easier since it has a regular pattern. To facilitate the computation of the latter, we break the suffixes of the numbers into individual digits and handle the digits by radix place. When listed in order, digits in each radix place of the suffixes of the numbers make up a sequence of the form (0^{x}1^{x}2^{x})^{y} where *x* and *y* are powers of 3 (*a*^{k} represents *k* consecutive occurrences of *a*; the parentheses indicate grouping). The pattern may be incomplete in the last group, but that should not be too difficult to address. Whether the digits in the sequence are preceded by alternating signs is decided by the radix length of the numbers. The sign before the leading 0 is decided by the total count of digits in previous groups and the radix place.

To compute the equivalent resistance measured between two designated junctions in a circuit of resistors, we can either connect the two junctions to the ends of a constant voltage source and compute the current across the circuit, or connect them to the ends of a constant current source and compute the potential difference between them. In either way, we establish a system of linear equations in voltages at the junctions and currents over the resistors according to Kirchhoff’s current law and Ohm’s law, which are quoted as follows.

Kirchhoff’s current law.At any point in a circuit where charge density is not changing in time, the sum of currents flowing towards that point is equal to the sum of currents flowing away from that point.

Ohm’s law.The current passing through a conductor between two points is directly proportional to the potential difference across the two points, and inversely proportional to the resistance between them.

Then we can use Gaussian elimination to solve the linear system.

In the case of using a constant current source, the problem can be alternatively formulated as a convex cost flow problem. The circuit is regarded as an undirected flow network where the cost of an arc is defined as the heat generated by the current flowing through the corresponding resistor. We establish a flow of current on this network that generates the least heat and compute the equivalent resistance using the generated heat according to Joule’s first law. The successive shortest path algorithm for minimum (linear) cost flow still works, but special care has to be taken when computing the costs of augmenting paths since the cost of any arc is a quadratic function in the flow over it.

Before examining the game in a cube of arbitrary dimensions, we shall first analyze a simplified version where the cube is restricted to be of dimensions *n* × 1 × 1. We claim that a game with lights on in cells (*x*_{1}, 1, 1), (*x*_{2}, 1, 1), …, (*x _{k}*, 1, 1) is equivalent to a game of Nim with

- Turning off the light at (
*x*, 1, 1) alone is equivalent to removing the whole pile of_{i}*x*chips;_{i} - Turning off the light at (
*x*, 1, 1) and toggling the light at (_{i}*x*_{j}, 1, 1) is equivalent to removing*x*−_{i}*x*chips from a pile containing_{j}*x*chips._{i}

Consequently, the nimber of the aforementioned game is *x*_{1} ⊕ *x*_{2} ⊕ ⋯ ⊕ *x _{k}*, where ⊕ denotes nimber addition, which is effectively bitwise exclusive-or.

Now we are ready to scrutinize the original game. Assume that the game has lights on in cells (*x*_{1}, *y*_{1}, *z*_{1}), (*x*_{2}, *y*_{2}, *z*_{2}), …, (*x _{k}*,

To evaluate *x* ⊗ *y*, we can take advantage of the following two lemmas concerning Fermat 2-powers (numbers of the form 2^{2n}) in addition to the properties of the field :

- The nimber product of a Fermat 2-powers and any smaller number is their product in the sense of ordinary natural number arithmetic.
- The nimber square of a Fermat 2-power
*x*is 3*x*⁄2 in the sense of ordinary natural number arithmetic.

The following example demonstrates how techniques are combined to evaluate 32 ⊗ 16:

32 ⊗ 16 | = (16 ⊗ 2) ⊗ 16 | (2^{5} = 2^{22} ⋅ 2^{20}) | |

= (16 ⊗ 16) ⊗ 2 | (commutativity and associativity of multiplication) | ||

= 24 ⊗ 2 | (Fermat 2-powers lemma 2) | ||

= (16 ⊕ 8) ⊗ 2 | (24 = 2^{4} ⊕ 2^{3}) | ||

= 16 ⊗ 2 ⊕ 8 ⊗ 2 | (distributivity of multiplication over addition) | ||

= 32 ⊕ (4 ⊗ 2) ⊗ 2 | (Fermat 2-powers lemma 1; 2^{3} = 2^{21} ⋅ 2^{20}) | ||

= 32 ⊕ 4 ⊗ (2 ⊗ 2) | (associativity of multiplication) | ||

= 32 ⊕ 4 ⊗ 3 | (Fermat 2-powers lemma 2) | ||

= 32 ⊕ 12 | (Fermat 2-powers lemma 1) | ||

= 44 |

The underlying model of this problem is the shortest path problem on direct acyclic graphs. After topologically sorting the vertices, one can compute the shortest path in linear time.

Wikipedia contributors, Alpha-beta pruning, Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Alpha-beta_pruning&oldid=191655157 (accessed March 15, 2008) |

Michael S. Horn, 3D Convex Hull Construction, Randomized Incremental Algorithm, http://www.eecs.tufts.edu/~mhorn01/comp163/algorithm.html |

Wikipedia contributors, Kirchhoff's circuit laws, Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Kirchhoff%27s_circuit_laws&oldid=198132996 (accessed March 15, 2008) |

Wikipedia contributors, Ohm's law, Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Ohm%27s_law&oldid=198358159 (accessed March 15, 2008) |

Wikipedia contributors, Nimber, Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Nimber&oldid=192952237 (accessed March 15, 2008) |

Thomas S. Ferguson, Part I. Impartial Combinatorial Games, Game Theory, http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf |

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator