Problem A. 896. (January 2025)
A. 896. Marine biologists are studying a new species of shellfish whose first generation consists of 100 shellfish, and their colony reproduces as follows: if a given generation consists of \(\displaystyle N\) shellfish (where \(\displaystyle 5 \mid N\) always holds), they divide themselves into \(\displaystyle N/5\) groups of 5 shellfish each. Each group collectively produces 15 offspring, who form the next generation. Some of the shellfish contain a pearl, but a shellfish can only contain a pearl if none of its direct ancestors contained a pearl. The value of a pearl is determined by the generation of the shellfish containing it: in the \(\displaystyle n\)-th generation, its value is \(\displaystyle 1 / 3^n\). Find the maximum possible total value of the pearls in the colony.
Proposed by: Csongor Beke, Cambridge
(7 pont)
Deadline expired on February 10, 2025.
Let's consider \(\displaystyle n\) generations of the shellfish, és let's call a set \(\displaystyle \{s_1,s_2,...,s_n\}\) of shellfish chain, if \(\displaystyle s_{i+1}\) is an offspring of \(\displaystyle s_i\) (for all \(\displaystyle 1\le i \le n-1\)). Observe that any chain can contain at most one pearl. Let \(\displaystyle c(s)\) be the number of chains containing shellfish \(\displaystyle s\). Based on our previous observation, \(\displaystyle \sum_{k\in P} c(s)\le C\), where \(\displaystyle C\) denotes the total number of chains and \(\displaystyle P\) denotes the set of shellfish containing a pearl. Since each chain contains exactly one shellfish from each generation, and shellfish of the same generation appear in the same number of chains (since they have the same number of offsprings and the same number of parents), therefore if \(\displaystyle N(s)\) denotes the number shellfish in the generation of shellfish \(\displaystyle s\), \(\displaystyle c(s)=C/N(s)\). Finally, if \(\displaystyle S_i\) denotes the set of shellfish in the \(\displaystyle i^{\text{th}}\) generation (where \(\displaystyle |S_i|=100\cdot 3^{i-1}\)), then
\(\displaystyle C\ge \sum_{s\in P} c(s)=\sum_{i=1}^{n}|P\cap S_i|\cdot \frac{C}{|S_i|}=\sum_{i=1}^{n}|P\cap S_i|\cdot \frac{C}{100\cdot 3^{n-1}}=\frac{3C}{100}\cdot \sum_{i=1}^{n}|P\cap S_i| \cdot \frac{1}{3^i}=\frac{3C}{100}\cdot \sum_{s\in P} v(s), \)
where \(\displaystyle v(s)\) denotes the value of shellfish \(\displaystyle s\). From here the total value \(\displaystyle \sum_{s\in P} v(s)\) of the shellfish with pearls is at most 100/3. Since this is true for an arbitrary number of generations of shellfish, it remains valid even for an infinite number of generations by tending to infinity with \(\displaystyle n\). This value can be easily attained, e.g. if every shellfish from the first generation contains a pearl.
Remark. Using the argument we can prove the following slightly more general statement: if every shellfish in the same generation have the same number of offsprings and the same number of parents (which leads to the key observation that every shellfish of the same generation will appear in the same number of chains), and the value of each shellfish is reversely proportional to the number of shellfish in its generation (hence, it's also proportional to the number of chains containing the given shellfish), then we cannot get a greater value compared to the simple case when every shellfish of the first generation contains a pearl.
Statistics:
21 students sent a solution. 7 points: Aravin Peter, Balla Ignác , Bodor Mátyás, Czanik Pál, Forrai Boldizsár, Gyenes Károly, Holló Martin, Keresztély Zsófia, Kocsis 827 Péter, Minh Hoang Tran, Morvai Várkony Albert, Pázmándi József Áron, Sánta Gergely Péter, Szakács Ábel, Tianyue DAI, Varga Boldizsár, Virág Tóbiás, Vödrös Dániel László, Wágner Márton, Xiaoyi Mo. Not shown because of missing birth date or parental permission: 1 solutions.
Problems in Mathematics of KöMaL, January 2025