Lazy Chickens in Grids and Cubes Paolo Baldan University of Padova Italy Roberto Bruni Unviersity of Pisa Italy Editor: Paolo Baldan Download: PDF Dr. Egghead, after a long and brilliant scientific career, retired to his birth town, where he now runs a small farm. There he raises a strange breed of chickens, called lazy chickens, that originated from some secret experimentation conducted in his past life, when he was working on genetic manipulation. Lazy chickens would produce very tasty eggs, but unfortunately they are characterised by a tremendous laziness that forces them to sleep all daytime! After some experiments, Dr. Egghead discovers how to get some eggs from lazy chickens.  In fact, he realises that the presence of regular active chickens, can trigger some spirit of emulation in lazy chickens which thus start being active and producting eggs! He prepares a 8×8 grid of small cages, with a single chicken per cage and finds out that whenever a lazy chicken has two adjacent (in the sense of sharing cage sides) active chickens, then it also becomes active and it starts influencing lazy neighbours as well. Q1: What is the least number of regular active chickens that Dr. Egghead must insert in the cages of the 8×8 grid to make all chickens in the grid active? More generally,  what is the solution for a generic n×n grid? As the production increases and business improves, Dr. Egghead decides to assemble the cages to form a 8×8×8 cube. This time, he finds out that three active neighbours are necessary to win laziness (two do not suffice anymore). Q2: What is the least number of regular active chickens that Dr. Egghead must insert in the cages of the 8×8×8 cube to make all chickens in the cube active? More generally, what is the solution for a generic n×n×n cube? Solutions Q1: It is very easy to find a solution that involves 8 regular active chickens, e.g. placed along the main diagonal. The tricky part is to prove that 7 are not enough. The proof of minimality can be constructed by exploiting a suitable invariant on the sides of the cages. Call a side of the cage of an active chicken mixed if it is not shared with another active chicken (i.e., it is shared with a lazy chicken or it is on the perimeter of the grid). We would like to reach a state of the grid where all chickens are active and thus there are exactly 8 * 4 = 32 mixed sides (i.e., all and only those on the perimeter). Now, it is immediate to check that each transformation of a lazy chicken into an active one cannot increase the number of mixed sides. But then, if we start with just 7 chickens, even if we place them in pairwise non-adjacent cages, the maximum number of mixed sides that we can have is 7 * 4 = 28. The solution easily generalizes to a n×n grid by noticing that placing regular active chickens along the diagonal gives a solution with n chickens and that if we start with just n-1 chickens then we can expect (n-1)*4 mixed sides at most, as opposed to the 4*n arising along the perimeter when all chickens are active. Q2: In this case the difficulties are reversed. By analogy with the grid case and exploiting a similar invariant, we can prove that at least 82 = 64 regular active chickens are needed (because at the end we expect 82 * 6 mixed sides, those on the faces of the cube, and each active chicken can provide 6 mixed sides at most, when placed in a cage adjacent to lazy chickens only). However finding how to place them in the cube is more challenging. This time we find convenient to define the solving scheme directly for the n×n×n case (where n2 cages are needed). Let us call ci,j,k the cage at level i from top, position j from left, and depth k from the front face of the cube (each index ranging from 0 to n-1).  Then, we claim that a solution with exactly n2 regular active chickens is obtained by placing them in the cages ci,j,k such that (j+k) mod n = i. This corresponds to fill the diagonal of the bottom level and then to shift the placing by one position to the left (circularly) as we move one level up. The solution for n=5 is depicted below, where the red cages (dark grey, if printed in black&white) represent active chickens. We prove that this is actually a solution with an inductive reasoning. The base case n=1 is trivial. For the inductive case,assuming that the solution works for the n×n×n cube we prove that it works for the (n+1)×(n+1)×(n+1) cube. In order to avoid a cumbersome notation, we will be a bit informal and we will concentrate on the specific case n = 4. Take the solving scheme for n+1=5 depicted above, and consider the 4×4×4 cube obtained by removing the bottom face, the front face and the leftmost face. Such sub-cube is highlighted below by using orange (medium grey, if printed in black&white) cages. The sub-cube does not correspond to the solving scheme for n=4, since it has less active chickens than needed and those present are positioned differently than expected.  However, the active chickens in the removed faces can help to ``activate'' some lazy chickens in the needed positions. In fact, it is not difficult to see that we can turn some lazy chickens into active chickens in order to reach the situation depicted below Note that the considered sub-cube, depicted in the picture below on the left, if rotated upside down, as illustrated in the right part of the figure, will contain active chickens in the cages required by the solving scheme (and some more). Hence, by inductive hypothesis we have that all the chickens in the sub-cube can be made active, thus leading to the following situation: Now, also the lazy chickens in cages ci,j,k such that  0 <= j+k < i < n, i.e., in orange (medium grey, if printed in black&white) cages in the picture on the left below, can be made active. We thus reach the situation illustrated in the picture on the right. We are left to ``activate'' the chickens in the three triangle-shaped portions on the removed slices (the bottom level, the front face and the leftmost face): (i) cn,j,k with n < j+k, (ii) ci,0,k with 0 <= i < k < n, and (iii) ci,j,0 with 0 <= i <= j < n.  In each case the problem can be easily solved by noticing that each cage of such triangles is adjacent to a face of the sub-cube where all chickens are active, so that only two adjacent active chickens on the same slice are needed. Then, since the diagonals of such slices are active by the initial placing of regular active chickens, we can immediately conclude (as in the grid case) that also the three triangle-shaped portions can be made active.