BR Maths Corner-1

The Technology & Economic Forum is a venue to discuss issues pertaining to Technological and Economic developments in India. We request members to kindly stay within the mandate of this forum and keep their exchanges of views, on a civilised level, however vehemently any disagreement may be felt. All feedback regarding forum usage may be sent to the moderators using the Feedback Form or by clicking the Report Post Icon in any objectionable post for proper action. Please note that the views expressed by the Members and Moderators on these discussion boards are that of the individuals only and do not reflect the official policy or view of the Bharat-Rakshak.com Website. Copyright Violation is strictly prohibited and may result in revocation of your posting rights - please read the FAQ for full details. Users must also abide by the Forum Guidelines at all times.
SK Mody
BRFite
Posts: 251
Joined: 15 Mar 2002 12:31

Re: BR Maths Corner-1

Postby SK Mody » 28 Aug 2008 21:44

Amber G wrote:You can, perhaps simplify it a little, just take two numbers with the same 'r' - as you proceeded to do, and subtract. the closest two .. that you will get 999... followed by 0's .


Certainly makes it a lot shorter. By the way, using the same idea, it is not difficult to show that given any two digits d and e, there is a multiple that contains only those two digits.

Regarding the kabootar-pinjra principle :mrgreen: it is interesting that both solutions use it.

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 28 Aug 2008 23:29

given any two digits d and e, there is a multiple that contains only those two digits.

May be there is a little typo but ..Just to be a little careful :) if the given digits are, say 2 and 3, you can not find a multiple of 10 which uses just these two digits. :)

Here is a solution of factors of (2^58+1)

Look it as 4*x^4+1 where x=2^14, and of course,
4 *x^4 + 1 = 4*x^4+4*x^2+1-4*x^2 = (2*x^2+1)^2-(2x)^2
=(2x^2+2x+1)(2x^2-2x+1)

so these two factors are (2^29+2^15+1) and (2^29-2^15+1)

Of course, it is easy to see 5 is also a factor (4^29+1 has a factor 4+1). and 2 x^2-2x+1 here is a multiple of 5.

Any number like 2^n+1 where n is of the form 4k+2 is a fair game. :)

SK Mody
BRFite
Posts: 251
Joined: 15 Mar 2002 12:31

Re: BR Maths Corner-1

Postby SK Mody » 29 Aug 2008 01:01

Ah yes, forgot about the zeros. Can't do without them. :)

Vriksh
BRFite
Posts: 406
Joined: 27 Apr 2003 11:31

Re: BR Maths Corner-1

Postby Vriksh » 29 Aug 2008 07:39

Any Gurus out here working on Percolation thresholds in networks?

http://en.wikipedia.org/wiki/Percolate

Such as Bond or Site or Resistance, conductance or even the so called Rigidity percolation. What bother me the most is significance of the percolation threshold and the percolation exponent.

Nandu
BRF Oldie
Posts: 2195
Joined: 08 Jan 2002 12:31

Re: BR Maths Corner-1

Postby Nandu » 30 Aug 2008 00:41

Amber G., you mentioned that the Cow/Buffalo problem is from old Hindu sources. What about the Ankan problem? What is its source?

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 30 Aug 2008 08:09

Nandu - Ankan problem is original. The theme is, I am sure, of course, have been used quite often (in fact many times in IMO/InMO/USAMO contests) in similar problems based on Fermat's little/Euler's theorem (a^(phi(n))==1 mod n).. for particular case of 10).. Basically it means if n is prime to 10 (that is, n is not divisible by 2 or 5) then (10^(phi(n)) -1) is divisible by n. One could have used this method but kabootar kabbotar method is neat too.

(Note that, if n is not divisible by 2 or 5, it was possible to achieve aknkan of 1)

Fermat's little theorem is one of my favorite as it is quite beautiful, easy to prove (does not require high math) yet very few young students know it.(Math highs chool/college text books generally do not teach it)

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 30 Aug 2008 19:22

Folks, FWIW:

If anyone enjoyed the math problems I posted here, or anyone (bright middle/high school students in USA or India) you know who enjoys math, I would urge them to check out the two options listed below. These opportunities are open to every student in India (or USA) as long as they have e-mail or postal mail and willing school teacher/parent to guide/mentor. If a student does very well, (s)he has fun, gets some national/international reorganization.

