## Question 1

Divide a circle into 6 sectors. Write 1,0,1,0,0,0 in each sector. A move consists of incrementing neighbouring numbers, can we get all numbers in the circle to be equal by a sequence of these moves?

I tried brute force and as intuition seems to suggest, this isn’t possible.

import operator

def move(n):
if(sum(n)>10):
if(n.count(n[0]) == len(n)):
print("Hooray")
return
print(n)
return

start = (1,0,1,0,0,0)
move(start)

SOLUTION? Why No?

## Question 2

Of all the sets of integers whose sum is 1000, what’s the set which has maximum product?

## Solution 2

Consider $y = a^b$, does $a$ or $b$ contribute more to the size of $y$? This is what I was first faced with. I could take $500$ $2$’s and its sum would be $1000$. Here the product would be $2^{500}$. If you thought $b$ contributed more you would go with this.

Say you thought $a$ was more important, in this case $125$ $8$’s would sum to $1000$. Note the product here is $8^{125}$.

Even though we humans are naturally bad at grasping enormous numbers, We can write $8^{125}$ as ${2^{3}}^{125} = 2^{375}$ which is obviously less than $2^{500}$.

Ok as some of us might have guessed, its better to multiply more of a smaller number than to multiply a larger number more number of times.

Multiplication is repeated Addition, while Power is repeated Multiplication.

But $2^{500}$ is still not the answer. Let us divide $k$ (a constant) evenly into $\frac{k}{x}$ pieces (each of size $x$). So we wish to maximize the product

is maximum. Note how $\frac{1000}{2} = 500$ and $\frac{1000}{8} = 125$.

To maximize $y$, we differentiate and equate that to $0$.

So you can see how no matter what the sum is (doesn’t have to be $1000$) the maximum product is when $x = e \$, But we can’t choose $e$ as it’s not a Integer. So we choose the nearest integer to $2.73$ i.e. $3$.

So the ideal answer should be full of $3$’s. But as $1000\%3 == 1$ we can take $333$ $3$’s then we would have to take $1$ as the last integer and this sucks for maximizing product. So $332$ $3$’s and $2$ $2$’s is optimal as $3\times 1 < 2 \times 2$.

In the case that $k\%3 == 2$ then we should take $\lfloor \frac{k}{3} \rfloor$ number of$3$’s and a single $2$.

$3^{332}\times2^2$

## Question 3

A dragon has $100$ heads, A soldier can cut off $24$ heads but then $15$ will grow back, he can cut off $17$ heads but then $2$ will grow back. He can also cut off $11$ heads but then $20$ will grow back. Will the dragon ever die if the soldier tries various combinations of these moves? If so how?

## Solution 3

Move $1$ causes a $(-24+15) = -9$ change in heads.
Move $1$ causes a $(-17+2) = -15$ change in heads.
Move $1$ causes a $(11-20) = 9$ change in heads.

Say we do $k_1$ number of move $1$, $k_2$ number of move $2$, and $k_3$ number of move $3$. The net change is,

We want to find integer values for $k_1, k_2, k_3$ such that $\Delta \text Heads = -100$. Solving for it,

$(k_3 - k_1)$ will also be a integer, say $k_0$.

As a fraction plus a integer can never be a integer, so we can be sure there exists no integers $k_1,k_2, k_3$ such that the above equation is satisfied.

The dragon can never be killed

## Question 4

What is the remainder when you divide $n = (174\cdots174)$ (here $174$ is repeated 16 times, $n$ has $48$ digits) with $999$?

## Solution 4

The first key insight is to remember how the divisibility rule for $9$ (which happens to also be used for $3$) was derived. If a decimal number $n$ has the $k$ digits $n_k n_{k-1} \cdots n_1$ then,

We know that $(10^n - 1)$ is always divisible by $9$. So if $(n_k + n_{k-1} + \cdots + n_2 + n_1)$ is divisible by $9$, the whole number is divisible by $9$.

Coming to this problem, we need to divide with $999$. Which peculiarly divides $10^n$ as shown below,

So it leaves a remainder of $1, 10, 100$ periodically with powers of $10$, unlike $9$ which was nice enough to only leave $1$ as a reminder - this had helped us isolate just the digits from $n$.

So our $n$ in terms of its $48$ digits would be,

We can’t separate any multiples of $999$ from the first $3$ digits, so let’s write,

