Solution Gossip travels fast

 

Question (a)

It is not difficult to fill the diagram with numbers indicating on which day the people living there will be convinced. It takes 10 days to reach apartment 6 on floor 8 and they will start spreading the rumour on day 11.

floor 12
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5

 

 

 

 

??

 

 

 

 

4

5

 

 

 

 

 

 

 

 

3

4

5

 

 

 

 

 

 

 

2

3

4

5

 

 

 

 

 

 

floor 3
 
1

2

3

4

5

 

 

 

 

 

floor 2
 
X

X

X

3

4

5

 

 

 

 

X

X

X

2

3

4

5

 

 

 

floor 1
 
X

X

X

1

2

3

4

5

 

 

Ap. 10
 

Ap. 1
 

 

 

Question (b)

We now may work backwards, starting from the apartment in position (6,8) and figuring out which other apartments are required to supply the rumour to that position. For instance, the three apartments in positions (6,7), (7,6) and (8,5) indicated by the number 1 will do. To supply the rumour to these three apartments, at least five apartments on the diagonal below are required, for instance those indicated by the number 2 in positions (6,6), (7,5), (8,4), (9,3) and (10,2). But to supply the rumour to these five apartments, again just five apartments on the diagonal just below will do! For instance: those indicated by the number 3. This pattern can now be repeated. It is not difficult to complete the diagram and to count the number of apartments required to spread the rumour convincingly to position (6,8). The total number of apartments is then equal to 6+39+1=46.

Explanation: from the initial 9 apartments indicated with X only 6 are required, 39 apartments are required to pass on the news to position (6,8), and of course the people living there should be available too. 

floor 12
 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

??

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

3

2

1

 

 

 

 

 

 

 

 

3

2

1

 

 

floor 3
 

 

 

 

 

 

3

2

 

 

floor 2
 
X

X

X

 

 

 

 

3

2

 

X

X

X

 

 

 

 

 

3

2

floor 1
 
X

X

X

 

 

 

 

 

 

 

Ap. 10
 

Ap. 1
 

 

 

 

Question (c)

Minimality of the solution given under (b) follows from the observation that in the first step at least three consecutive locations (indicated by the number 1) on a diagonal are required, and that in the next step (starting from these three consecutive locations) it follows that at least five consecutive locations (indicated by the number 2) on the next subdiagonal are required. From then onwards again at least five consecutive locations on a next subdiagonal are always required: this minimal pattern no longer grows but it has stabilized.

 

For the first step there are two ways to choose the three consecutive locations on the diagonal.

For the second step there are four ways to choose the five consecutive locations on the next subdiagonal.

For each of the following steps there are two ways to choose the five consecutive locations on the next subdiagonals. This continues until a position is reached ‘at the border’, i.e. on the first floor or with a first apartment. From then onwards there is only one choice available.

 

We need to work out each of the eight situations that are possible after the first two steps. As an example consider the situation indicated in the diagram given under (b). This pattern of five positions needs to shift down precisely once, and to shift to the left precisely five times. There are 6 different ways to do this. In a similar way we may treat the other possibilities and we find that there are “six over one” plus “six over two” plus “six over three” plus “six over four” possibilities, i.e. 6+15+20+15=56 possibilities, for the given pattern of locations indicated by the number 1. For the other possible pattern of locations with a number 1 there are 0+1+6+15=22 possibilities.

 

In total this means that there are 78 different possibilities.