Passing Balls: Hard Version

Read the Medium solution first.

Now since the tree is tall and numbers of balls are a lot, we can only pass our algorithm into the computer. Below is the implementation in C++.

1
2
3
4
5
6
7
8
9

int position(int height, int ball) {
    int x = 1, p = ball;
    for (int i = 0; i < height; i++)
        if (p&1)
            x = (2 * x) % 1000, p = (p + 1) / 2;
        else
            x = (2 * x + 1) % 1000, p = p / 2;
    return x;
}

Call the function position(100, 3366) and we will get our desired answer.

I got my solution from an observation I had. Every ball with even index will be passed to the right child, while every ball with odd index will be passed to the left child. 3366th ball will be passed down to the right child as its 1683rd ball. This 1683rd ball will be passed down to the left child as its 842nd ball. This process repeats recursively, and you can use this to deduce which path the 3366th ball would've took. Once you have the path, it is easy to calculate which leaf the ball would've ended up in. This is my python code which does that.

import math

Ball = 3366
Height = 100

def f(v, ball):
    while ball > 1:
        v.append(ball % 2 == 0)

        ball = math.ceil(ball / 2)

def ff(v):
    sm = 1

    for dr in v:
        sm = sm * 2 + dr

    return sm

v = list()

f(v, Ball)

while len(v) < Height:
    v.append(False)

print(ff(v))

it outputs 2083143601107473657586501287936. The last 3 digits of this output is 936, which is the answer.

I used a similar method to Laurent, in which I also noticed that the process is related to binary numbers. Why? We can see this recursively: try labeling the nodes of the tree as if they were the leaves of this process for whatever height they are at. We get ${1}, {1,2}, {1,3,2,4}, {1,5,3,7,2,6,4,8}, ...,$ and so on.

It is clear to see that each sequence is produced by taking the previous one and inserting $k + 2^n$ after the value $k$ , where $n$ is the height of the tree. Therefore each leaf corresponds to a finite series of distinct powers of $2$ . Then it is only natural to pursue the binary expansions.

Furthermore, by our insertion pattern, we see that a one in the binary expansion corresponds to going to the right on the tree. It is a known property of binary trees which are labeled in this way that the left node of a node labeled $n$ is $2n$ and that the right node is $2n+1$ .

Now, since our first node is labeled as $1$ , we must look at one less than our desired ball. It is especially handy that we need to read our binary digits backward, and that the binary algorithm works backward. After we run out of binary digits, i.e., we hit the last $1$ and go to the right for the last time, we must go left until we are in the last row.

Hopefully, this explanation is very clear; here is my implementation in python, which has variables (height, n) set for generalization:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

ball = 1
height = 100
n = 3366
n -= 1
while n > 0:
    if n % 2 == 0:
        ball *= 2
    else:
        ball = 2*ball +1
    n //= 2

while (ball < 2**height):
    ball *= 2

print(ball)

This reverse the number $3365_{10}=000\cdots000110100100101_2$ to $101001001011\underbrace{000\cdots000_2}_{88\text{ times}}=2635·2^{88}$ .

Add this to the number of the first leave $2^{100}$ : $2635·2^{88}+2^{100}=2,083,143,601,107,473,657,586,501,287,\boxed{936}$

$2635·2^{88}+2^{100}$ modulo 1000 with a simple calculator:

$\begin{aligned}&2^{88}&=2^{64}·2^{16}·2^8&\equiv616·536·256&=84,525,056&\equiv56,\\&2^{100}&=2^{64}·2^{32}·2^4&\equiv616·296·16&=2,917,376&\equiv376\end{aligned}$

and answer is $635·56+376=35,936\equiv\boxed{936}$ .