2
$\begingroup$

2010 ZIO P3

Hello everybody! The problem you see is an algorithmic problem I could not solve. :( This is ZIO $2010$, P$3$.

The first thing that I thought when I saw the problem was that - "Umm... this sounds easy, just go step by step" and I did try to go step by step on the first part.. BUT this problem is too long and the fact that there are a lot of functions this takes too long. Of course, if the problem could be solved manually one by one, why would this be on a high school competition? I somehow managed to calculate a few values and tried to find a pattern but no use. The real difficulty of this problem in my opinion is the fact that all functions depend on each other somehow (leave the function $f$) which should probably be cleverly used to find the solution, I guess. Moreover, $g(n)$ and $h(n)$ give values $\pmod{10}$. Would some sort of a recursive algorithm work? (Note that in this competition, you are given $30$ minutes to solve one problem or $10$ minutes to solve a sub-case. That's pretty low.)

The answers are $3,0,2$.

Any help would be appreciated. Thanks!

$\endgroup$
1
  • $\begingroup$ $n\equiv 7 \bmod 11\implies f(n)=3$ $\endgroup$
    – user645636
    Nov 6, 2019 at 18:03

1 Answer 1

3
$\begingroup$

$$n\equiv 7 \bmod 11\implies f(n)=3$$ which then working back further leads to:$$n\equiv 3\bmod 11\implies f(n)=9$$ and$$n\equiv 1\bmod 11\implies f(n)=27$$ as well as, $$n\equiv 0\bmod 11\implies f(n)=81$$$$n\equiv 5\bmod 11\implies f(n)=243$$$$n\equiv 2\bmod 11\implies f(n)=729$$$$n\equiv 6\bmod 11\implies f(n)=2187$$$$n\equiv 8\bmod 11\implies f(n)=6561$$$$n\equiv 9\bmod 11\implies f(n)=19683$$$$n\equiv 4\bmod 11 \implies f(n)=59049$$ and exceptions are $n=4$, and $n\equiv 10\bmod 11$ because the latter gives back itself as the input value in $f$

$n\equiv 9\bmod 10\implies q(n)=f(n)+1$

etc.

$\endgroup$
2
  • $\begingroup$ Thanks @Roddy MacPhee for the answer but can you please elaborate on the solution a bit and explain it to me please. $\endgroup$
    – Vasu090
    Nov 9, 2019 at 3:36
  • $\begingroup$ set $4$ equal to $(2n+2 \bmod 11) -1$ then backsolve, $$4+1=5\equiv -6\equiv 2n+2 \bmod 11$$ that implies$$n+1\equiv -3\bmod 11\implies n\equiv -4\equiv 7\bmod 11$$ follow the same as before with the new $n$ for the rest. $\endgroup$
    – user645636
    Nov 9, 2019 at 8:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .