Interesting Questions

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 splAdd(a,b):
    return(tuple(map(operator.add, a, b)))

def move(n):
    if(sum(n)>10):
        if(n.count(n[0]) == len(n)):
            print("Hooray")
        return
    print(n)
    move(splAdd(n,(1,1,0,0,0,0)))
    move(splAdd(n,(0,1,1,0,0,0)))
    move(splAdd(n,(0,0,1,1,0,0)))
    move(splAdd(n,(0,0,0,1,1,0)))
    move(splAdd(n,(0,0,0,0,1,1)))
    move(splAdd(n,(1,0,0,0,0,1)))
    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
$$\Large x^{\frac{k}{x}}$$
is maximum. Note how $\frac{1000}{2} = 500$ and $\frac{1000}{8} = 125$.

$$\Large y = x^{\frac{k}{x}}$$
$$\large \ln y = \frac{k}{x}\ln x$$

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

$$\frac{1}{y} \frac{dy}{dx}= \frac{-k}{x^2}\ln x + \frac{k}{x^2}$$
$$\Large \frac{dy}{dx}= (x^{\frac{k}{x}}) \frac{k}{x^2}(1 - \ln x) = 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,

$$\Delta \text Heads = -9k_1 + -15k_2 + 9k_3$$

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

$$-9k_1 + -15k_2 + 9k_3 = -100$$
$$100 + 9(k_3 - k_1) = 15k_2$$
$(k_3 - k_1)$ will also be a integer, say $k_0$.
$$k_2= \frac{100}{15} + 9\frac{k_0}{15}$$

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,

$$n = n_k(10)^{k-1}+n_{k-1}(10)^{k-2}+ \cdots +n_2(10)^{1}+n_1(10)^{0}$$
$$n = [n_k(10^{k-1}-1)+ \cdots+n_1(10^{0}-1)] + (n_k + n_{k-1} + \cdots + n_2 + n_1)$$

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,

$$1\times 999 + 1 = 10^3$$
$$10\times 999 + 10 = 10^4$$
$$100\times 999 + 100 = 10^5$$
$$1001\times 999 + 1 = 10^6$$
$$10010\times 999 + 10 = 10^7$$

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,
$$n = 1(10)^{47}+7(10)^{46}+4(10)^{45} + \cdots + 4(10)^{3}+1(10)^{2}+7(10)^{1}+4(10)^{0}$$

We can’t separate any multiples of $999$ from the first $3$ digits, so let’s write,
$$p_1 = 1(10)^{2}+7(10)^{1}+4(10)^{0}$$

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

$$p_2 = 4(10^{45}-1) + \cdots+ 4(10^{6}-1) + 4(10^{3}-1) + (15\times4)$$
$$p_3 = 7(10^{46}-10) + \cdots+ 7(10^{7}-10) + 7(10^{4}-10) + (15\times70)$$
$$p_4 = 1(10^{47}-100) + \cdots+ 1(10^{8}-100) + 1(10^{5}-100)+ (15\times100)$$

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$.

$$n = p_1 + p_2 + p_3 + p_4$$
$$n \equiv (15\times4) + (43\times70) + (43\times100) + p_1\mod 999$$
$$n \equiv (16 \times 174) \equiv 786 \mod 999$$

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
$$a+b+ab = (a+1)(b+1) - 1$$

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
$$[((x_1+1)(x_2+1)-1), x_3, \cdots, x_n]$$
$$[((x_1+1)(x_2+1)-1+1)(x_3+1)-1, \cdots, x_n]$$
$$= [(x_1+1)(x_2+1)(x_3+1)-1, \cdots, x_n]$$
$$\cdots \ \ \cdots$$

So you get where this is going,
$$[(x_1+1)(x_2+1) \cdots (x_{n-1}+1)(x_n+1) -1]$$

The final term will be
$$\left [ \prod_{i=1}^n(x_i+1) \right ]-1$$

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,

$$\left [ \prod_{i=1}^n(i+1) \right ]-1 = (n+1)! - 1$$

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
$$a+b+c = [xy] = 10x + y$$

So the given equation will be,

$$n + d(n) + d(d(n)) = (100a + 10b + c) + (10x + y) + (x+y) = 1000$$
$$(100a + 10b + c) + 11x + 2(a+b+c - 10x) = 1000$$
$$102a + 12b + 3c - 9x = 1000$$

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$ ,

$$102\times 9 + 12b + 3c - 9x = 1000$$
$$3(4b+ c ) = 82 + 9x$$
$$(4b+ c ) = (\frac{82}{3} + 3x)$$
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)))

Final Answer:

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.