PLEASE HELP - Due 15th Sept
Tokens are put on some squares of an 8 x 8 grid to make a pattern, such as the one shown in the first diagram (without arrows.
We try to remove the tokens in a sequence of clearing steps. A clearing step consists of choosing row or a column which only contains 1 or 2 tokens and removing them. For example, we cannot initially remove all tokens from Column D. But we can clear Row 5 and then, in some later step, remove the two remaining tokens in column D.
If all the tokens in a oattern can be removed from the grid using some sequence of clearing steps, the pattern is called clearable. The pattern in the diagram is clearable because we can remove all tokens using the following sequence of 13 steps (among other possibilites) :
2, E, 8, G, 7, F, D, 5, 6, 3, 4, A, 1.
These steps are represented by the arrows numbered 1 - 13 in the second diagram.
a) Show that the pattern can be cleared in 11 steps.
b) Explain why it is impossible to clear the pattern in less than 11 steps.
c) The third diagram/pattern is not clearable - explain why.
d) What is the smallest number of tokens that can appear in a non-clearable pattern? Explain.
Thanks so much for your time - these problems are very difficult!!