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.