Recurse and induct.

Strong induct, btw copied from oly arena mock and BMO

alexanderhamilton124 wrote: Strong induct, btw copied from oly arena mock and BMO Send source

From the OMC RMO livesolve. solved with rawlat_vanak, AdhityaMV, zvfrozel, and mathscrazy. We first note that $f(2^k) = 2^{k-1}$ for $k \geq 1$ and $f(1) = 1$. For $k \geq 2$, this can be proven by noting that any subset of $2^1, \dots, 2^{k-1}$ may be chosen as the middle part of the $2^k$-chain. We will induct on $m \geq 0$. At $m = 0$, we have $f(3) = 1$, which fits. Now let $m > 1$. We focus on the term that precedes $n$. We obtain \begin{align*} f(2^m \cdot 3) &= \sum \limits_{1 \leq i < m} f(2^{i} \cdot 3) + \sum \limits_{1 \leq i \leq m} f(2^i) + 1 \\ &= \sum \limits_{0 \leq i < m} (i \cdot 2^{i-1} + 2^{i}) + \sum_{1 \leq i \leq m} 2^{i-1} + 1 \\ &= 2^{m+1} - 1 + \sum_{0 \leq i < m} i \cdot 2^{i-1}\end{align*}Define $P(x) = \sum \limits_{0 \leq i < m} x^i = \frac{x^m-1}{x-1}$. Looking at $P'(1)$, we may compute the term in the above summation to be \[m \cdot 2^{m-1} - 2^{m} + 1\]Thus \[f(2^m \cdot 3) = m \cdot 2^{m-1} - 2^{m} + 1 + 2^{m+1} - 1 = 2^{m-1}(m+2),\]as we wanted to show. $\square$

It is not hard to see that for composite $n$, $$f(n)=1+\sum_{d\mid n,\, 1<d<n} f(d),$$and that for prime $n$, $f(n)=1$. Note that $f(2)=1$ and $$f(2^n)=1+f(2)+f(4)+\dots+f(2^{n-1})\implies f(2^n)-f(2^{n-1})=1+f(2)+f(4)+\dots+f(2^{n-2})=f(2^{n-1})\implies f(2^n)=2f(2^{n-1})$$suggests that $f(2^n)=2^{n-1}$. Now, $$f(2^m\cdot 3)= 1+f(3)+\sum_{i=1}^{m-1} f(3\cdot 2^i) + \sum_{i=1}^m f(2^i).$$We proceed by strong induction. Suppose $f(2^k \cdot 3) = 2^{i-1} (i+2)$ holds for all $i\leq m-1$. We also check and find that $f(3)=1$. We have $$f(2^m\cdot 3)=2+\sum_{i=1}^{m-1}2^{i-1} (i+2)+\sum_{i=1}^m 2^{i-1}=2+\sum_{i=1}^{m-1}2^{i-1}\cdot\, i+\sum_{i=1}^{m-1} 2^i+\sum_{i=1}^m 2^{i-1}.$$We know that $\sum_{i=1}^{m-1} x^i = \frac{x^m-x}{x-1}$, and by differentiating, we get $$\sum_{i=1}^{m-1} x^{i-1}\cdot i=\frac{(x-1)(x^{m-1}\cdot m-1)-(x^m-x)}{(x-1)^2}.$$For $x=2$, the sum evaluates to $2^{m-1}\cdot m-2^m+1$. Therefore, we indeed have $$f(2^m\cdot 3)=2+2^{m-1}\cdot m-2^m+1+2^m-2+2^m-1=2^{m-1}\cdot m +2^m=2^{m-1}(m+2),$$and hence we are done by induction.

Claim: $$f(2^{m+1}.3) = 2f(2^m.3)+2^m$$ Proof: The $2$ factor can be explained as the chains present in $f(2^m.3)$ will occur in $f(2^{m+1}.3)$, once all together and once without $2^m.3$. The other $2^m$ comes as $(1,...,2^{m+1},2^{m+1}.3)$ chains are left to count. Between $1$ and $2^{m+1}$, $2,4,8,...,2^m$ can come, which makes a total of $2^m$ ways. We can finish by inducting on m.

