Maths Olympiad Prep

Library / /13 of 13

Combinatorics Difficulty 7.8 National olympiad, round 2 Find the answer

A ten-level 2-tree is drawn in the plane: a vertex A1A_{1} is marked, it is connected by segments with two vertices B1B_{1} and B2B_{2}, each of B1B_{1} and B2B_{2} is connected by segments with two of the four vertices C1,C2,C3,C4C_{1}, C_{2}, C_{3}, C_{4} (each CiC_{i} is connected with one BjB_{j} exactly); and so on, up to 512 vertices J1,,J512J_{1}, \ldots, J_{512}. Each of the vertices J1,,J512J_{1}, \ldots, J_{512} is coloured blue or golden. Consider all permutations ff of the vertices of this tree, such that (i) if XX and YY are connected with a segment, then so are f(X)f(X) and f(Y)f(Y), and (ii) if XX is coloured, then f(X)f(X) has the same colour. Find the maximum MM such that there are at least MM permutations with these properties, regardless of the colouring.

A number or a short expression. Spacing and $ signs are ignored.

Solution

The answer is 2272^{2^{7}}. First we need a suitable terminology. Similarly to 10-level 2-tree we can define a kk-level 2-tree for k1k \geq 1. For convenience we suppose that all the segments between vertices are directed from a letter to the next one. The number of the letter marking a vertex we call the level of this vertex; thus A1A_{1} is the only vertex of level 1,B11, B_{1} and B2B_{2} belong to level 2 and so on). We will also call descendants of a vertex XX all vertices which can be reached from XX by directed segments. Let T1T_{1} and T2T_{2} be two kk-level 2-trees with coloured leaves. We call a bijection f:T1T2f: T_{1} \rightarrow T_{2} isomorphism when two conditions are satisfied: (i) if two vertices XX and YY are connected by an edge in T1T_{1}, then f(X)f(X) and f(Y)f(Y) are connected by an edge in T2T_{2}, and (ii) if XX has some colour in T1T_{1}, then f(X)f(X) has the same colour in T2T_{2}. When T1=T2T_{1}=T_{2}, we call ff automorphism of the tree. By χ(k)\chi(k) we denote the minimal number of automorphisms a kk-level 2-tree with coloured leaves can have (the minimum is over all colourings). Our problem is to find χ(10)\chi(10). We start with almost obvious Lemma 1. Isomorphism of trees preserves the level of a vertex. Proof. Isomorphism ff cannot diminish the degree of a vertex. Indeed, neighbours of each vertex XX become neighbours of f(X)f(X), therefore the degree of f(X)f(X) is not less than the degree of XX. By pigeonhole principle it also means that the degree can not increase. It follows that the last level vertices go to the last level vertices. Therefore vertices of the previous level go to the same level, since they remain neighbours of the last-level vertices, and so on. Now we are ready to solve the problem. Proposition 1. For each k2k \geq 2 we have χ(k)(χ(k1))2\chi(k) \geq(\chi(k-1))^{2}. Proof. In a kk-level tree the descendants of B1B_{1} (including B1B_{1} ) form a kk-1-level tree T1T_{1}. This graph has at least χ(k1)\chi(k-1) different automorphisms. The same is true for tree T2T_{2} formed by the descendants of B2B_{2}. Let gg and hh be automorphisms of T1T_{1} and T2T_{2} respectively. Now we can define mapping ff of the whole tree applying gg to descendants of B1,hB_{1}, h to descendants of B2B_{2} and AA to itself. Obviously ff is an automorphism: for X=AX=A the condition holds since B1B_{1} and B2B_{2} were mapped to themselves (by Lemma 1 ), and for XX in T1T_{1} or T2T_{2} because gg and hh are automorphisms. Thus for each pair (g,h)(g, h) there is an automorphism ff, different pairs produce different ff, and the number of pairs is at least (χ(k1))2(\chi(k-1))^{2}. Corollary. For k3k \geq 3 we have χ(k)22k3\chi(k) \geq 2^{2^{k-3}}. Proof. This inequality is proved by induction, with Proposition 1 as induction step. It remains to check it for k=3k=3. If in a 3 -level 2 -tree at least one of the vertices B1,B2B_{1}, B_{2} has two descendants of the same colour, there is an automorphism exchanging these two vertices and preserving the rest. If each of B1,B2B_{1}, B_{2} has one blue and one golden descendant, there is an automorphism exchanging B1B_{1} and B2B_{2} and preserving colours of their descendant. In both cases the number of automorphisms (including the identical one) is at least 2. We already know that every 3-level 2-tree with (four) coloured leaves there are at least two colour-preserving automorphisms. Now every nn-level tree, n3n \geq 3, has 2n32^{n-3} vertices of level n2n-2, and the descendants of each of these vertices form a 3-level tree. It is enough to consider automorphisms preserving vertices of level n3n-3 (and, a fortiori, of all lesser levels). Such an automorphism can act on the descendants of each of 2n32^{n-3} vertices of level n2n-2 in at least 2 ways. Thus there are at least 22n32^{2 n-3} such automorphisms. It remains to construct for each k3k \geq 3 a colouring of kk-level tree a colouring admitting exactly 22k32^{2^{k-3}} automorphisms. As it happens sometimes, we will prove somewhat more. Proposition 2. For each k3k \geqslant 3 there are three colourings M1,M2,M3\mathcal{M}_{1}, \mathcal{M}_{2}, \mathcal{M}_{3} of leaves of kk-level 2-tree such that the trees with these colourings are not isomorphic, and each of these colourings admits 22k32^{2^{k-3}} automorphisms exactly. Proof. For k=3k=3 let C1,C2C_{1}, C_{2} be the descendants of B1B_{1}, and C3,C4C_{3}, C_{4} the descendants of B2B_{2}. The three colourings are the following: C1,C2,C3C_{1}, C_{2}, C_{3} blue, C4C_{4} golden; C1,C2,C3C_{1}, C_{2}, C_{3} golden, C4C_{4} blue; C1,C3C_{1}, C_{3} blue, C2,C4C_{2}, C_{4} golden. Obviously the trees with these colourings are not isomorphic and admit two automorphisms each. The induction step. Let M1,M2,M3\mathcal{M}_{1}, \mathcal{M}_{2}, \mathcal{M}_{3} be the desired colourings of kk-level tree. Consider the following colourings of the (k+1)(k+1)-level tree: - M1\mathcal{M}_{1} for descendants of B1B_{1} and M2\mathcal{M}_{2} for descendants of B2B_{2}; - M2\mathcal{M}_{2} for descendants of B1B_{1} and M3\mathcal{M}_{3} for descendants of B2B_{2}; - M3\mathcal{M}_{3} for descendants of B1B_{1} and M1\mathcal{M}_{1} for descendants of B2B_{2}. It is quite obvious that these three colourings are not isomorphic and have the desired number of automorphisms.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.