Is it Number Theory or Combinatorics ?

Discrete Mathematics Level 5

For \(k≥1\), let \(a_{k}\) be the greatest divisor of \(k\) which is not a multiple of \(3\).

Set \(S_{0}=0\) and \(S_{k}=a_{1}+a_{2}+...+a_{k}\) for \(k≥1\).

Find the number of integers \(k\) with \(0≤k<3^{15}\) such that \(S_{k}\) is divisible by \(3\).

Note A generalization of this problem was once proposed for IMO.

Try other interesting combinatorics in my set Hard


Problem Loading...

Note Loading...

Set Loading...