Why induct when there are much better solutions? (Posting solution) Note that in any $n-$chain where $n$ is of the given form, some of the first terms will be pure powers of 2, until we have a multiple of 3 and then all the numbers following will be multiples of 3. Let the first multiple of $3$ in an $n-$chain be $2^a \times 3$. Note that before this element we may have any elements in the set $\{2, 2^2, \dots, 2^{a}\}$ (for example the set is empty when $a = 1$). There are $2^a$ ways to choose elements from this set. Also, after this element there are terms of the form $3k$, where $k$ is in the set $\{2^{a+1}, 2^{a+2}, \dots, 2^{m-1}\}$. We take two cases: Case 1: $a < m$. Then there are $2^{m-a-1}$ ways to choose elements from this set, so overall we get $\sum_{a = 0}^{m-1} 2^a \times 2^{m-a-1} = \sum_{a = 0}^{m-1} 2^{m-1} = m 2^{m-1}$ chains. Case 2: $a = m$, then this set is empty, yielding $2^m$ chains. Overall summing over both cases we have $ m 2^{m-1} + 2^m = \boxed{(m+2)2^{m-1}}$ chains, as desired. $\square$

"better" is not the right word; also induction is far more natural and intuitive

alexanderhamilton124 wrote: "better" is not the right word; also induction is far more natural and intuitive Better in that it shows where the number comes from, in a sense.

I did Q3 and 6 full, Q5 and 1 partial from class 12 west bengal. Do you think I have any chance at all?

I did Q6 like this: there are $2^{m-1}$ chains for $f(2^m)$. Now suppose we describe a ‘link’ as a tuple $(a_k,a_{k+1})$ in a particular chain. Suppose in total there are $N$ links in all the chains of $2^m$ Now for any chain of $2^m$, we can convert it to a chain for $2^m\cdot3$ in three ways: (A) Simply add $2^m\cdot3$ at the end. So in total there are $2^{m-1}$ ways. (B) Take any link, multiply the last element by $3$, and multiply all the other next elements in the chain by $3$. This can be done in $N$ ways. (C) Take any link (a,b), cut it, and insert $3a$ between them. Multiply all next elements in chain by $3$. This can also be done in $N$ ways. Then I proved that $N=2^{m-2}({m-1})$, which gives us $2N+2^{m-1}=$required answer How much can I expect?

Eka01 wrote: alexanderhamilton124 wrote: Strong induct, btw copied from oly arena mock and BMO Send source see discod

I also have the same solution but I did the induction and the recursion formula correctly but when evaluating the actual summation I was messing up may be like missing +1,-1. What could be the partial marks I can get?

Mquej555 wrote: I also have the same solution but I did the induction and the recursion formula correctly but when evaluating the actual summation I was messing up may be like missing +1,-1. What could be the partial marks I can get? >= 12-13 i think (youre talking about the AGP right)

also p5 on bmo round 1 2022 16th November

Siddharthmaybe wrote: also p5 on bmo round 1 2022 16th November I'm not sure but as far as I know there are 4 problems in BMO

newton_24 wrote: Siddharthmaybe wrote: also p5 on bmo round 1 2022 16th November I'm not sure but as far as I know there are 4 problems in BMO Bmo in this case is bmo1.

I HATE COMBI BLUFFED ONLY

$f(1)=1$ $f(2)=1$ and in general $f(2^k)=2^{k-1}$ Proof: $f(2^k)=\sum_{i=1}^{k-1}f(2^i)$ which further gives us $f(2^{k})-f(2^{k-1})=\sum_{i=1}^{k-2}f(2^{i})\implies f(2^k)=2f(2^{k-1})$, we can continue this to get $f(2^k)=2^{k-1}$ $f(3)=1$ and in general $f(2^m\cdot 3)=\sum_{i=0}^{m} f(2^{i}\cdot 3)+\sum_{i=0}^{m}{f(2^i)}$ Proof: We assume it is true for $m-1$ and then we show it is also true for $m$. \begin{align*}f(2^m\cdot 3)&=\sum_{i=0}^{m} f(2^{i}\cdot 3)+\sum_{i=0}^{m}{f(2^i)}\\&=\sum_{i=1}^{m-1}(2^{i-1}(i+2))+\sum_{i=1}^{m}f(2^{i-1})+2\\&=m\cdot 2^{m-1}-2^{m}+2^{m}+1-2+2^m+1=2^{m-1} (m+2)\end{align*}