3. You are given a grid of cells. Each cell has a positive integer written on it. You can
move from a cell x to a cell y if x and y are in the same row or same column, and the
number in y is strictly smaller than the number in x. You want to colour some cells
red so that:
• Every cell can be reached by starting at a red cell and following a sequence of
zero or more moves as de?ned above.
• The number of red cells is as small as possible.
You should report the following information:
2• The number of red cells.
• The smallest number appearing amongst all red cells.
If there are multiple valid solutions, give any one solution.
For example, suppose the grid is as follows:
2 2 3
2 1 2
3 2 2
It is su?cient to colour the two cells labelled 3, and one cannot do better than this.
In this case, the number of red cells is 2 and the smallest number appearing amongst
all red cells is 3.
(a) 55 25 49 40 55 3 55
33 32 26 59 41 40 55
31 23 41 58 59 14 33
9 19 9 40 4 40 40
55 54 55 46 52 39 41
10 41 7 47 5 30 54
40 22 31 36 7 40 28
21 40 41 59 14 36 31
(b) 50 98 54 6 34 94 63 52 39
62 46 75 28 65 18 37 18 97
13 80 33 69 93 78 19 40 13
94 10 88 43 61 72 94 94 94
41 79 82 27 71 62 57 67 34
8 93 2 12 93 52 91 86 93
94 79 64 43 32 94 42 91 9
25 73 29 31 19 70 58 12 11
(c) 50 54 6 34 78 63 52 39 41 46
75 28 65 18 37 18 13 80 33 69
78 19 40 13 10 43 61 72 13 46
56 41 79 82 27 71 62 57 67 81
8 71 2 12 52 81 1 79 64 81
32 41 9 25 73 29 31 19 41 58
12 11 41 66 63 14 39 71 38 16
71 43 70 27 78 71 76 37 57 12
77 50 41 81 31 38 24 25 24 81
3. You are given a grid of cells. Each cell has a positive integer written on it. You can
move from a cell x to a cell y if x and y are in the same row or same column, and the
number in y is strictly smaller than the number in x. You want to colour some cells
red so that:
• Every cell can be reached by starting at a red cell and following a sequence of
zero or more moves as de?ned above.
• The number of red cells is as small as possible.
You should report the following information:
2• The number of red cells.
• The smallest number appearing amongst all red cells.
If there are multiple valid solutions, give any one solution.
For example, suppose the grid is as follows:
2 2 3
2 1 2
3 2 2
It is su?cient to colour the two cells labelled 3, and one cannot do better than this.
In this case, the number of red cells is 2 and the smallest number appearing amongst
all red cells is 3.
(a) 55 25 49 40 55 3 55
33 32 26 59 41 40 55
31 23 41 58 59 14 33
9 19 9 40 4 40 40
55 54 55 46 52 39 41
10 41 7 47 5 30 54
40 22 31 36 7 40 28
21 40 41 59 14 36 31
(b) 50 98 54 6 34 94 63 52 39
62 46 75 28 65 18 37 18 97
13 80 33 69 93 78 19 40 13
94 10 88 43 61 72 94 94 94
41 79 82 27 71 62 57 67 34
8 93 2 12 93 52 91 86 93
94 79 64 43 32 94 42 91 9
25 73 29 31 19 70 58 12 11
(c) 50 54 6 34 78 63 52 39 41 46
75 28 65 18 37 18 13 80 33 69
78 19 40 13 10 43 61 72 13 46
56 41 79 82 27 71 62 57 67 81
8 71 2 12 52 81 1 79 64 81
32 41 9 25 73 29 31 19 41 58
12 11 41 66 63 14 39 71 38 16
71 43 70 27 78 71 76 37 57 12
77 50 41 81 31 38 24 25 24 81
