if I'm not mistaken, the answer is $M=g(n)=2^{2^{n-3}}$ for $n$-level trees ($n\geq 3$).

now we prove $g(n)\geq2^{2^{n-3}}$ using induction on $n$. a straightforward check for $n=3$ shows the base case is indeed true, in fact $g(3)=2$. take an $n+1$-level tree and look at the two $n$-level subtrees under it. each of those have at least $g(n)$ good permutations so taking one of each, we find that the large tree has at least $g(n)^2$ good permutations hence $g(n+1)\geq g(n)^2\geq2^{2^{(n+1)-3}}$. to finish the problem, we inductively create an equality case for all $n$. we represent the coloring of the leaves of an $n$-level tree as a binary string of length $2^{n-1}$ where for example 1 means blue and 0 means golden. define $X_3=(1,1,1,0)$ and $Y_3=(1,0,1,0)$, note that both of these have exactly $2$ good permutations. we define $X_{n+1}=(X_n,Y_n)$ and $Y_{n+1}=(X_n,X_n^c)$ (where $A^c$ means swapping ones and zeroes in $A$). by induction we know that $X_n, X_n^c,Y_n$ all have exactly $2^{2^{n-3}}$ good permutations. Now for the two $n+1$-level trees, if a permutation swaps the two $n$-level trees, it cannot be a good permutation because $X_n,Y_n,X_n^c$ all have different amount of blue leaves! note that $X_n$ always has more blues than golds so $X_n^c$ has more golds than blues but $Y_n$ has equal amounts of both. so the first swap cannot happen so any permutation leaves the two n-level subtrees in their place so each good permutation now, is a choice of a good permutation for each of those subtrees so we now have exactly $(2^{2^{n-3}})^2=2^{2^{(n+1)-3}}$ good permutations for $X_{n+1}$ (which proves it for $X_{n+1}^c$ as well) and $Y_{n+1}. so we are done

İ found that g(n) >= 2^(2^n-3) but couldnt found an example, cuz i hadnt left much time:[. But anyway, that is a good example

I found the construction quite natural if you think about it as follows: The proof of the lower bound actually shows that any of the $2^{n-3}$ groups of four vertices at the lower two levels already has an additional symmetry, leading to $2^{2^{n-3}}$ without any induction. So if we want to have an example without any further symmetries, we need two things to happen: 1) all the $2^{n-3}$ groups need to have only one symmetry, and 2) there should be no (non-trivial) symmetries on other levels. Now we note that there are exactly three types of such groups of four vertices (up to internal symmetry): $0001, 0111$ and $0101$. Call them $A,B,C$. Next, to not have any other symmetries on the level one higher we should combine always two different of them, i.e. we should choose $BC, CA$ or $AB$. But this is again three choices, so the argument can be iterated! So reversing the argument, we can start with $A$ on the top level and then in each lower level write $BC$ if $A$ above, $CA$ if $B$ above and $AB$ if $C$ above. So in the second step we write $BC$, then $CAAB$, then $ABBCBCCA$ etc. In the final step, replace $A,B,C$ by their original meanings. It only takes a moment of thought to see that this indeed achieves exactly what we desired.

Tintarn wrote: I found the construction quite natural if you think about it as follows: The proof of the lower bound actually shows that any of the $2^{n-3}$ groups of four vertices at the lower two levels already has an additional symmetry, leading to $2^{2^{n-3}}$ without any induction. So if we want to have an example without any further symmetries, we need two things to happen: 1) all the $2^{n-3}$ groups need to have only one symmetry, and 2) there should be no (non-trivial) symmetries on other levels. Now we note that there are exactly three types of such groups of four vertices (up to internal symmetry): $0001, 0111$ and $0101$. Call them $A,B,C$. Next, to not have any other symmetries on the level one higher we should combine always two different of them, i.e. we should choose $BC, CA$ or $AB$. But this is again three choices, so the argument can be iterated! So reversing the argument, we can start with $A$ on the top level and then in each lower level write $BC$ if $A$ above, $CA$ if $B$ above and $AB$ if $C$ above. So in the second step we write $BC$, then $CAAB$, then $ABBCBCCA$ etc. In the final step, replace $A,B,C$ by their original meanings. It only takes a moment of thought to see that this indeed achieves exactly what we desired. The exact way I constructed. Hope I could clearly explain on the contest...

Hi, wanted to ask something. On the marking scheme , they give one point for answer, and alsoThey say that they give 3 point for lower bound and 3 point for example. So i just showed the lower bound and wrote that my claim was 2^(2^7). Does that mean i will get 3 point (for lower bound) or 4 point (for the answer too) ?

Evolhimar wrote: Hi, wanted to ask something. On the marking scheme , they give one point for answer, in 3. , They say that they give 3 point for lower bound and 3 point for example. So i just showed the lower bound and wrote that my claim was 2^(2^7). Does that mean i will get 3 point (for lower bound) or 4 point (for the answer too) ? They've also mentioned that these scores are not summed up.