Option 1 - AMC/AIME/USAMO ( or their Indian InMO etc equivalent)
For details see, say: FAQ:
http://www.unl.edu/amc/f-miscellaneous/faq.shtml
The AMC tests are available worldwide and are a big part of shared experience of young math-interested people around the world. Participation can be entirely by postal mail and is growing in the US as well as in countries of Asia and Europe. Any student in any registered school who meets the age/grade restrictions for the AMC8, AMC10 and AMC12 may take them. The AIME is by invitation to the top 1% of scorers on the AMC10 and the top 5% of scorers on the AMC12. …The only requirement for participation is registration.
[The USAMO is restricted to students attending school in the United States or Canada and citizens the United States living abroad…but InMO is there ]


Another, one is usamts (It used to be run by NSA and had Imts (International Math Talent Search) component too). Basically one gets a set of 5 problems, you have one month to work (You can use books/computer/internet etc .. but can not take another human’s help – It runs on honor system – and you can qualify/invited for AIME etc if you do well) See Link usamts.org for details (First problem set of this year, is already there, one can check it out on the site given - but please do not discuss those problems here as the contest is still open till Oct 18)

(Schools like MIT asks AMC/AIME scores in their applications, and good scores are quite helpful )

ArmenT
BR Mainsite Crew
Posts: 4239
Joined: 10 Sep 2007 05:57
Location: Loud, Proud, Ugly American

Re: BR Maths Corner-1

Postby ArmenT » 31 Aug 2008 02:48


Rupesh
BRFite
Posts: 870
Joined: 05 Jul 2008 19:14
Location: Somewhere in South Central India

Re: BR Maths Corner-1

Postby Rupesh » 02 Sep 2008 12:22

1 x 8 + 1 = 9
12 x 8 + 2 = 98
123 x 8 + 3 = 987
1234 x 8 + 4 = 9876
12345 x 8 + 5 = 98765
123456 x 8 + 6 = 987654
1234567 x 8 + 7 = 9876543
12345678 x 8 + 8 = 98765432
123456789 x 8 + 9 = 987654321

1 x 9 + 2 = 11
12 x 9 + 3 = 111
123 x 9 + 4 = 1111
1234 x 9 + 5 = 11111
12345 x 9 + 6 = 111111
123456 x 9 + 7 = 1111111
1234567 x 9 + 8 = 11111111
12345678 x 9 + 9 = 111111111
123456789 x 9 +10= 1111111111

9 x 9 + 7 = 88
98 x 9 + 6 = 888
987 x 9 + 5 = 8888
9876 x 9 + 4 = 88888
98765 x 9 + 3 = 888888
987654 x 9 + 2 = 8888888
9876543 x 9 + 1 = 88888888
98765432 x 9 + 0 = 888888888

Brilliant, isn't it?

And look at this

1 x 1 = 1
11 x 11 = 121
111 x 111 = 12321
1111 x 1111 = 1234321
11111 x 11111 = 123454321
111111 x 111111 = 12345654321
1111111 x 1111111 = 1234567654321
11111111 x 11111111 = 123456787654321
111111111 x 111111111 = 12345678987654321

Najunamar
BRFite
Posts: 201
Joined: 28 Dec 2007 16:40
Location: USA

A simple NT problem

Postby Najunamar » 03 Sep 2008 17:56

I know many are in the grad level problem solving mode - but here's one more at the middle school level.

Show that y^2 = 1 + 2^x, has only one integral solution {3,3}. i.e. no other solution exists where both x, y are inetgers. :mrgreen:

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 03 Sep 2008 19:30

One solution:
2^x=(y-1)(y+1) so both (y-1) and (y+1) has to be power of 2, (two consecutive even numbers except when x=0), powers of two goes 1,2,4,8,.. and then the difference is more than 2) QED .

