There are several letters e, a and b on a blackboard. We may replace two e's by one e, two a's by one b, two b's by one a, an a and a b by one e, an a and an e by one a,ab, and an e by one b. Prove that the last letter does not depend on the order of erasure.

Question

blockcolder · Answer

So to summarize:
ee becomes e, aa becomes b, bb becomes a.
ab becomes e, ae becomes a, be becomes b.
Of course, the letters don't have to be adjacent.

anonymous · Answer

Thank's for the simplification, but could someone please tell me how I am supposed to prove the last statement?

blockcolder · Answer

It took me a long time, but here's a solution.
Let $w_i$ be the number of a's, $x_i$ the number of b's, and $y_i$ the number of e's at step i. Step 0 is the initial configuration.
I assert that if the quantity $w_0+2x_0\equiv k \pmod{3}$, then $w_i+2x_i\equiv k \pmod{3}$ for all $i\leq w_0+x_0+y_0-1$, where k can be 0, 1, or 2. If k=0, then the final letter is e; if k=1, it's a; if k=2, it's b.

blockcolder · Answer

You can prove this assertion by mathematical induction and considering all the 6 scenarios that can happen.

anonymous · Answer

Thanks a lot!