A whiteboard has $p$ $``A"$ symbols and $m$ $``B"$ symbols written on it. You choose any two symbols to erase and replace them with another one according to the following rules:
$A A \Rightarrow B$$A B\text{ or } BA \Rightarrow A$$B B \Rightarrow B$
If you continue to apply replacements for as long as possible, which values of $p$ and $m$ result in a single $A$ remaining at the end?
-
Can the number of
$A$s on the whiteboard increase? -
What restrictions exist on how we may reduce the number of
$A$s? -
… and what does that tell you about
$p?$ -
The question essentially asks to remove all
$B$s. Couild there be a situation when you cannot remove a B? Justify.
-
The number of
$A$s can never be increased, so$p\geq1.$Also, as the number of$A$s may decrease only by$2$at a time via the first rule,$p$must be odd (since we need one$A$at the end). In contrast, there is no constraint on the initial number of$B$s. Since the number of$A$s is always greater than$0,$we will always be able to apply a replacement if there is at least one$B.$Every replacement that involves a$B$reduces the number of$B$s by one. Consequently, the number of$B$s will be reduced to$0$no matter how many we started with.