Problem 2 · The largest zigzag
Greedy digit-by-digit construction avoiding three monotone digits.
Integer answer, at most 4 digitsA positive integer is called a zigzag number if it satisfies the following three conditions:
- Its digits are nonzero and all different.
- It has no three consecutive digits in ascending order.
- It has no three consecutive digits in descending order.
For example, 14385 and 2917 are zigzag numbers but 2564 and 71544 are not. What is the largest four-digit zigzag number?
Reasoned solution
Key idea: to maximise, pick the largest possible digit left to right, making sure no three consecutive digits are ever monotone.
First digit: $9$. Second: $8$? Then we would have $9 > 8$ and the third digit would need to be larger than $8$ to avoid three descending: only $9$, already used. Impossible: the second digit must be $7$.
With $9 > 7$, the third must go up: the largest available is $8$ → $978$. The fourth must go down and differ from the used digits: the largest is $6$.