Replacing Numbers By Half Of Their Average

Discrete Mathematics Level 5

Let \(n>0\) be a positive integer. Prasun the gahn dew has written \(n\) \(1\)'s on a blackboard. Each second, Prasun chooses two integers \(a\) and \(b\) written on the blackboard and replaces them by \(\dfrac{a+b}{4}\) (he removes \(a\) and \(b\) and then writes \(\dfrac{a+b}{4}\) on the blackboard in their place). After \(n-1\) seconds, there is only one number remaining. Suppose that there exists a sequence of moves such that this remaining number is equal to \(\dfrac{1}{n}\). Find the number of \(n \leq 1000\) for which this is possible.

Details and assumptions

  • For example, if \(n=3\), initially the numbers written on the blackboard are \(1 \quad 1 \quad 1 \) (three \(1\)'s). Prasun chooses two of these \(1\)'s and replaces them by \(\dfrac{1+1}{4} = \dfrac{1}{2}\). After the first second, the numbers written on the blackboard are \(1 \quad \dfrac{1}{2}\). In the next second, Prasun replaces these numbers by \(\dfrac{1+1/2}{4} = \dfrac{3}{8}.\) This is the remaining number.

  • By default, \(n=1\) works, since the only number written on the blackboard is equal to \(1=\dfrac{1}{1}.\)


Problem Loading...

Note Loading...

Set Loading...