TTMUA Lab
TMUA 2018 · Paper 2 · Question 8 of 20

TMUA 2018 Paper 2 Question 8

Proof and counterexample — Reasoning about codes for mountain profiles. Try it first; the answer and a full worked solution are below.

TMUA 2018 · Paper 2Proof and counterexampleReasoning about codes for mountain profiles7 options

The original question includes a diagram: A zig-zag path of six upstrokes and six downstrokes rising from and returning to a dashed horizontal 'sea level' line, never dipping below it; a key shows an upstroke as a line rising left to right and a downstroke as one falling left to right.

The diagram shows an example of a mountain profile: a zig-zag path made of strokes above a dashed horizontal line.

This consists of upstrokes which go upwards from left to right, and downstrokes which go downwards from left to right. The example shown has six upstrokes and six downstrokes. The horizontal line at the bottom is known as sea level.

A mountain profile of order n consists of n upstrokes and n downstrokes, with the condition that the profile begins and ends at sea level and never goes below sea level (although it might reach sea level at any point). So the example shown is a mountain profile of order 6.

Mountain profiles can be coded by using U to indicate an upstroke and D to indicate a downstroke. The example shown has the code UDUUUDUDDUDD. A sequence of U's and D's obtained from a mountain profile in this way is known as a valid code.

Which of the following statements is/are true?

I    If a valid code is written in reverse order, the result is always a valid code.
II   If each U in a valid code is replaced by D and each D by U, the result is always a valid code.
III  If U is added at the beginning of a valid code and D is added at the end of the code, the result is always a valid code.

  1. Anone of them
  2. BI only
  3. CII only
  4. DIII only
  5. EI and II only
  6. FI and III only
  7. GII and III only
Show the answer and worked solution
answer · D
  1. Anone of them
  2. BI only
  3. CII only
  4. DIII only
  5. EI and II only
  6. FI and III only
  7. GII and III only
The single code UUDD settles the first two. Reversed it reads DDUU, which starts by going below sea level, so I fails; swapping every letter turns it into the same DDUU, so II fails as well. (Reversing and swapping would work — that is the mirror image — but neither operation alone does.) For III, the opening U lifts the whole path one unit; the inner code never falls below its own starting level, so the new path never falls below sea level, and the closing D brings it back down to sea level with n+1 of each stroke. Only III.