10771 - Barbarian Tribes
There are two tribes: Gareds and Kekas. Gared maids and Keka maids are placed in a circle.
Two persons from the circle are selected (by a complicated process), and replaced by another person. If both persons were from the same tribe, the new person will be a Gared. If they were from different tribes, it will be a Keka. This process is repeat until only one person remains.
Given values of and , determine which tribe's person will remain at the end.
It is possible to answer this problem without even knowing exact details of selection process. Notice this invariant: after each elimination step, the parity of the number of Kekas maids does not change.
So, if there was an odd number of Kekas at the beginning, there'll be an odd number of them at the end, i.e. just one Keka. And if the initial number was even, no Kekas will remain.
3 3 2 4 2 2 0 1 7 0 0 0
Keka Gared Keka