Here is similar question, only a little (well, much) harder question :)
Find all possible integer solution of (x,y,z) where 3^x+4^y=5^z
(Hint: There aren't any except (0,1,1) and (2,2,2))

Added later: BTW (Just for the incentive for BRFers :) there is One million dollar prize for anyone who can show this for general numbers (ie prove a^x+b^y+z^c where, (a,b.c) are prime to each other, and one of (x,y,x>2) has only finite number of solutions .(No, for particular case of 3,4,5 the problem is hard but not that hard (can be done with high school math). BTW this is different from Fermat's last theorem (which is proven now) x^n+y^n=z^n have no integer solutions when n>2)

SK Mody
BRFite
Posts: 251
Joined: 15 Mar 2002 12:31

Re: BR Maths Corner-1

Postby SK Mody » 04 Sep 2008 08:25

How many different ways are there to evaluate the fraction:
v/w/x/y/z
Or equivalently how many different ways are there to evaluate
v-w-x-y-z

Can you generalize your answer to:
x1/x2/x3/ ... /x_n
?

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 04 Sep 2008 09:10

SK Mody wrote:How many different ways are there to evaluate the fraction:
v/w/x/y/z
Or equivalently how many different ways are there to evaluate
v-w-x-y-z

Can you generalize your answer to:
x1/x2/x3/ ... /x_n
?

Assuming that value depends on where one puts "(" ...
Don't peek unless you want to
(2n-2)!/(n!(n-1)!)


Similar (/same - shifted by one) problem : Number of ways a regular polygon of sides (n+2) be divided in n triangles...

Vriksh
BRFite
Posts: 406
Joined: 27 Apr 2003 11:31

Re: BR Maths Corner-1

Postby Vriksh » 04 Sep 2008 19:05

A long time ago I stumbled upon this interesting fact

Let Q be a set of n positive unique integers.

Then: n, S=Sum(Q) and P=Product(Q) uniquely define Q

ie. Given S, P and n, there exists only one set Q of n elements that satisfies.

When not all elements in Q are unique then there exists atmost 2 solutions.

example n=2
Q = 2,3
S=Sum(Q)=5
P=Prod(Q)=6

n=5
Q=1,2,3,4,5
S=15
P=120

non-unique case
n=5
Q=2,2,2,4,5
S=15
P=160

Caveat: I don't know if this theorem/hypothesis is true or not, but I have failed to find examples to the contrary perhaps due to lack of due diligence.

I tried hard to find multiple solutions for many different S and P but the problem is greater than my abilities (aka brute force). Infact I sort of began to believe if you take out the unique restriction in the set Q even then there is a special relationship of S and P ie only a couple of solutions exist per S and P and atmost one solution can exist for most S and P.

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 04 Sep 2008 21:37

Vriksh:

This theme is used for many recreational type problems. While given S and P "most" times the solution may be unique, but it is not necessary.

For example, given P=36, S=13 n=3 You have (6,6,1) and (2,2,9) or given P=96, S=21 you get (12,8,1) and (16,3,2) and as long as n>2 you can get as many non-unique solutions and more than 2 unique solutions if you increase n because if nothing else, you can get
P=96*13 and S=13+21 and n=6 you can construct 4 different set of solutions from the above two.

Hope this helps.

Here are two sort of famous problems, First one is easy (Answer is all but given away by the example above) the second one is challenging.
First problem:
A census taker asked a mathematician how many sons does he have and what are their ages.. So he answered, "well, I have three sons, the product of their ages (at their last birth date) in years is 36 and sum is my house number. The census taker, who was also a mathematician, looked at the house number and said "but that's not enough information". So he replied, "well the oldest one is playing cricket outside". The census taker was happy, filled out his forms etc..So what are the three ages?

The second problem (a much harder):
have two nephews Sanjay (Nickname can be S) and Pratik (nick name can be P). You can take it as given that both are good in math. I once selected 2 positive integers, both greater than 1 (equal or greater than 2), and less than 50. Let the sum of these numbers be S and Product of these numbers be P. I gave sum of these numbers (S) to S(anjay), and product of these numbers (P) to P(ratik).

Now S calls P on phone and tells; "You can never guess the sum S"
Little later P Calls S , " Yes, now I do know the value of S"
Little later S calls P . " Big deal, now I also know the value of P"

What were the numbers I selected?

ramana
Forum Moderator
Posts: 54175
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby ramana » 05 Sep 2008 01:44

I know a game.

- Ask someone to think of a three digit number and write it along side on a piece of paper. Eg 123 should be written as 123123.
- Give that slip to another person and ask them to divide by 13 and write the answer on another slip.
- Give the second slip of paper to another person and ask them to divide by 11 and write the answere on another slip of paper.
- Give the third slip of paper to another person and and ask them to divide by 7 and write the answer on a slip of paper.

Give the final slip of paper to the orignal person. It will be the original three digit number.

Why does that work?

amit_s
BRFite -Trainee
Posts: 14
Joined: 12 Jan 2008 04:46

Re: BR Maths Corner-1

Postby amit_s » 05 Sep 2008 01:57

ramana wrote:I know a game.

- Ask someone to think of a three digit number and write it along side on a piece of paper. Eg 123 should be written as 123123.
- Give that slip to another person and ask them to divide by 13 and write the answer on another slip.
- Give the second slip of paper to another person and ask them to divide by 11 and write the answere on another slip of paper.
- Give the third slip of paper to another person and and ask them to divide by 7 and write the answer on a slip of paper.

Give the final slip of paper to the orignal person. It will be the original three digit number.

Why does that work?



That was simple.

Let's assume number is abc.
abcabc can be written as c + 10b + 100c + 1000c + 10000b + 100000a
= 1001c + 10010b + 100100a
= 1001(c + 10b + 100a)
= 13*11*7(c+ 10b + 100a)
= 13*11*7(abc)

ramana
Forum Moderator
Posts: 54175
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby ramana » 05 Sep 2008 01:59

You got it. By writing the number alongside is same as mutliplying by 1001. The factors of 1001 are 13, 11 and 7.

Vriksh
BRFite
Posts: 406
Joined: 27 Apr 2003 11:31

Re: BR Maths Corner-1

Postby Vriksh » 05 Sep 2008 04:01

Amber G

the first one was easy, but the second one is far from satisfactory, All I could prove was the sum is odd and atleast one of the numbers is prime and then I gave up. I cheated a little bit and looked up goldbach conjectures, it still did not help me.

Also in the 3^x+4^y = 5^z problem.

I can prove if x is odd there exists no solution and the only soln lies in x being even, ie 0 and 2, but could not effectively disprove all higher odd powers or even that there cannot be other solutions for x=0 and x=2. 50% solution is good enough for the day I think.

the problem seems to reduce to a proof of

9^x+4^y = 5^z

does not have other solution apart from (0,1,1) and (1,2,2)

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 05 Sep 2008 06:37

Vriksh wrote:A long time ago I stumbled upon this interesting fact

Let Q be a set of n positive unique integers.

Then: n, S=Sum(Q) and P=Product(Q) uniquely define Q

ie. Given S, P and n, there exists only one set Q of n elements that satisfies.
.....


Just to add to my previous post, One can generate infinite number of cases, (even all distinct) for n=3 where same Sum and product give 2 solutions
You can take one set as (1, 3k, 2(2k-1)
Other (2,k , 3(2k-1))
You get sum= 7k-1 and product=6k(2k-1)..
From these you can get (2,3,15) and (1,9,10)
or (2,4,21) and (1,12,14)
... etc... etc..
You can get as many as you want by choosing k=2,3,4,5...
:)

ArmenT
BR Mainsite Crew
Posts: 4239
Joined: 10 Sep 2007 05:57
Location: Loud, Proud, Ugly American

Re: BR Maths Corner-1

Postby ArmenT » 05 Sep 2008 08:14

-- never mind. read amber G's question more carefully --

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 06 Sep 2008 02:18

Few points.
With respect to 1001, ..A relative unknown method to test divisibility by 7,11, and 13 involves this. To check divisibility by 2 (check the last digit), by 3 (sum all the digits and see if that is a multiple of 3), and by 5 (last digit is 0 or 5) is well known. Also one can check easily for number 11 too, but to check divisibility by 7 and 13 is not that simple. (although there are many methods- none too simple) Following method, IMO is simpler than most others, as I learned when I was young , as long as you can work with numbers less than 3 digits…(For example given a number 24034 you do quickly ( 034-24 you get 10 and you know the number is neither divisible by 7 or 11 or 13 and a number say
Given a number 123214 you quickly do 214-123=91 and thus the number (123214) is divisibly by 7 and 13… basically if the number is “abc,def,ghi,klm" you do abc-def+ghi-klm – fill in with zero’s on the left if you need…. Basically you reduce a large number to a number of 3 digits which is very easy to handle - I know this is rather academic when one has calculators..)

With respect to:
All I could prove was the sum is odd and atleast one of the numbers is prime and then I gave up. I cheated a little bit and looked up goldbach conjectures, it still did not help me.


V – Nice work, and Yes Goldbach conjecture implies that S is not even (or not like number 13 or 15 etc). The problem was one of the problems in past IMTS (where one has about 1 month to solve and help for books/computers/internet is allowed) so one can expect it to take some time .. I will post a solution here, if there would still be some interest.
With respect to 3^x+4^y = 5^z

Some Hints: when x<0 (negative) – it is easy to prove no solutions…
When x=0 : (that is 1+4^y=5^z) As you say, has only 1 solution. (proof, may be a little harder). I can give hint/proof (or Vriksh can too) if there is interest.
When x>0 : One Hint: Both x and z have to be even. (Vriksh has proven x is even). (FWIW - There would still be some work, after that. Also remember, if you can find a "general" method - for general case not only for 3,4,5 - there is a $100,000 prize! :)

With respect to Vriksh’s S and P problem, for n=3 (or greater than 3) one can prove there are infinite solutions (even non distinct).. I already gave one method which generate infinite cases where there are two solutions… It is possible to give method to generate infinite cases where there are 3 (or as many as you want) solutions for given P and Q

For example: n=3

(41,18486,24566)
(82, 6162, 36849)
(246,1846,41001)

Each give S=43093 and P=18619210116



(No, I did not use a computer! Or even a calculator I started with the method posted in previous message, that is (1,3k,2(2k-1)) (2,k,3(2k-1) and tried to find integer solution when the first number is 6 –
This quickly reduces to finding integer solutions of a eq x^2-41y^2=200
This is known as Brahmgupta equation (If you want to google, Pell equation may get more hits : for example see
http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Pell.html

The method I used, I found very interesting. It uses Bhaskara II’s chakravala method along with Brahmgupta’s way to solve basic Pell equation. I still get amazed that Brahmgupta did all that work in 6th century (?)... centuries before Euler/Fermat/Pell.


(The equation gives a series (infinite solutions for x and y each giving a new triplet)

Najunamar
BRFite
Posts: 201
Joined: 28 Dec 2007 16:40
Location: USA

Re: 3^x + 4^y = 5^z

Postby Najunamar » 06 Sep 2008 06:45

Here's one solution.

First using mod 3 on both sides, Find z is even (for nonzero x).Then taking mod 4 on both sides we find x is even.
Next, we use x=2m and z=2n, we get 4^z = 5^2n -3^ 2m
further simplified to 4^z = (5^n - 3^m)(5^n +3^m)

We find for the RHS one term is 2 mod 4 and the other is 0 mod 4 thus implying unless we have 2 itself as one of these factors there are no solutions since the only case is when m=n=1 when this is satisfied we find the only solution other than x=0 is when y=z=x=2

Case when x= 0 is 4^y = 5^z -1 = (5-1)*(5^(z-1)+5^(z-2)+...+5^2+5+1) RHS has 3 as one of the factors when z is even thus negating any possiblity other than z =1)


Another interesting problem is to show that there exist no integral solutions other than x=3, y=5 for x^3 - y^2 =2.

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: 3^x + 4^y = 5^z

Postby Amber G. » 06 Sep 2008 07:43

Najunamar wrote:Here's one solution.

First using mod 3 on both sides, Find z is even (for nonzero x).Then taking mod 4 on both sides we find x is even.
Next, we use x=2m and z=2n, we get 4^z = 5^2n -3^ 2m
further simplified to 4^z = (5^n - 3^m)(5^n +3^m)

We find for the RHS one term is 2 mod 4 and the other is 0 mod 4 thus implying unless we have 2 itself as one of these factors there are no solutions since the only case is when m=n=1 when this is satisfied we find the only solution other than x=0 is when y=z=x=2

Case when x= 0 is 4^y = 5^z -1 = (5-1)*(5^(z-1)+5^(z-2)+...+5^2+5+1) RHS has 3 as one of the factors when z is even thus negating any possiblity other than z =1)


.

Nice.. Agreed that both x and z has to be even, but IMO something is still missing in the proof (or I am not seeing it) , eg it is not clear how can one say that, say 5^m-3^n=2 has only possible solution when m=n=1 ?
( For example, as you yourself give a problem , 5^2 comes within 2 of 3^3 so may be some combination of (m,n) may get it to there..)

SK Mody
BRFite
Posts: 251
Joined: 15 Mar 2002 12:31

Re: BR Maths Corner-1

Postby SK Mody » 06 Sep 2008 16:23

Amber G. wrote:
SK Mody wrote:How many different ways are there to evaluate the fraction:
v/w/x/y/z
Or equivalently how many different ways are there to evaluate
v-w-x-y-z

Can you generalize your answer to:
x1/x2/x3/ ... /x_n
?

Assuming that value depends on where one puts "(" ...
Don't peek unless you want to
(2n-2)!/(n!(n-1)!)


Similar (/same - shifted by one) problem : Number of ways a regular polygon of sides (n+2) be divided in n triangles...


That was fast.


One way to show this is to note that if I let a_n denote the number of ways of bracketing x_0/x_1/x_2/.../x_n, then:

a_(n+1) = a_0*a_n + a_1*a_(n-1) + ... a_n*a_0

with a_0 = 1.

(Split the expression x_0/x_1/ ... /x_n into two parts in n different ways)

There is a nice way to solve the recurrence relation above using the characteristic polynomial (Sigma(a_k*s^k), but it is inconvenient to type it here due to the notation.

By the way the polygon problem is called Catalan's problem, I think.

Najunamar
BRFite
Posts: 201
Joined: 28 Dec 2007 16:40
Location: USA

Missing section in proof

Postby Najunamar » 06 Sep 2008 16:31

Here's some more intermediary steps. On the RHS if you take n even then first term is 2 mod 4 and second is 0 mod 4, if you take n is odd then reverse is true (first term 0 mod 4 and second is 2 mod 4).

Since any multiple of 2 other than 2*4^k where k = 0,1,.... would leave such a residue of 2 iff there are other factors that aren't powers of 4 there are no other integral solutions QED.

Najunamar
BRFite
Posts: 201
Joined: 28 Dec 2007 16:40
Location: USA

Re: x^3 -y^5 = 2

Postby Najunamar » 06 Sep 2008 16:34

I am sorry that should read x=3, y=+/- 5 (typing too fast in old age I guess :(( ). I left out the negative possibility .

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: Missing section in proof

Postby Amber G. » 06 Sep 2008 19:52

Najunamar wrote: Here's some more intermediary steps. On the RHS if you take n even then first term is 2 mod 4 and second is 0 mod 4, if you take n is odd then reverse is true (first term 0 mod 4 and second is 2 mod 4).

Since any multiple of 2 other than 2*4^k where k = 0,1,.... would leave such a residue of 2 iff there are other factors that aren't powers of 4 there are no other integral solutions QED.

Sorry, but IMO, this is still not clear, other factor, as you said, is 0 mod 4, (not power of 4) it does not mean it is of the type 4^k but 4*k ...and 2*(4*k) can certainly be a power of 4..
SKM:
It was fast

Because I heard the problem before :) These are called, as you said, Catalan numbers and they pop up at many places. The number of paths in nxn grid, between two diagonal points, if you can't cross the diagonal line is given by the same formula. Another problem is "cinema line" problem:
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)

For x^3-y^2=2 problem
Using Z[sqrt(-2)] as a unique factorization domain, that is easy. (Rewrite it as x^3=(y+sqrt(-2)(y-sqrt(-2)), each factor has to be perfect cube in that domain etc) Will be interested to see other proofs here.

Najunamar
BRFite
Posts: 201
Joined: 28 Dec 2007 16:40
Location: USA

Re: Not clear...

Postby Najunamar » 06 Sep 2008 22:53

For every term that is 2 mod 4, there exists at least 1 odd factor, see all integers that are 2 mod 4, +/- 6, +/- 10, ....to +/- infinitiy; hence unless it is +/- 2 the RHS possesses odd factors hence no solution can exist for n, m > 1 since LHS is a power of four and hence has even factors onleee.

I have not found a simple proof for x^3 - y^2 =2 problem - still looking for one that won't involve groups/fields etc.

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 07 Sep 2008 00:56

Sorry but one more time, :) hope fully the last time (seem to be repeating the same)

For every term that is 2 mod 4, there exists at least 1 odd factor, see all integers that are 2 mod 4, +/- 6, +/- 10, ....to +/- infinitiy; hence unless it is +/- 2 the RHS possesses odd factors hence no solution can exist for n, m > 1 since LHS is a power of four and hence has even factors onleee.

That's true.. but let me repeat, what I said before, to be clear..

1. Yes, one of the factor (on RHS) is 2 mod 4

2. The one which is 2 mod 4, has to be 2 (Otherwise, there is an odd factor >1)

3 And the other factor (on RHS) is multiple of 4 (But It is not shown, as far I can see, that it is a power of 4 or has an odd factor)


BUT, and here is the problem-- why it can't be, say 2147483648? (while the first factor is 2 and then 2*2147483648 = 4^16.) (you can have 2*(4k) as a power of 4 for example 2*512 = power of 4 where 512 is 0 mod 4)
Hope what I am saying is a little clearer now...
regards

SK Mody
BRFite
Posts: 251
Joined: 15 Mar 2002 12:31

Re: BR Maths Corner-1

Postby SK Mody » 07 Sep 2008 02:17

Amber G wrote:The number of paths in nxn grid, between two diagonal points, if you can't cross the diagonal line is given by the same formula. [Catalans formula]


Yes - one can think of an open bracket as +1 and close bracket as -1. Every x_i in x_1/x_2/.../x_n is associated with exactly one bracket (If the bracket is to the left of x_i it is an opening bracket. If it is to the right, it is a closing bracket. Then the bracketing problem can be restated as:
How many ways are there to write n +1's and n -1's in a row if for any k <= 2n the sum of the first k numbers is >= 0. If you then think of +1 as "moving north-east" and -1 as "moving south-east", you get the nxn grid problem. In fact that was how I tried to solve the problem originally. I was thinking of posting that problem also a bit later :lol:.

ChandraS

Re: BR Maths Corner-1

Postby ChandraS » 07 Sep 2008 03:41

ramana wrote:I know a game.

- Ask someone to think of a three digit number and write it along side on a piece of paper. Eg 123 should be written as 123123.
- Give that slip to another person and ask them to divide by 13 and write the answer on another slip.
- Give the second slip of paper to another person and ask them to divide by 11 and write the answere on another slip of paper.
- Give the third slip of paper to another person and and ask them to divide by 7 and write the answer on a slip of paper.

Give the final slip of paper to the orignal person. It will be the original three digit number.

Why does that work?

very simple onlee.

Assume the 3 digit # is A. Writing it side by side is as good as multiplying by 1000 and adding A to it ie. multiply by 1001. Now you divide by 13, 11 & 7. Now 13x11x7=1001 onlee!! So you get A back.

We had a math teacher do something similar in school back home. All of us kids would be amazed. Of course, she made us figure out why (not easy for 8-9 yr olds with just 1-2 years of multiplying higher numbers). But it all paid off for us as it made us aware of diff relationships between numbers and tricks to manipulate numbers faster, rather the dreaded rote learning of multiplication tables. I can still remember the monotone pitch of us kids going on... 'one four's are four' 'two four's are eight' 'three four's are twelve' and so on :rotfl:

Najunamar
BRFite
Posts: 201
Joined: 28 Dec 2007 16:40
Location: USA

Re: 3^x +4^y =5^z

Postby Najunamar » 08 Sep 2008 17:11

Amberji,
Attached is hopefully again the last piece of clarification.

Note: having proved that either of 5^m -3^n or 5^m +3^n = 2, it is clear that it is 5^m - 3^n that is 2 (since the only case for non-negative m,n where latter is true is if m=n=0 which is the trivial solution (0,-inf, 0) and (-inf, 0, 0) for (x,y,z).

Hence 5^m - 3^n =2, so 5^m = 2+3^n using modulo 3 and 4 we can indeed show m, n are odd and further more n is of the form 4k+1. Substituting for 5^m we get
4^y = (2+3^n +3^n)*(2) i.e. 4^y = 4*(1+3^n) for some odd n

We can now show that (1+3^n) = (1+3)*(3^(n-1)-3^(n-2)+....+1); Here the RHS has 4 as one factor and the other factor has an odd number of odd terms hence has to be odd - only case where this yields an acceptable solution is when n=1 where we get simply 1 as the factor in question.

I believe this proves the original assertion.

Najunamar
BRFite
Posts: 201
Joined: 28 Dec 2007 16:40
Location: USA

Re: Missing section in proof

Postby Najunamar » 08 Sep 2008 18:31

For x^3-y^2=2 problem
Using Z[sqrt(-2)] as a unique factorization domain, that is easy. (Rewrite it as x^3=(y+sqrt(-2)(y-sqrt(-2)), each factor has to be perfect cube in that domain etc) Will be interested to see other proofs here.[/quote]


I have another approach to the x^3-y^2 =2 problem. I still had to resort to Descartes rule of signs (still qualifies as high school level math?). I would also love to see other approaches (more elegant solutions?)

use x^3 - 27 = y^2 - 25, factorize both sides to give (x-3)(x^2 +3x +9) = (y-5)(y+5).

RHS is positive for abs(y) >5 and negative when abs(y)< 5. (ofcourse zero when abs(y)=5

Case 1: abs (y) > 5

Now we are assured RHS >0 => also that x >3 hence the other factor on LHS (x^2+3x+9) = ((y^2 -25)/((y^2-25)^(1/3) -3)

Case 2: abs (y) < 5

Now RHS is < 0 and x < 3, once again we are left with same equation as above.

Now, the factor x^2 + 3x +9 -f(y) = 0 has real roots iff 9-f(y) < 0 which means,

f(y) > 9 where f(y) = (y^2 -25)/((y^2-25)^(1/3)-3).

Using y^2 – 25 = z and rearranging, simplifying this implies

z > 9*(z^(1/3) – 3) => ((z/9)+3)^3 >z,

z^3 + (729*3)z^2 +(8*729)z +27*729 > 0

Using Descartes rule of signs we can conclude max positive real roots = 0 and max real negative roots = 3. But we need non negative roots for abs(y) > 5 , hence no solution for abs(y) >5, using all possible combinations for abs (y) <5 we find no other solutions either.

Najunamar
BRFite
Posts: 201
Joined: 28 Dec 2007 16:40
Location: USA

Re:Found an error in the previous post...

Postby Najunamar » 09 Sep 2008 19:38

Oops - looks like there is no backdoor way for the x^3 - y^2 =2 integer solutions problem, In one of the steps I had mistakenly used x^3 = y^2 - 25 instead of y^2 + 2.

Apologize for the confusion - still searching for an elegant and simple solution....

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 10 Sep 2008 03:30

Najunamar - with respect to 3^x+4^y=5^z, yep, the step, to show, no solutions for 3^n-1=2^m, for n>2 is critical. BTW one can just check modulo 8 (LHS can only be 2 or 4 - (because 3^2==1 mod 8 ) while for n>2 rhs is 0 mod 8 )

With respect to x^3-y^2=2, I noticed, the typo, but knew you will find it. The trouble with Descartes rule type solution is that for real values of x , x can be as large as you want.
(I did have/seen solution(s) which does not involve UFD but none as elegant, or short as UFD method... It will be "beyond the scope" here)
BTW - An interesting part about the above (x^3-y^2=2),
if we allow rational values for x and y are there other solutions besides (5,3)?

Answer is yes. apart from (3,2), x=1.29 and y=3.83 would work other solution
x= 164323 / 29241 and y=66234835 / 5000211


Another problem: (Same difficulty - and only one solution - (+- for y counts as one) also) is
x^3+2= y^2

(There was, once a prize for such a puzzle to find rational solutions for x^3+y^3=6 .. toobad that someone told me after the deadline finished, else it was easy money)

Let me ask, a similar problem ( based on the same theme. ) Its an old classic problem

Find a right angle triangle, whose all sides are integers (>0) and one leg is 1 unit longer than the other leg. (Leg here is not hypotenuse). For example one solution is (3,4) (hypotenuse is-5, 3^2+4^2=5^2). Other is (20, 21) (One can check 20^2+21^2=29^2)
Can you find any other value?

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 10 Sep 2008 04:17

Number theory is cool .. but just to change flavor, here is a (hopefully simple)problem in probability.

X throws a fair coin 50 times, Y throws a fair coin 51 times, what is the probability that Y will throw more heads than X?

Amber G.
BRF Oldie
Posts: 6985
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 11 Sep 2008 01:36

Another 2 probability problems - Not hard but may be a little different than run of the mill -
1. A fair coin is tossed until either 5 heads come consecutively or 3 tails come consecutively . (You keep throwing the coin till one of the above two happens). What is probability that 5 heads (consecutive) will come before 3 tails (consecutive)?

2. Is probability of January 13 falling on a Saturday is less than it (January 13) falling on a Friday? If yes why? and by how much? (We assume Gregorian Calendar - with usual rules of leap years etc._

Karan Dixit
BRFite
Posts: 1102
Joined: 23 Mar 2007 02:43
Location: Calcutta

Re: BR Maths Corner-1

Postby Karan Dixit » 11 Sep 2008 03:57

I have a logic problem. Logic is a lot like mathematics. So, I think this thread would be an appropriate thread for this problem. I friend of mine shared this problem with me over masala dosha dinner. Nothing unethical involved here so please take it easy.

Problem:

We have 25 horses arranged as following:

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Our objective is to determine fast top three horses. The limitation of the course is that we can race only five horses per race. We do not have time clock. So, only way to determine a winner is by running them and watching who crosses the finish line first.

We can make some assumptions:
a) Horses do not get tired
b) Each horse has one fixed speed with which it runs

How many races will it require to determine top three winners?

Please explain the logic you used to reach the answer. Thanks!

Vriksh
BRFite
Posts: 406
Joined: 27 Apr 2003 11:31

Re: BR Maths Corner-1

Postby Vriksh » 11 Sep 2008 18:16

Regarding Horse races


7<=Races <=9 races
I cannot explain properly but it involves

1. Race 5 horses at a time = 5 races total
2. Choose top 3 of each race
3. Race the 5 first place horses (get 1,2,3 place here) = 1 Race -> fastest horse realized
4. Race the 5 second place horses (get position 1 and 2) = 1 Race
5. If need be Race the 5 3rd place horses (get position 1 here) = 1 Race
6. If need be race horses at place 2 and 3 of step 3 with 1 and 2 step 4 and place 1 of step 5 = 1 Race

Max Races = 9
Min Races = 7
Step 5 is optional if we find the 2 place finisher of the first race of the top horse of step 3 is not 1st in step 4
Step 6 is optional if Step 5 is played out if we find the 3 place finisher of the first race of the top horse of step 3 is not 1st in step 5

There are other possibilities but each can be discounted logically



Return to “Technology & Economic Forum”

Who is online

Users browsing this forum: Ambar and 11 guests