Volume III

Q3.1: Find sum of the following series: 1/(1^2)+1/(2^2)+1/(3^2)+...

A3.1: Expanding sin(x) into Taylor series yields sin(x)=x-(x^3)/3!+(x^5)/5!-(x^7)/7!+...

Alternatively we can expand sin(x) as a polynomial of infinite degree,

sin(x)=x*(x^2-Pi^2)*(x^2-4*Pi^2)*(x^2-9*Pi^2)*..., which has the following roots:

+/-0*Pi, +/-1*Pi, +/-2*Pi, +/-3*Pi, ... Rewriting last expansion as sin(x)/x=

=C*(1-(x/Pi)^2)*(1-(x/(2*Pi))^2)*(1-(x/(3*Pi))^2)*... and noting that since

lim[x->0](sin(x)/x)=1, C=1 we have the equality: sin(x)=x*(1-(x/Pi)^2)*

*(1-(x/(2*Pi))^2)*(1-(x/(3*Pi))^2)*...=x-(x^3)/3!+(x^5)/5!-(x^7)/7!+...

Opening brackets and aggregating all members of x^3 degree gives us the following

equality: -(x^3)/(pi^2)-(x^3)/((2*Pi)^2)-(x^3)/((3*pi)^2)=-(x^3)/3!, simplifying last

expression gives us the formula for finding of sum of square reciprocals:

1/(1^2)+1/(2^2)+1/(3^2)+...=(Pi^2)/3!=(Pi^2)/6.

Q3.2: Prove that present value of n-coupon period floating leg with $1 notional priced

at par (accrual rates equal to discount factors for the corresponding periods) equals to $1.

A3.2: Present value of $1 notional n-coupon floating leg equals to: pv =

= r1/(1+r1) + r2/((1+r1) * (1+r2)) + ... + rn/((1+r1) * (1+r2) * ... * (rn +1)) +

+ 1/((1 + r1) * (1 + r2) * ... * (rn + 1)) =

= ((1 + rn) + sum(i=1, n-1)(ri * prod(j=i, n-1)(1 + rj+1))) /

/ prod(j=1, n)(1 + rj) = (1 + rn) * (1 + rn-1 + sum(i=1, n-2)(ri *

* prod(j=i, n-2)(1 + rj+1))) / ((1 + rn) * prod(j=1, n-1)(1 + rj+1)) =

=((1 + rn) * (1 + rn-1) * ... * (1 + r1)) / ((1 + rn) * (1 + rn-1) * ... * (1 + r1)) = 1.

We can also write the following equality (1 + r1) * (1 + r3) * ... * (1 + rn) = (1 + y) ^ n,

where we replace r1, r2, ..., rn variables with a single variable y, then: pv =

= (sum(i = 1, n-1)(y * ((1 + y) ^ n) / ((1 + y) ^ i)) + (1 + y)) / ((1 + y) ^ n) =

= sum(i = 1, n-1)(y / ((1 + y) ^ i)) + 1 / ((1 + y) ^ (n - 1)) = y * ((1 - 1 /

/ (1 + y) ^ n) / (1 - 1 / (1 + y)) - 1) + 1 / ((1 + y) ^ (n - 1)) =

= y * (1 - 1 / ((1 + y) ^ n) - y / (1 + y)) / (y / (1 + y)) + 1 / ((1 + y) ^ (n - 1)) =

= 1 + y - 1 / ((1 + y) ^ (n - 1)) - y + 1 / ((1 + y) ^ (n - 1)) = 1.

Q3.3: You are on deserted island, looking for hidden treasure. Island has only 2 trees oak

and pine. According to treasure map first you need to locate gallows, then walk to the oak

counting your steps, from oak you need to turn 90 degrees right and walk the same number

of steps. Then put stick in the soild marking this spot and return to gallows. From gallows

walk to pine tree also counting steps. From pine tree make left 90 degree turn and walk

the same number of steps as you walked from gallows to pine tree. From this spot go to half

distance to the stick and dig out the treasure. There's only one problem with this map:

Gallows was destroyed by weather so you cannot locate them. However you are able to locate