We can separate digits based on which power of $10$ accompanies them - $10^{3k}, 10^{3k+1}, 10^{3k+2}$.

Here we needed to find out how many elements are there in the set $3, 6, \cdots , 45$. One way is to calculate for $n$ in the AP equation $a_n = a + (n-1)d$. So $45 = 3 + (n-1)3$, $n = 15$.

We can do $\frac{2784}{999}$ by hand and get the answer $786$.

The remainder is 786

## Question 5

There is a set containing $1, 2, \cdots, 199$, we proceed to continuously select (at random) $2$ numbers ($a$ and $b$) then compute the number $c = (a+b+ab)$. We remove both $a$ and $b$ while we add $c$ to this set. Finally what will the final remaining number be?

## Solution 5

Note that

So now the operation becomes “selecting (at random) $2$ numbers ($a$ and $b$) then compute the number $c = (a+b+ab) = (a+1)(b+1) - 1$. We remove both $a$ and $b$ while we add $c$ to this set”.

So for $[x_1, x_2, \cdots, x_n]$, after the first operation it would become
$[(x_1+x_2 + x_1 x_2), x_3, \cdots, x_n]$ which is same as $[((x_1+1)(x_2+1)-1), x_3, \cdots, x_n]$. So on repeatedly applying this operation we get

So you get where this is going,

The final term will be

So for $[x_1, x_2, \cdots, x_n] = [1,2,3, \cdots, n]$ as given in the question means that the final term will be,

## Question 8

Find n, where $n + d(n) + d(d(n)) = 1000$. $d(n)$ is the digital sum of $n$.

Digital sum is the digit sum of $n$. I was baffled by this term, for it was the first time I had heard it.

## Solution 8

We know that $n>d(n)>d(d(n))$ So as all $3$ terms are positive, $n$ can be at max a $3$ digit number. Any larger than that and the sum will overshoot $1000$.

It can’t be a $2$ digit number either as even if $n$ is $99$ the largest $2$ digit number, $n + d(n) + d(d(n)) = 99 + 18 + 9 = 126 < 1000$

So expressing $n$ using it’s digits, $n = [abc] = 100a + 10b + c$,

We can see that the sum of 3 digits cannot exceed a 2 digit number, let

So the given equation will be,

Now we can be sure $a<9$ is not possible as even for $n = 899$, $n + d(n) + d(d(n)) = 899 + 26 + 8 = 933 < 1000$. So substituting $a=9$ ,

So we can be sure there exists no integers $b,c, x$ such that the above equation is satisfied.

I wrote a code in python to try and brute force the solution,

# To find n such that n + d(n) + d(d(n)) = 1000
def d(i):
sum = 0
for j in str(i):
sum = sum + int(j)
return(sum)

for i in range(900,1000):
print("\n\nThis is for "+str(i)+"\n")
print(i+d(i)+d(d(i)))

No such $n$ exists

1) 101000 in a circle (6 sectors). Add one to neighbouring numbers, can we get all numbers to be equal.
NO, but why…?

2) Sum of a set of integers is 1000, what’s the maximum possible product of these integers?
$3^{332}\times2^2$

3) Will the dragon die? ( -15, 9, -9 ) ( -24 +15), (-17, +2) , (-20 +11)
No

4) Smallest multiple of 9 with all even digits?
$288$

5) $n$ couples in a village, keep copulating until a boy is born, how does the boy:girl ratio change?
1:1

6) $k = 174\cdots174$ ( 16 times ) % 999 ( what’s k? )
786

7) $p(n) = n^2 - 10n -22 = x\times y$ where $n = 10x + y$
21

8) $n + d(n) + d(d(n)) = 1000$
No $n$ exists such as to satisfy this equation.

9) What’s the output of this program?

def f(n):
if(n>0):
print("hello")
print("world")


$n$ “hello” followed by $n+1$ “world”

10) Find the 100 largest numbers in a set of $10^9$ numbers?
heap ds

11) Find a set of 20 positive integers such that for all (maybe any?) subset of that set the sum of the elements in that subset is a perfect number?
??

12) There is a set containing $1, 2, \cdots, 199$, remove 2 numbers $a$ and $b$ at random from this set then add the number $(a+b+ab)$ to this set. Finally what number will be remaining?
$((n+1)!-1)$

13) How many 36 digit numbers exist which are not divisible by 100?
$9\times10^{35} - 9\times 10^{33}$

Written with StackEdit.