BR Maths Corner-1

[chetak]

First, if a person was born in 2001, the sum will be 11 and not 111 ...
But if a person was born in 19xx .. big deal? x+(111-x) is always 111.
(Next year this will be 112 .. and so on..)

Sorry all.

Suitably contrite.

[Najunamar]

Hi Amber G,
Regarding the Ramanujan note problem, here's something (I worked backwards and it looks too much like a madrassaa proof, wish it were more elegant)

2 = sqrt (4) = sqrt (1 + 3) = sqrt (1 + sqrt (9)) = sqrt (1 + sqrt (1 + 2*sqrt(16))) .....

Eachs successive attempt you get a sqrt (n^2) for increasing n, and since n^2 = 1 + n^2 -1 = 1 + (n-1)*(n+1), again use (n + 1) ^2 = 1 + (n+1-1)*(n+1+1), till you get requisite infinite series on right hand side.

********************************
OT: Funny anecdote,back during eye eye tea days, went for an exhibition on Ramanujan and saw a beautiful definite integral which I was able to solve with conformal mapping (fresh off Complex variable course) and felt good till all friends pointed out Ramanujan solved it using some other more elegant method, like cutting a mango with a sledgehammer!
***************************************

[Amber G.]

^^^ Hello.
If you remember, what was that integral? Just curious.

****
Wrt to the infinite continued sqrt() function...
Nice method ... but in the method you gave,unless you prove that it indeed converges to 2 the answer will be suspect.

You can always have a series with f(1) = 50(or any number instead of 2) and f(n+1) = ((f(n))^2-1)/n), and then say since sqrt(1+n f(n+1)) = f(n) so the answer is f(1) or 50 ( ) .... you can "prove" the expression to be any number you want..

(For example, we follow along the same lines as yours.. Taking 4 instead 2..)
4 = sqrt(16) = sqrt(1+15)
15 = sqrt( 1 + 2*112)
112 = sqrt( 1+ 3* 4181)
4181 = sqrt( 1+4*4370190)
.... and so on .,. to get result as 4)