Talgat05 wrote: Evolhimar wrote: Hi, wanted to ask something. On the marking scheme , they give one point for answer, in 3. , They say that they give 3 point for lower bound and 3 point for example. So i just showed the lower bound and wrote that my claim was 2^(2^7). Does that mean i will get 3 point (for lower bound) or 4 point (for the answer too) ? They've also mentioned that these scores are not summed up. So u mean, its 3 points?

I'm just adding a picture.

If you misread the problem and thought (falsely) that all vertices are coloured and not just the leaves, here is a solution.

Does anyone has the marking scheme of the day 2?

Evolhimar wrote: Talgat05 wrote: Evolhimar wrote: Hi, wanted to ask something. On the marking scheme , they give one point for answer, in 3. , They say that they give 3 point for lower bound and 3 point for example. So i just showed the lower bound and wrote that my claim was 2^(2^7). Does that mean i will get 3 point (for lower bound) or 4 point (for the answer too) ? They've also mentioned that these scores are not summed up. So u mean, its 3 points? Unfortunately, yes

So u get that 1 point for writing the answer, only if u both dont prove the lower bound and u dont give an example?

Make the question general such that we are working on $n$-level $2$-tree.Notice that we have $3$ kinds of points in $2-tree$. $(1)$ Vertices connected with $2$ segments (Starting vertex) $(2)$ Vertices connected with $1$ segments (Last level vertices of tree) $(3)$ vertices connected with $3$ segments (middle vertices) It is easy to see that last vertices ($J_i$) has property $f(J_i)=J_j$. Since $J_i,J_{i+1}$ ($i$ is odd here )are connected to the same vertex, we have $f(J_i)=J_{j+1}$. In more informal way, pairs must stay pairs ( possibly swapping each other).Notice that after we permutate all $J$s, other points are permutated too ( there are no more extra permutations after that). So, it is enough to work on our last level only. And "pairs of pairs" $J_{i}J_{i+1}, J_{i+2}J_{i+3}$ ( where $ i \equiv 1 \mod 4)$ must stay same. There are total $2^{n-3}$ pairs of pairs, Any sets pairs of pairs have additional symmetry, giving lower bound as $M \ge 2^{2^{n-3}}$, now we show equality case. To make a construction for equality case, we must have such pairs of pairs such that they have one symmetry only ( $0001, 0111, 0101 $ and their symmetry where $0,1$ shows colors), call these $A,B,C$, to not have symmetry, we must have $AB,BC,CA$ as combinations, call them $X,Y,Z$. to not have symmetry, we must have $XY,YZ,ZX$, call them $N,L,R$. We can repeat this prosses, each prosses reduces number of points $2$ times. Since we have $3$ points, reduce the number of points to $4$, , call the last combinations $U,V,W$, select $U,V,W,U$, which is obviously there are no more symmetries. Since our question asked for special case $n=10$, our answer is $M \ge 2^{128}$, hence we are done!. $\blacksquare$

How do permutations work? We can think of permutations as taking any vertice (except the lowest ones) and swapping places of two trees that come out of it below. Clearly, after any permutation, all vertices remain on the same level as they were before. Answer. Basically just induct. We start with small cases. A $3$-level tree has at least $2$ permutations (including empty permutation). A $4$-level tree is just a vertice connected to two $3$-level trees, each of whom had $2$ permutations, so the minimum number of permutations for a $4$-level tree has to be $2\times 2=4$. The sequence is $2, 4, 16, 256...$, which is just $f(n)=2^{2^{n-3}}$, where $n$ is the number of levels. We now show this minimum is achievable. Let B mean blue and G mean golden $\bullet$ For the $3$-level tree, it's easy to see that colorings $$(GBBB), (BGBB), (BBGB), (BBBG), (BGGB), (GBGB), (BGBG), (GBBG), (BGGG), (GBGG), (GGBG), (GGGB)$$have exactly $2$ permutations each. $\bullet$ For the $4$-level tree, we just need to ensure that swapping two $3$-level trees will not cause any new possible permutations. To do that, we just let each $3$-level tree have a different amount of B's, for example, $(GBBG)$ and $(GGGB)$. So $4$-level tree $$(GBBG)(GGGB)$$has exactly $4$ permutations. $\bullet$ For the $5$-level tree, we just need to ensure that swapping two $4$-level trees will not cause any new permutations. To do this we just let each $4$-level trees have a mirrored set of $3$-level trees. In this case, after swapping two $4$-level trees we will further need to swap $3$-level trees to achieve new permutations, but swapping $3$-level trees is not possible due to our construction of the $4$-level tree above. So $5$-level tree $$\{(GBBG)(GGGB)\}\{(GGGB)(GBBG)\}$$has exactly $16$ permutations. $\bullet$ For the $6$ level tree we mirror the $4$-level trees. So $6$-level tree $$[\{(GBBG)(GGGB)\}\{(GGGB)(GBBG)\}][\{(GGGB)(GBBG)\}\{(GBBG)(GGGB)\}]$$has exactly $256$ permutations. $\bullet$ For $n$-level tree we just mirror the $(n-2)$-level trees. And so on.