oak and pine trees. How to find the treasure? (Gammow's problem.)

A3.3: Lets apply complex coordinate system to our map in a way that both oak and pine lie

on real line (ax) with respective coordinates o=-1+0*i and p=1+0*i. Let's also assume

that gallows located at: g=a+b*i. Now if oak location was origin point, then:

og = (a+1) + b * i, turning this vector +90 degrees we have i*og = i*(a+1)-b = fs, where fs

is a coordinate of first stick put into the soil. if pine location was an origin point then

pg = (a - 1) + i * b. Turing this vector -90 degrees yields -i*pg = i*(1-a)+b = ss, where

ss is a coordinate of second stick put into the soil. Now treasure is burried in the middle

point between first and second stick coordinates. So treasure is located at t = (fs+ss)/2=

= (i*(a+1)-b+i*(1-a)+b)/2 = (i*a+i-b+i-i*a+b)/2 = 2*i/2 = i.

Q3.4 What is greater pi^e or e^pi?

A3.4: Right down inequality as pi^e ? e^pi, then transform it to e ? pi / ln(pi), then let's

rewrite it as e ? f(pi), where f(pi) = f(x = pi) = x / ln(x). Now let's find a minima:

f'(x) = 1/ln(x) - x / (ln(x))^2 / x = 1/ln(x) - 1/(ln(x))^2 = 0. It's easy to see that

f'(e) = 0. We just need to show that found extrema is minima: f''(x) = -1/(ln(x))^2/x +

+ 2/(ln(x)^3)/x. Now f''(e) = -1/e + 2/e = 1/e > 0, so x=e is minima and e < pi / ln(pi), so

pi^e < e^pi.

Q3.5: Using binary [0,1] uniform RND input generate uniformly distributed integer numbers

from 0 to N-1.

A3.5: Find closest integer k, such that 2^(k-1) < N <= 2^k. Sample k binary readings or bits

together so they will represent an integer number from 0 to N-1. Then in case if N = 2^k no

further processing is necessary and resulted number can be printed directly to output. But in

case if N < 2^k, then all integers i that are (N-1) < i < 2^k should be discarded and

((counter++) % N) value should be printed instead where counter = 0 initially and counter

variable is incremented with every successful binary random number generation.

Q3.6: You have 2 cubes, oce numbers on cube faces in a way to display any day in any given

month (e.g. 01,...,31).

A3.6: Numbers 0,1,2 should be displayed on both cubes, this leaves us with 6 vacant faces for

remaining 7 numbers: 3,4,5,6,7,8,9. This implies that we have to squeeze 2 numbers into one face.

6 and 9 are perfect candidates for this on a condition that we're not restricted to place cubes

upside down. So first cube gets 0,1,2,3,4,5 and second 0,1,2,6,7,8.

Q3.7: There's a row of 10 room and a treasure which is hidden in one of them.

Each night, a ghost moves the treasure to an adjacent room. You're trying to

find the treasure, but can only check one room per day. How do you find it?

A3.7: Initially looks scary right? But here is the important keyword: ADJACENT.

So, ghost can't just hop to a random room every night hiding the treasure in an

arbitrary room. First lets label rooms 1 through 10 and denote Tk as room where

treasure is on day k. Also denote Ck as room you check on day k. Then we will

need at most 16 days to find the treasure. How? Well, let's check the rooms Ck =

k + 1 on days k = 1, 2, ..., 8 and rooms Ck = 18 - k on days k = 9, 10, ..., 16.

Proof:

If T1 is even, then we will find the treasure in one of the first 8 days. In

other words, there exists k with 1 <= k <= 8 such that Tk = Ck. Note that Tk and

Ck have the same parity (e.g. first day they are both even, second day they are

both odd). Since T1 is even and C1 = 2, and both Tk and Ck change by at most 1

from day to day. Hence Tk - Ck is also even. Moreover T1 <> 1 (it has to be even

on first day) and T8 <> 10 (it's has to be odd on 8th day if it's even on first)

. If T1 > 1 and C1 = 2, then T1 - C1 >=0. In addition, if T8 < 10 and C8 = 9,

then T8 - C8 <= 0. If ghost moves in the same direction with us, then (T[k] -

C[k]) - (T[k-1] - C[k - 1]) = 0. If ghost moves in opposite direction (i.e.

towards us), then (T[k] - C[k]) - (T[k-1] - C[k - 1]) = -2. But since both ghost

and us started from even positions the difference between ghost's and our

position will be always even and therefore multiple to 2 for first 8 days. Hence

there exists some k, 1 <= k <= 8, such that Tk - Ck = 0 or Tk = Ck.

Alternatively if T1 is odd, we will find the treasure on some day k, 9 <= k <=

16. Note that since T1 is odd then T9 has to be odd too as adding even number (9

- 1 = 8) to an odd number (1) will produce odd number (1 + 8 = 9). Also Tk and

Ck will have the same parity i.e. they will be either both even or both odd.

Since T9 is odd, T9 < 10 and as 16 - 9 = 7 is odd, T16 should be even (as odd +

odd = even) and hence T16 > 1. Moreover Tk - Ck is always even and hence

multiple to 2 for any k, 9 <= k <= 16. As in the even case (T[k] - C[k]) -

(T[k-1] - C[k - 1]) = 0 if we move in the same direction with treasure or (T[k]

- C[k]) - (T[k-1] - C[k - 1]) = -2 if we move in the opposite directions. Hence

T9 - C9 <= 0, but T16 - C16 >= 0, from here it's easy to see that there's some k

, 9 <= k <= 16 such that Tk - Ck = 0 and Tk = Ck.

In general we will need to perform (n - 2) + (n - 2) = 2 * (n - 2) = 2 * n - 4

checks to find treasure in n adjacent rooms. We never should bother with

checking of first or last room, as ghost cannot leave treasure in the same room

for more than 1 night and can move treasure to an adjacent room only.