The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

Practice Paper 3 Question 8

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?

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Hints

  • Hint 1
    Can the number of \(A\)s on the whiteboard increase?
  • Hint 2
    What restrictions exist on how we may reduce the number of \(A\)s?
  • Hint 3
    ... and what does that tell you about \(p?\)
  • Hint 4
    The question essentially asks to remove all \(B\)s. Couild there be a situation when you cannot remove a B? Justify.

Solution

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.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footas[email protected]. Please do not write to this address regarding general admissions or course queries.