Maths Olympiad Prep

Library / /38 of 39

Combinatorics Difficulty 7.1 National Olympiad, round 2 Find the answer Italy

Problem:

π\pi cchi are animals that live in families of 1, 2 or 3 individuals. Originally a family of 3π3 \pi cchi was imported into Italy. A family of nπn \pi chi reproduces by growing by 2n22n-2 new individuals, forming a total of 3n23n-2, and splitting into new families (not necessarily do two families with the same number of individuals split in the same way). All families reproduce simultaneously at each brood. For example, after the first brood there are necessarily seven π\pi cchi, which could be divided into three families of two and one of one, or into one of three and two of two, or into seven of one, and so on. How many possibilities are there for the total number of π\pi cchi after the seventh brood?

This was a multiple-choice question, but the options didn't survive into the source we have. The answer given is B, and the solution below works it through.

Solution

Solution:

The answer is (B). The number of π\pi cchi after 7 broods can take any odd value between 7 and 2912^{9}-1, and no other. The answer to the question is therefore 29172+1=283=253\frac{2^{9}-1-7}{2}+1=2^{8}-3=253, since this is the number of odd numbers between 7 and 291=5112^{9}-1=511.

We justify the previous statement through the following facts:

a. a family consisting of only 1 π\pi cchio will forever continue to consist of a single π\pi cchio: obvious;

b. a family consisting of 2π2 \pi chi can give rise, after n1n \geq 1 broods, to no more than 2n+12^{n+1} π\pi cchi;

c. a family consisting of 3π3 \pi chi can give rise, after n1n \geq 1 broods, to any number of π\pi cchi that is odd and between 7 and 2n+212^{n+2}-1.

We prove statements (b) and (c) simultaneously by induction: assuming that (b) and (c) hold for a certain nn we will prove them for n+1n+1. Note that the base case n=1n=1 is obvious for both. Note also that the parity of the number of π\pi chi does not change after a brood, so the parity condition stated in point (c) is indeed necessary. Moreover:

b. in this case, after one brood we have 4π4 \pi cchi, which can live in four families of 1 (in which case at all subsequent generations we will still have 4π4 \pi chi), a family of 2 and two of 1, two families of 2, or a family of 3 and one of 1. In the various cases, statements (b) and (c) for nn broods show that - after a further nn broods - we will have at most
1+1+1+1,2n+1+1+1,2n+1+2n+1,(2n+21)+1 1+1+1+1, \quad 2^{n+1}+1+1, \quad 2^{n+1}+2^{n+1}, \quad\left(2^{n+2}-1\right)+1
π\pi cchi. Since each of these numbers is less than or equal to 2n+22^{n+2}, this proves statement (b) for n+1n+1 broods.

c. in this case, after one brood the 7π7 \pi cchi can be distributed into families in the following ways:
3+3+1,3+2+2,3+2+1+1,3+1+1+1+1,2+2+2+1,2+2+1+1+1,2+1+1+1+1+1,1+1+1+1+1+1+1. \begin{gathered} 3+3+1, \quad 3+2+2, \quad 3+2+1+1, \\ 3+1+1+1+1, \quad 2+2+2+1, \quad 2+2+1+1+1, \\ 2+1+1+1+1+1, \quad 1+1+1+1+1+1+1 . \end{gathered}
After a further nn broods, using the inductive hypothesis as above we obtain that in the various cases the total number of π\pi cchi is at most
2(2n+21)+1,(2n+21)+2(2n+1),(2n+21)+(2n+1)+1+1,(2n+21)+1+1+1+1,3(2n+1)+1,2(2n+1)+1+1+1(2n+1)+1+1+1+1+1,1+1+1+1+1+1+1. \begin{gathered} 2\left(2^{n+2}-1\right)+1, \quad\left(2^{n+2}-1\right)+2\left(2^{n+1}\right), \quad\left(2^{n+2}-1\right)+\left(2^{n+1}\right)+1+1, \\ \left(2^{n+2}-1\right)+1+1+1+1, \quad 3 \cdot\left(2^{n+1}\right)+1, \quad 2 \cdot\left(2^{n+1}\right)+1+1+1 \\ \left(2^{n+1}\right)+1+1+1+1+1, \quad 1+1+1+1+1+1+1 . \end{gathered}
It is easy to check that each of these numbers is less than or equal to 2n+312^{n+3}-1. Finally, if after the first brood the 7π7 \pi chi are organized into families as 3+3+13+3+1, then after a further nn broods the number of π\pi cchi will be of the form d1+d2+1d_{1}+d_{2}+1, where d1,d2d_{1}, d_{2} can take any odd value between 7 and 2n+212^{n+2}-1. The expression d1+d2+1d_{1}+d_{2}+1 can then take any odd value between 7+7+1=157+7+1=15 and 22n+22+1=2n+312 \cdot 2^{n+2}-2+1=2^{n+3}-1. It remains only to show that the number of π\pi cchi after n+12n+1 \geq 2 broods can also be 7, 9, 11 or 13, but this is easy. Indeed, if at some point the π\pi cchi organize into families of 1, from that point on their number will no longer grow, so it suffices to show that these numbers of π\pi cchi are achievable after at most two broods, for example as follows:
37;32+1+1+1+1+14+1+1+1+1+1=932+2+1+1+14+4+1+1+1=11;32+2+2+14+4+4+1=13 \begin{gathered} 3 \rightarrow 7 ; \quad 3 \rightarrow 2+1+1+1+1+1 \rightarrow 4+1+1+1+1+1=9 \\ 3 \rightarrow 2+2+1+1+1 \rightarrow 4+4+1+1+1=11 ; \quad 3 \rightarrow 2+2+2+1 \rightarrow 4+4+4+1=13 \end{gathered}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.