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