BTW, Answer is indeed 2 (But the showing that the effect of the extra "(n+2)" in the last term indeed converges to zero requires some doing... that kind of stuff, IMO, was genius of Ramanujan's intuition...

[Amber G.]

^^ Standard definition means two angles which add up to 180 degrees.. (Not three or more)
http://mathworld.wolfram.com/SupplementaryAngles.html
(Or regular dictionary http://www.thefreedictionary.com/supplementary+angles)

[Vayutuvan]

As promised, here is a problem whose solution can be represented as a computer program (i.e. algorithm) very easily.

Given a number n and k, how many different k-dimensional boxes of volume n with integral sides can be got? Assume that the sides of the boxes are parallel to the coordinate axes.

[Amber G.]

Given a number n and k, how many different k-dimensional boxes of volume n with integral sides can be got? Assume that the sides of the boxes are parallel to the coordinate axes.

Hello,

Can you define the problem clearly please. What is a k-dimensional box? What is meant by integral side? What is a side?

Or by box, you mean, say for 2 dimensional, a rectangle of side a, and b, where n=ab, (which just means how many ways you can factor n)..( and for 3 dimensional space, how many ways you can write n as product of 3 factors?)?

[Vayutuvan]

Given a number n and k, how many different k-dimensional boxes of volume n with integral sides can be got? Assume that the sides of the boxes are parallel to the coordinate axes.

Hello,

Can you define the problem clearly please. What is a k-dimensional box? What is meant by integral side? What is a side?

Or by box, you mean, say for 2 dimensional, a rectangle of side a, and b, where n=ab, (which just means how many ways you can factor n)..( and for 3 dimensional space, how many ways you can write n as product of 3 factors?)?

Better term for 'side' probably is 'edge'. 'Integral' because we want to limit the length of the edge to be a member of the set of natural numbers.

Fundamental theorem of arithmetic - account for over-counting - if the n is a product of m < k numbers, k-m sides are of unit length

[Amber G.]

In my opinion, It does not matter much what you use, "side" or "edge", both are vague, unless you define what you mean by "volume", "box" etc.. in k-dimension..Also meaning of "different" (as in - is 1 x 3 box different than 3 x 1 box..In three dim lot of people will call a tall building "different" than a long building while criteria may be different for Lego blocks where one can easily rotate a block..).. FWIW, unless one knows the audience very well, at least in math, one should use a language which is more precise...

Can this problem be restated, such as :
How many ways a positive integer n, can be factored in k factors?
Or am I missing something? (Also, does order count here? - if not, one ought to restate that explicitly).
Thanks.

[Vayutuvan]

In my opinion, It does not matter much what you use, "side" or "edge", both are vague, unless you define what you mean by "volume", "box" etc.. in k-dimension..Also meaning of "different" (as in - is 1 x 3 box different than 3 x 1 box..In three dim lot of people will call a tall building "different" than a long building while criteria may be different for Lego blocks where one can easily rotate a block..).. FWIW, unless one knows the audience very well, at least in math, one should use a language which is more precise...

Can this problem be restated, such as :
How many ways a positive integer n, can be factored in k factors?
Or am I missing something? (Also, does order count here? - if not, one ought to restate that explicitly).
Thanks.

Amber Ji

Define your own "Different" and then give how ever many answers. In this case, for two definitions of "different", you have two different answers - one counting all isomorphisms and the other without. Iin the former, there is a distinguished ordering of the k-axes and in the second case the k-dimensions are anonymous. Vertex, edge and face have specific meaning in 3- or k- dimensions. k-box is also well defined (similar to n-cube) so is its volume. Using the natural definitions for the words would suffice to understand and solve the problem. I am essentially trying to get across the point that number theory and geometry are related and also the point as how to generate combinatorial objects.

Hint for others : Amber ji's answer is pretty close (for the first definition of "different"), but a sum is involved).

The answer is summation over 0 < i <= k (how many ways n can be factored into i factors). But this is over-counting because we want to eliminate symmetries.

[Amber G.]

There was an interesting problem posted here by AdityaS about 2 years ago:
http://forums.bharat-rakshak.com/viewto ... er#p647231
(See few messages below for discussion and details)..
Here, perhaps, a good math student, without calculator/computer will get the right answer while if, one uses brute force and computer without care, would get a wrong answer. ... (Crux of the fun was, unless one used very high precision .. rounding errors would give completely wrong answer)

This same theme has been commented on this dhaga many times.. even messages around 20th June (Brahmgupta's method to find squares which are also sum of first n natural numbers) talks about Fibonacci.

Here is a similar problem from a recent Math contest (HighSchool level) .. see if you can write computer program to get the correct answer.. or simple math can get you there too.

Given x(1) = 1 and x(2) = sqrt(1/3)
and x(n+2) = (x(n+1)+x(n))/(1- x(n)x(n+1)) (for all natural numbers n>0)


What is x(2011) ?

(For computers, it is straight forward iteration ...with, perhaps a slight challenge to represent sqrt(3) without introducing rounding errors... ..)

Hint (or may not be too much of a hint) : This was a multiple choice question... with 4 choices. so one had 25% chance..

[Vayutuvan]

^
OK. Tried some simple iterations to see if telescoping kind of trick can be applied. Hmm... could it be zero?

[ArmenT]

^^^
AmberG:

Code: Select all

#!/usr/bin/env python
# Note I'm using python 3. For python 2.xx users, you may need to remove the parens around the print statements.
from decimal import Decimal, getcontext

x = [0] * 2017
getcontext().prec = 1000
x[1] = Decimal('1')
x[2] = Decimal.sqrt(Decimal('1') / Decimal('3'))
for n in range(1, 2015):
    x[n + 2] = (x[n+1] + x[n]) / (Decimal(1) - x[n] * x[n+1])

# Print last few numbers
for n in range(2001, 2016):
    print(n, " => ", x[n])

# Print x[2011]
print(x[2011])

Numbers seem to cycle between a few numbers with every iteration, so it appears to be somehow connected to some kind of trig. function . Some I recognized as:
-sqrt(3), -1, -(2 + sqrt(3)), sqrt(3), 1, 1/sqrt(3), -1/sqrt(3) etc., but I confess that the one for x[2011] looked a bit unfamiliar to me:

Now I decided to google for the first few digits of x[2011] and discovered it was tan(165) (or tan(345). Suddenly, it occurred to me that a lot of those other x[n] were also numbers that were tan(some angle) (e.g. tan (30) = 1/sqrt(3), tan(45) = 1, tan(60) = sqrt(3) etc.). Sure enough, I checked some of the others and they all seem to have values corresponding to tan(angles_that_are_divisible_by_15). So my guess that it had a connection to a circular function was correct .

Suddenly, high school math came back to me:

tan(a + b) = (tan(a) + tan(b)) / (1 - tan(a) * tan(b))

This looks a heck of a lot like your formula, where x[n] = tan(a) and x[n+1] = tan(b) and x[n+2] = tan(a + b). Now the rest of it is pretty easy to figure out

[Amber G.]

^^^Nice! ( Also impressed by the ability of google to recognize tan(165 degrees)!
Yes, the values go some thing like (+ or - signs of) (1, sqrt(3), 1/sqrt(3), 2-sqrt(3) or 2+sqrt(3)) ... all are tangent of some multiple of 15 degrees..

If one wants to impress, and quote brahmgupta ...

(Some may l appreciate the beauty and say wow) ..

If a(n) = (15) (1/10) ((7sqrt(5)-5)(((1+sqrt(5))/2)^n - (7sqrt(5)+5)(((1-sqrt(5))/2)^n)

In spite of all those funny sqrt's etc... RHS will come out to be an integer (actually multiple of 15)

and it does look fairly simple .. It is 15 multiplied by ...
(1.06524758...)( 1.61803399)^n - (2.06524758..)(-0.61803399...)^n
(which will come out to be exact integer, if infinite decimals are used ... ..

x(n) is tan(a(n))

Why this is all so, please check out (wiki) Gopala Hemachandra numbers, or wiki vedic meter ( Sanskrit sholaka's meter) .. (Google "fibonacci numbers vedic meter" or something like that) ..

Hint: As said above, if x(n) = tan(u(n)) than u(n+2) = u(n+1)+u(n) .. just like Gopala Hemachandra numbers (or Fibonacci) discussed not too long ago ..if you take 15 degrees as unit, than u(1) =3*15 (tan of 45(degrees) = 1, and u(2) = 2 ..(tan 30(degrees) = 1/sqrt(3) the series will go 3,2,5,7,...and will repeat mod 12..


BTW, the problem (or close approximation of the problem) appeared in AMC (American Mathematical Contest), open to all US High school students. (About 500,000 students to take part in that)

[Vayutuvan]

^^^

tan(a + b) = (tan(a) + tan(b)) / (1 - tan(a) * tan(b))

This looks a heck of a lot like your formula, where x[n] = tan(a) and x[n+1] = tan(b) and x[n+2] = tan(a + b). Now the rest of it is pretty easy to figure out

Nice computer assited pattern recognition. This is how computers can help - similar to in Physics natural phenomenon obeserved/measured leading to theories or hypothesis by theoretical physicist-conducting a repeatable experiment-experimental Physicist gets a nobel prize for validating/invalidating the hypothesis-theoretical physicist might get a nobel prize cycle.

One successful example in Computer assisted Math is of course the 4CT. A good book is "Four Colors Suffice".

[Amber G.]

International Math Olympiad site, live streaming etc.. (Opening Ceremony is on July 17th)
https://www.imo2011.nl/live

[Amber G.]

Here is a problem from today's International Math Olympiad.
(There were 3 problems - 4.5 hours)

This seems an easy one . Wordings slightly changed so that general audience can understand. (Kids are not allowed to use computers, use of which can make it very easy for this audience..)

There are 4 numbers, all positive integers, and all distinct (no two are equal). Let there sum be S. Now you take a pair (two numbers) from these four and add them , if this sum divides S it is a "good pair". Choose the four numbers such that you can get maximum number of "good pairs" .

For example, if four numbers are (1,2,3,4) then only two pairs are good (1,4), (2,3). ( S=10, and both pairs has sum =5 and 5 divides 10)

You can improve on it, say (1,2,4,5).. now you have 3 good pairs..
(1,2),(2,4), (1,5) ..........

Can you have all six good pairs? Or 5? what is the maximum numbers of good pairs (and what are the corresponding 4 numbers?

Part II of contest is tomorrow.

[Amber G.]

^^^ Re-posting earlier message:
India IMO team for 2011 - Wish these boys and girl the best...
- Akashdeep (West Bengal)
- Akashnil(12th; West Bengal) (Was in 2010 IMO)
- Debdyuti Banerjee(or Chandan)(11th, West Bengal)
- Indraneel Kasmalkar(12th, Pune)
- Prafulla Sushil dhariwal(10th, Pune) (16 Year)
- Mrudul Thatte(10th, Pune) ( 15 year )
(US team looks fairly strong this year)

btw, the opening ceremony can be seen here: clicky
(Around 58 minutes into it - between 58-59 minute - is Indian team)

[Amber G.]

I see no comments on the problem I posted from this IMO.. (It is relatively easy and I am told all (or most) of the Indian Kids solved it in the heat of the battle...

Official Results are not out yet, so you have to wait for the news stories for a few days but from the partial results , I am pretty sure that..

Akashnil Dutta is may get a Gold. (Most successful Indian student with 1 gold and previous 2 silvers)... Congrats!


(Also Akasdeep ,Mrudul and Debdyuti,, have a chance for silver)

Akashnil is one of a few students who solved Problem #2 (A weird (in my opinion) "geometry" problem which looked easy but most were unable to solve it in the exam.

The problem #2 is interesting enough to be chosen as a polymath project this year:
http://michaelnielsen.org/polymath1/ind ... e=Imo_2011

Edited Later: I was advised, that it is wise to hold on till all the scores are in (!). Final Jury Meeting is tomorrow. Full raw scores are in, but cut-off points for medals are to be decided. Akashnil now hangs (from what one may think) between silver and gold.
Indian team as a whole did pretty well. Most likely 2B, 3S 1G or 2B 4S or 3B 3S or something like that once cut-off points are decided.

[gakakkad]

I ll try to post the solution by today evening. Please do not post the solution's .

[Amber G.]

I thought I will post another problem from this IMO which is relatively easy (virtually every one got it) and may be interesting to some. Using a computer (to see the pattern) will make the problem really trivial so unless you want to don't use a computer..
(A good high school student should be able to solve it given enough time)

Here is the problem (slightly modified to make is understandable) (Problem comes from Iran)

There are n weights. Their values are (1,2,4,8,....2^(n-1)). You are also given a balance. You are to place each of the weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step you choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.
Determine the number of ways in which this can be done.

[ArmenT]

^^^^
(n-2)! + 1 for n > 1 and 1 when n=1?

[Amber G.]

^^^
When n=2, answer is 3, (If you first put '1' (has to be on left), '2' has to be on left, but if you first put '2' on left, now 1 can be on placed on either side -- total 3 ways)

[gakakkad]

AMBER SIR, heres solution for first one. h&d blows to us apduls when high school kids do these more efficiently than us But its true . I was far better when I was in school than now. Maybe because I took up medicine. But i try to keep my maths alive.

there are only 4 good pairs possible. Let {a1,a2,a3,a4} be a set . Substitute a1=1,a2,=f-1,a3=v-1,a4=e-1 where we assume that these are edge sides and vertices of a regular polyhedron without holes (platonic solid) , let G= A1+A2+A3+A4. detailed solution as soon as i have access to scanner. feeling lazy to type , But briefly G = V+E+F -2. nOW EULARS formula is v-e+f=2 adding 2e to both sides of eulars formula .we get g=2e. Now a1+a2=f. , a1+a3=v ,for a solid pf=2e=qv where p = the number of edges of each face,q = the number of faces meeting at each vertex but g=2e ,ergo (a1+a2)|g ,(a1+a3)|g. a1+a4 = e which obviosly is divisible by 2e, a3+a4 can easily be proved to be not divisible,a2+a3=e. so we have four possible good pairs. {1,5,7,11} is one pair a1+a2 , a1+a3 etc are divisible but a3+a4 are not. other pair is {1,11,19,29}which is similar divisibility prop to previous one. QED

[ArmenT]

^^^
When n=2, answer is 3, (If you first put '1' (has to be on left), '2' has to be on left, but if you first put '2' on left, now 1 can be on placed on either side -- total 3 ways)

Ah, I see. I was counting 1 & 2 on the left pan as the same as 2 & 1 on the left pan, in which case my formula works out.
Whoops, also screwed my logic a bit. I noticed the weights were from (1, 2, 4...2^(n-1) and I went off-by-one on the factorial bit. Should have been (n-1)! + 1
In case you're wondering about my reasoning, I worked like this:
1. Once n'th weight is on the left pan, remaining (n - 1) weights can be placed in any combination on either the right or left pan (it doesn't matter where they go, since their total can never exceed 2^(n - 1).
2. Ergo this means that the remaining (n-1) weights can be arranged in (n-1)! ways (assuming that order doesn't matter and there's at least one weight on the right pan)
3. We also have the case where all weights are on the left pan. Therefore we add 1 more to the answer.
4. Hence (n-1)! + 1.

[Amber G.]

Congratulations to India's IMO team:
Akashnil Dutta - Gold medal (He won silver in 2010 and also in 2009)
Akashdeep Dey - Silver medal
Debdyuti Banerjee Bronze medal (Missed a silver by a whisker)
Mrudul Thatte Bronze medal
Prafulla Dhariwal Honourable mention (Missed a Bronze by a whisker!)
Indraneel Kasmalkar Honourable mention (Also Missed a Bronze by a whisker)

(I was relieved and was very glad to see that Akashnil won the gold, as my earlier post was based on partial results.. Just to see how close it was..

Raw scores were Akashnil (28), Akashdeep (22) Debdyuti (21), Mrudul (18) and Prafulla and Indraneel (both 15) ..Cut off for Gold was 28 (!), For Silver 22 and for Bronze 16

I am also glad that USA team also did very well (6 gold medals)

Also in the hall of fame was a German girl, Lisa Sauermann for getting the only perfect score in this IMO.(This will be her 4th Gold)

Here is the (un)official ranking .. (There is no official ranking of the countries just individual medals)

1. China
2. USA
3. Singapore (This was a surprise - but the team was good)
4. Russia
5. Thailand
6. Turkey
7. North Korea (This team was kicked out in last IMO due to cheating - a charge many (members of the jury) now feel was plain wrong - so this was nice)
8. Taiwan
8. Romania
10. Iran

India was at 23rd (Still about 10 higher than 2010)..

[Amber G.]

^^^
When n=2, answer is 3, (If you first put '1' (has to be on left), '2' has to be on left, but if you first put '2' on left, now 1 can be on placed on either side -- total 3 ways)

Ah, I see. I was counting 1 & 2 on the left pan as the same as 2 & 1 on the left pan, in which case my formula works out.
Whoops, also screwed my logic a bit. I noticed the weights were from (1, 2, 4...2^(n-1) and I went off-by-one on the factorial bit. Should have been (n-1)! + 1
In case you're wondering about my reasoning, I worked like this:
1. Once n'th weight is on the left pan, remaining (n - 1) weights can be placed in any combination on either the right or left pan (it doesn't matter where they go, since their total can never exceed 2^(n - 1).
2. Ergo this means that the remaining (n-1) weights can be arranged in (n-1)! ways (assuming that order doesn't matter and there's at least one weight on the right pan)
3. We also have the case where all weights are on the left pan. Therefore we add 1 more to the answer.
4. Hence (n-1)! + 1.

ArmenT: Thanks but I think the answer is still incorrect. Hint for n=1, answer is 2, n=2, answer is 3 (not 2) Remember, that order does matter. For example, in case of n=3 (weights 1,2,4) if you start with '4' (which has to be placed on left) ..there are still 8 ways you can put the rest (1, and 2) (1(L)2(L), 1(L),2(R),1(R)2(L), 1(R),2(R) and 4 more when you start putting 2 first then 1 )

[Amber G.]

AMBER SIR, heres solution for first one. h&d blows to us apduls when high school kids do these more efficiently than us But its true . I was far better when I was in school than now. Maybe because I took up medicine. But i try to keep my maths alive.

there are only 4 good pairs possible. Let {a1,a2,a3,a4} be a set . Substitute a1=1,a2,=f-1,a3=v-1,a4=e-1 where we assume that these are edge sides and vertices of a regular polyhedron without holes (platonic solid) , let G= A1+A2+A3+A4. detailed solution as soon as i have access to scanner. feeling lazy to type , But briefly G = V+E+F -2. nOW EULARS formula is v-e+f=2 adding 2e to both sides of eulars formula .we get g=2e. Now a1+a2=f. , a1+a3=v ,for a solid pf=2e=qv where p = the number of edges of each face,q = the number of faces meeting at each vertex but g=2e ,ergo (a1+a2)|g ,(a1+a3)|g. a1+a4 = e which obviosly is divisible by 2e, a3+a4 can easily be proved to be not divisible,a2+a3=e. so we have four possible good pairs. {1,5,7,11} is one pair a1+a2 , a1+a3 etc are divisible but a3+a4 are not. other pair is {1,11,19,29}which is similar divisibility prop to previous one. QED

Brilliant!
The problem came (proposed by) from Mexico and I suspect not too many would have made its relationship with platonic solids. The sum(s) (6,8,12) (From {1,5,7,11}) are indeed (faces, corners, lines) related to a cube (or its dual Octahedron) and (12,20,30) (from {1,11,19,29}) are related to Dodecahedron (12 faces, 20 corners, 30 lines).. The Tetrahedron (4,4,6) which is self dual gives {1,3,3,5} where all the numbers are not distinct.

Of course, the answer would be {k,5k,7k,11k}and {k,11k,19k,29k} where k is an integer
and each would have 4 "good pairs".

[gakakkad]

^^^ In physics our rank must be second or third. AFAIK they do not maintain country tally. We always do best at physics. Because of Indian love for Irodov's problem book .If IMO had calculus in syllabus we would have always won . Wish number theory would be included in the Indian syllabus.

This sounds Childishly nationalistic . But I feel China sends college grads for this contest .

Will try to do the next one in a day or two.

[Amber G.]

Here is a problem from today's International Math Olympiad.
(There were 3 problems - 4.5 hours)
...
There are 4 numbers, all positive integers, and all distinct (no two are equal). Let there sum be S. Now you take a pair (two numbers) from these four and add them , if this sum divides S it is a "good pair". Choose the four numbers such that you can get maximum number of "good pairs" .
<snip>
.

Here is one solution.. Stop reading further, if you are working on it.

Let the numbers be a<b<c<d with a+b+c+d = S
(Pairs are (a+b), (a+c), (a+d), (b+c), (b+d), (c+d) )

>> c+d > a+b ==> c+d >S/2 so it can not divide S
>> Similarly b+d>a+c ==> b+d can not divide S too.
(So at the most we can have 4 "good" pairs)
To have 4 good pairs, we have to have a+d = b+c
(If they are not equal, larger one will be greater than S/2 and will not divide S)
Since, c>b and b+c = S/2 ; c> S/4 and so a+c > S/4
and b+c > a+c so a+c < S/2
Only way it can divide S is when it is S/3. so a+c =S/3
Now d-c = (which is equal to b-a because a+d=b+c) = (d+a) - (c+a) = S/2-S/3 = S/6
.
so b-a = S/6 (which one can also write as b = a+S/6)
(so b+a > S/6)
and a+b <S/3 (because a+c is s/3)
Only possible values of (a+b) are S/4 and S/5 !!
Rest is simple.. (We already have b = S/6+a, c = S/3-a. and d = S/2-a)
and a+b = a+(a+S/6)=2a+S/6

Case 1: when a+b = S/4
2a+S/6=S/4 which gives S=24a and
the numbers are (a,5a,7a,11a)

Case 2: when a+b=2a+S/6= S/5 we get S=60a and
the numbers (a,11a,19a,29a)
(These are the only solutions .. where there are 4 'good pairs' )

Fairly simple if one gets started in the right direction...
(Edited to remove some typo's)

[gakakkad]

^^ wow thats elegant and simple.

[Amber G.]

^^^
ArmenT etc .. - WRT the weights problem, counting for smaller numbers, (or with the help of a computer, even for not so smaller)can give few values..see if one can see a pattern.
(For one answer is 1, for 2 weights, answer is 3 )... Curious thing is, in one way one of the problems on page 1 of this BRF thread has something in common with this problem. !

One of my friend (actually my son's ex-classmate) was leader (official coach of the team) of one of the nation's team... interesting how time flies...not so long ago he was participating in IMO. (He went to college in US)

[svenkat]

The following are CAT(MBA giri) questions.But I find them sufficiently interesting to post them here.

Re: Alok and Bhanu play the following min-max game. Given the expression N = 9 + X + Y - Z Where X, Y and Z are variables representing single digits (0 to 9), Alok would like to maximize N while Bhanu would like to minimize it. Towards this end, Alok chooses a single digit number and Bhanu substitutes this for a variable of her choice (X, Y or Z). Alok then chooses the next value and Bhanu, the variable to substitute the value. Finally Alok proposes the value for the remaining variable. Assuming both play to their optimal strategies, the value of N at the end of the game would be one of the following 27, 0.0 ,20 ,18

Same problem with N = 12 + X*(Y - Z)

2)1! + 2! +... + 50!=?
a)3.1035*10^64 b)2.1021*10^65 c)3.1035*10^63 d)3.1035*10^62

[Amber G.]

2)1! + 2! +... + 50!=?
a)3.1035*10^64 b)2.1021*10^65 c)3.1035*10^63 d)3.1035*10^62

The answer is none. a) The answer is close to 3.1035..*10^64
(Even without a calculator, it is easy to rule out b), c) and d) as 50! is about 3*10^64 and c) and d) are much smaller, and b) is much bigger, as the sum would be about 2% more than of 50!)
(To get first few significant digits, you only have to sum 50!+49! (or may be additional 48!) see >here <

[Amber G.]

The following are CAT(MBA giri) questions.But I find them sufficiently interesting to post them here.

Re: Alok and Bhanu play the following min-max game. Given the expression N = 9 + X + Y - Z Where X, Y and Z are variables representing single digits (0 to 9), Alok would like to maximize N while Bhanu would like to minimize it. Towards this end, Alok chooses a single digit number and Bhanu substitutes this for a variable of her choice (X, Y or Z). Alok then chooses the next value and Bhanu, the variable to substitute the value. Finally Alok proposes the value for the remaining variable. Assuming both play to their optimal strategies, the value of N at the end of the game would be one of the following 27, 0.0 ,20 ,18

Same problem with N = 12 + X*(Y - Z)

Again, with multiple choice, one can easily rule out 27, or 0. 18 is easily reachable (select 9,9,9). So to reach 20 is trivial. ( Alok chooses 7, if it is Z one can easily add 18 and reaches 20. If it is X, then select 5(4 will work too), so net gain could be (9-5) or more than 5.. In either case you can reach 20.

For the next one, unless I am missing something trivial, the answer seems to be 30)

[skumar]

A ticket for the cinema costs Rs 1 (well it's an old problem when ticket did cost 1 Rs), There are n people in the line, each person has either Rs1 note(bill) of Rs 2 note, the cashier has no chance when he opened the window, how many ways these people have the notes so that cashier will not run out of change) .(For example for n=3, (1,1,1) is ok so is (1,2,1) but nothing else - 2,1,1 is not possible because for the first person cashier can't give change)

Going through archives to find one unsolved problem I could solve .


f(n) = 1 for n = 1
f(n) = 2 * f(n-1) if n is even
f(n) = 2 * f(n-1) * n / (n+1) if n is odd

For n = 1, only (1) works off course. Going further iteratively, all combinations where the difference between the number of 1s and 2s till that point is >= 0 are legal. Hence, in case of even n, you can add a 1 or 2 to the previous iteration since the difference in the previous iteration will always be at least 1. In case of odd n, you need to eliminate combinations where the difference between the 1s and 2s at that point is 0 e.g.
for n = 2, (1,1) and (1,2) work.
for n = 3,
you could add a 1 or a 2 to (1,1) to get (1,1,1) and (1,1,2)
but you can only add a 1 to (1,2) to get (1,2,1)


It also highlights one error in example given, for n=3, (1,1,1), (1,2,1) & (1,1,2) are ok.

[skumar]

^^^
When n=2, answer is 3, (If you first put '1' (has to be on left), '2' has to be on left, but if you first put '2' on left, now 1 can be on placed on either side -- total 3 ways)

Ah, I see. I was counting 1 & 2 on the left pan as the same as 2 & 1 on the left pan, in which case my formula works out.
Whoops, also screwed my logic a bit. I noticed the weights were from (1, 2, 4...2^(n-1) and I went off-by-one on the factorial bit. Should have been (n-1)! + 1
In case you're wondering about my reasoning, I worked like this:
1. Once n'th weight is on the left pan, remaining (n - 1) weights can be placed in any combination on either the right or left pan (it doesn't matter where they go, since their total can never exceed 2^(n - 1).
2. Ergo this means that the remaining (n-1) weights can be arranged in (n-1)! ways (assuming that order doesn't matter and there's at least one weight on the right pan)
3. We also have the case where all weights are on the left pan. Therefore we add 1 more to the answer.
4. Hence (n-1)! + 1.

If order does not matter, it should be 2^(n-1), not (n-1)! + 1. But since order matters ...

[skumar]

If order does not matter, it should be 2^(n-1), not (n-1)! + 1. But since order matters ...

If order matters ....



f(1) = 1
f(n) = (2 * n - 1) * f(n-1)
no idea why! waiting for Amber G to enlighten

Edited later -
learnt about double factorial, so f(n) = (2n-1)!! = (2n)! / (n!)(2^n)


Do the kids get points for finding the solution without knowing how to get there?

[vishvak]

Do the kids get points for finding the solution without knowing how to get there?

Only if scans of 'rough sheets' are not archived. Just joking!

[Amber G.]

<snip above post >
It also highlights one error in example given, for n=3, (1,1,1), (1,2,1) & (1,1,2) are ok.

Thanks, yes I was sloppy . (1,1,2) is ok.
The recursive relationship you gave above, for even n seems to be okay but, I believe, not for odd n.
(Try n=7 to see what I mean)

[Amber G.]

learnt about double factorial, so f(n) = (2n-1)!! = (2n)! / (n!)(2^n)

Do the kids get points for finding the solution without knowing how to get there?

If one gets on the right track, answer is quite simple...

Key is: Given n weights, the answer is same, irrespective of the individual value of each of those n weights .. (as long as they are of the form 2^n)

(For example, if you are given three weights.. the answer for the number of ways remains the same if the weights were (1,2,4) or (1,4,32), or (2,8,16)..(A moments thought will make this obvious)

Rest is simple, if F(n-1) is the number of ways for (n-1) weights, the last weight to be placed (n possibilities - it can have any of the n values ) can go on either side, except when it the heaviest weight, (In that case it can go only on one side)... so there are (2n-1) ways.
So F(n) = (2n-1)* F(n-1)
= (2n-1)*(2n-3)*F(n-2)
= (2n-1)*(2n-3)*(2n-5)..... 5*3*F(1) ....(and we know that F(1)=1)
which gives F(n) = (2n-1)!!
(The values go as 1, 3, 3*5=15, 75, ....)
(2n-1)!! = 1*3*5*....(2n-1)