Processing math: 61%

Wednesday, November 30, 2016

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=ab, 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 2500. 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 8125.

Even though we humans are naturally bad at grasping enormous numbers, We can write 8125 as 23125=2375 which is obviously less than 2500.

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 2500 is still not the answer. Let us divide k (a constant) evenly into kx pieces (each of size x). So we wish to maximize the product
xkx
is maximum. Note how 10002=500 and 10008=125.

y=xkx
lny=kxlnx

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

1ydydx=kx2lnx+kx2
dydx=(xkx)kx2(1lnx)=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×1<2×2.

In the case that k%3==2 then we should take k3 number of3’s and a single 2.

3332×22

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 (1120)=9 change in heads.

Say we do k1 number of move 1, k2 number of move 2, and k3 number of move 3. The net change is,

ΔHeads=9k1+15k2+9k3

We want to find integer values for k1,k2,k3 such that ΔHeads=100. Solving for it,

9k1+15k2+9k3=100
100+9(k3k1)=15k2
(k3k1) will also be a integer, say k0.
k2=10015+9k015

As a fraction plus a integer can never be a integer, so we can be sure there exists no integers k1,k2,k3 such that the above equation is satisfied.

The dragon can never be killed

Question 4

What is the remainder when you divide n=(174174) (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 nknk1n1 then,

n=nk(10)k1+nk1(10)k2++n2(10)1+n1(10)0
n=[nk(10k11)++n1(1001)]+(nk+nk1++n2+n1)

We know that (10n1) is always divisible by 9. So if (nk+nk1++n2+n1) is divisible by 9, the whole number is divisible by 9.

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

1×999+1=103
10×999+10=104
100×999+100=105
1001×999+1=106
10010×999+10=107

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++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,
p1=1(10)2+7(10)1+4(10)0

We can separate digits based on which power of 10 accompanies them - 103k,103k+1,103k+2.

p2=4(10451)++4(1061)+4(1031)+(15×4)
p3=7(104610)++7(10710)+7(10410)+(15×70)
p4=1(1047100)++1(108100)+1(105100)+(15×100)

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

n=p1+p2+p3+p4

We can do by hand and get the answer .

The remainder is 786

Question 5

There is a set containing , we proceed to continuously select (at random) numbers ( and ) then compute the number . We remove both and while we add to this set. Finally what will the final remaining number be?

Solution 5

Note that

So now the operation becomes “selecting (at random) numbers ( and ) then compute the number . We remove both and while we add to this set”.

So for , after the first operation it would become
which is same as . So on repeatedly applying this operation we get



So you get where this is going,

The final term will be

So for as given in the question means that the final term will be,

Question 8

Find n, where . is the digital sum of .

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

Solution 8

We know that So as all terms are positive, can be at max a digit number. Any larger than that and the sum will overshoot .

It can’t be a digit number either as even if is the largest digit number,

So expressing using it’s digits, ,

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 is not possible as even for , . So substituting ,




So we can be sure there exists no integers 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 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) Will the dragon die? ( -15, 9, -9 ) ( -24 +15), (-17, +2) , (-20 +11)
No

4) Smallest multiple of 9 with all even digits?

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

6) ( 16 times ) % 999 ( what’s k? )
786

7) where
21

8)
No 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")

“hello” followed by “world”

10) Find the 100 largest numbers in a set of 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 , remove 2 numbers and at random from this set then add the number to this set. Finally what number will be remaining?

13) How many 36 digit numbers exist which are not divisible by 100?

Written with StackEdit.