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.
Amber G.
BRF Oldie
Posts: 7034
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 11 Sep 2008 19:29

V - In 7 races, you can always find the top three.
(Let the horses be named A1,A2, ..A5, B1,...B5 ...E1,..E5 such that) wlog
(Assuming X1>X2>X3>X4>X5 for say X=A,B,C,D,E) 5 races
Assume A1>B1>C1>D1>E1 (Sixth race)
Run (A2,A3,B1,B2,C1) (7th race) top 2 from here (in right order) along with A1 as on the top

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

Re: BR Maths Corner-1

Postby Nandu » 12 Sep 2008 01:33

Amber G. wrote: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?


0.5


I was surprised when I worked it out.
First consider the case of X and Y each making 50 tosses. There are N = 2^100 different equal probabilty outcomes.
Let a be the number of outcomes where X and Y has equal number of heads.
Let b be the number of outcomes where Y has more heads.
Then, by symmetry, b is also the number of outcomes where Y has less heads.
Therefore, a + 2*b = N.
Now, let Y toss the coin one more time. In one case, he will get tails, so giving b outcomes where he has
more heads than X. In the other case, he will get heads, giving a + b (previously equal + previously more) outcomes where he has more heads than X. Add them up, and you have b + a + b = a + 2*b = N outcomes matching your criterion. Divide by total number pf possible outcomes = 2^101 = 2 * N and you get 0.5.

I didn't realize a and b need not be worked out to get the final answer, so I did make an attempt at finding out what a is, and it is 100C50.

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

Re: BR Maths Corner-1

Postby SK Mody » 14 Sep 2008 12:53

I don't know if this is a "well known" problem, but it's something that occurred to me.
A car is parked facing west on the side of the road, and parallel to it. It needs to make an N-point turn and go east. Given that the turning radius of the car is 'r' and the width of the road is 'w':
(a) what is the minimum possible value of N?
(b) what is the length of road required for this value of N?

You can assume that the dimensions of the car are negligible compared to 'w'.
You must at least explain your answer.

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

Re: BR Maths Corner-1

Postby SK Mody » 17 Sep 2008 19:49

Karan Dixit wrote: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!


Thread is in danger of falling of the 1 week edge.
Regarding horse races problem, I come to the same conclusion as Vriksh.

The answer is 9 races.
Divide horses into 5 groups of 5. Race each set. Take the top 3 from each set. So we have 5 sets of 3 horses. Take the 1st horse from the each of the 5 sets. Call this set A. Take the 2nd horse from each set - call this set B. Call the set of #3 horses set C. Now the winner has to be from set A. So race set A - remove the best horse - this is the winner. Also remove the slowest 2 from set A since they cannot be in the top 3. We are left with 12 horses. Now Set B can have at most 2 of the fastest 3 horses. So race set B and remove the slowest 3. Similarly set C can have at most 1 of the 3 fastest horses. So race set C and remove all except the winner from C. We are left with 5 horses (2 from set A, 2 from set B and 1 from set C). Race them to get the 2nd and 3rd fastest.

So all in all 9 races required.


A friendly reminder and link to: an earlier question.

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

Re: BR Maths Corner-1

Postby Amber G. » 18 Sep 2008 20:45

SKM - As said before, for horses race, 7 races are enough(see the earlier message) in all cases to get top 3 horses.

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

Re: BR Maths Corner-1

Postby SK Mody » 18 Sep 2008 21:32

Hmm. Yes. Sloppy thinking on my part. Thanks.

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

Re: BR Maths Corner-1

Postby Amber G. » 18 Sep 2008 22:57

FWIW: Here is my outline of the solution for 3^x+4^y=5^z problem: (x,y,z are ntegers)
Case 1 x<0 Easy to see both y and z has to be negative.
(why? – because for non—negative y (or z) 4^y is integer etc)
In that case, putting a=-x,b=-y,c=-z (a,b,c >0)
1/3^a + 1/4^ b = 1/5^c ==> 5^c(3^a+4^b) = (3^a )(4^b)
Which is impossible because there is no factor of 5 on RHS.

Case 2 – x=0 we have 1+4^y =5^z
On modulo 3, LHS is congruent to 2, so z has to be odd, so we write 1+4^y = 5*(25)^w
Now take modulo 8, RHS is 5 (because 25 is 1 modulo 8 ), so y has to be 1. (if y>1, LHS==1+0 = = 1 modulo 8.
So we have (0,1,1) as a solution.

So the main case. Case 3 (x,y,z all >0)
Take modulo 4, since RHS (5^z) is congruent to 1,
On LHS , we have to have 3^x or (-1)^x so x has to be even. Let x=2a

Similarly take modulo 3, LHS is congruent to 1 so z hast to be even too z=2c
So we have
4^y = 5^(2c)-3^(2a)= (5^c+3^a) (5^c-3^a)
Since, LHS is a power of 2 only, both the factors on right has to be some power of 2, so let

5^c+3^a = 2^m (obviously m>=3) (eq 1)
5^c-3^a = 2^n (obviously m>n>0) (eq 2)

subtracting we get 2*3^a = 2^m-2^n = 2^n(2^(m-n)-1)
or 3^a = (2^(n-1)) (2^(m-n)-1)
Since, LHS has no factors of 2, n-1 has to be zero. So now we have
3^a = 2^(m-1) – 1
Now if we take modulo 8, LHS is either 1 or 3,
While 2^(m-1) modulo 8 is zero for all exponents of 3 or more.
IOW, (m-1) can not be greater than 2
(but we know m is greater than 2 (eq 1) , so only possible value for m = 3)
Hence a=1
Or x = 2a = 2
Hence, only possible integer solutions are, (0,1,1) and (2,2,2).

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

Re: BR Maths Corner-1

Postby Amber G. » 18 Sep 2008 23:10

Just to add to the above,
A very easy similar looking question to be tried:
Find one solution for (a^3+b^4=c^5) (a,b,c are positive integers) :)
(See how long does it take...

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

Re: BR Maths Corner-1

Postby Karan Dixit » 19 Sep 2008 20:29

Regarding Horse Race:

Amber G is correct. You need only seven races to determine the top three positions. I liked the notation style Amber used to explain it.

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

Re: BR Maths Corner-1

Postby SK Mody » 24 Sep 2008 12:02

Give a method to find the exact real or complex solutions to the equation: x^3 + bx^2 + cx + d = 0.
Those who know are banned from giving the first answer. Amber G, you have been warned!
You disqualify yourself by googling for the answer.

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

Re: BR Maths Corner-1

Postby Amber G. » 27 Sep 2008 03:48

Amber G. wrote:Rumor is that a new "largest known prime" (mersenne prime number) number is found.. wait for a few days (about 2 weeks will be needed for it to be rechecked) till it gets checked out, and if so verified , it might hit the news.. Last largest know prime number discovered in 2006 was 2^32582,657 -1.
(I think $100,000 prize is going to be claimed - if the number checks out)
(It may be interesting that the story is being breaking out in BRF many days ahead of main news stream media - that is if the number gets independently verified to be a prime)

Okay so rumor was true. Not one but two mersenne primes (and two more perfect numbers)
were discovered. These were 2^37156667-1 and 2^43112609-1 (larger one was discovered earlier - the one mentioned in the "rumor" above.
($100,000 prize won because it is (both are) more than 10 million digits.

Story: in various news papers for example: Latimes
UCLA mathematicians claim record in search for rare prime numbers

BTW, prize for 100 million digits ($150,000) is still unclaimed, you (or your computer) may want to try it..:)

BTW - speaking of perfect numbers, following three theorems may be fun to prove (they are not that difficult and fun if you like to like number theory - and proof, if you are curious, could be found in books/wiki etc... I can put outline here, if some one is interested, and curious)
1 - Prove, given ( 2^p - 1 ) is prime, ==> p is prime. (easy)
2 - If (2^p-1 ) is prime, ((2^p-1)(2^(p-1)) is a perfect number (easy-medium)
3 - All even perfect numbers are of the form above (medium-hard)
(No one knows, if there are any odd perfect numbers - and no one has proven that there are not any- One of very famous open question in number theory)
Definition: http://en.wikipedia.org/wiki/Perfect_number

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

Re: BR Maths Corner-1

Postby SK Mody » 27 Sep 2008 14:15

Consider an equilateral triangle of height 'h'. Take any point P inside the triangle. Drop ppendiculars PA, PB and PC to each of the three sides.
Show that PA + PB + PC = h.

Show the same result for a regular tetrahedron. (Where PA PB and PC are the ppendiculars to the faces)

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

Re: BR Maths Corner-1

Postby Amber G. » 27 Sep 2008 17:07

Consider an equilateral triangle of height 'h'. Take any point P inside the triangle. Drop ppendiculars PA, PB and PC to each of the three sides.
Show that PA + PB + PC =h

Sorry could not resist it:
Area of a given triangle (or Volume of a tetrahedron, for that matter) is constant (that is , it does not depend on how you calculate it)
And of course, Area of the triangle = 3 small triangles if you join P to the corners of the triangle .. and rest is easy

But here is as question from Duke Math meet (High school) may be fun:

Given equivilateral triangle XYZ, and a point P inside, if PX=3, PY=4 and PZ=5 find h (height of equilateral triangle)
Note: The equilateral triangle is XYZ, and we know the distance of P from each of the corner)

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

Re: BR Maths Corner-1

Postby SK Mody » 28 Sep 2008 00:08

Amber G wrote:Given equivilateral triangle XYZ, and a point P inside, if PX=3, PY=4 and PZ=5 find h (height of equilateral triangle)


I found an ugly way to do it.

Let 'a' be the side of the triangle.
Let t1, t2 and t3 be the angles at point P.
t1 + t2 + t3 = 360

By cosine rule:
3^2 + 4^2 - 24cos(t1) = a^2
4^2 + 5^2 - 40cos(t2) = a^2
5^2 + 3^2 - 30cos(t3) = a^2

also:
cos(t3) = cos(t1+t2)
which gives after expanding and squaring once:
cos^2(t1) + cos^2(t2) + cos^2(t3) - 2cos(t1)cos(t2)cos(t3) - 1 = 0

Eliminating cos(t1), cos(t2) and cos(t3), I get after an unpleasant calculation:
a^4 - 50a^2 + 193 = 0

Solving for a^2 gives a^2 = 25 + 12*sqrt(3) (= 45.784 approx.)
Hence a = 6.766 approx.


Maybe there is a more elegant way.

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

Re: BR Maths Corner-1

Postby SK Mody » 28 Sep 2008 00:23

Amber G wrote:Sorry could not resist it:


The question was posed by my grade 11 maths teacher. I was too hung up on euclidean geometry at that time to be able to solve it. I think Euclidean geometry is a just a bad idea in school (particularly the excessive emphasis placed on it in those days - not sure about how it is now). It makes you think like a lawyer rather than a mathematician. If one wants to illustrate the idea of rigour there are easier topics.

Sanjay M
BRF Oldie
Posts: 4892
Joined: 02 Nov 2005 14:57

Re: BR Maths Corner-1

Postby Sanjay M » 28 Sep 2008 06:10

Huge new prime number discovered (BBC)

The search for new high prime number continues
Mathematicians in California could be in line for a $100,000 prize (£54,000) for finding a new prime number which has 13 million digits.

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

Re: BR Maths Corner-1

Postby Amber G. » 28 Sep 2008 07:51

Sanjay M wrote:
Huge new prime number discovered (BBC)

The search for new high prime number continues
Mathematicians in California could be in line for a $100,000 prize (£54,000) for finding a new prime number which has 13 million digits.

As said before, (see post a few message above and one on August 26) - breaking of this story in the news and following prediction was here almost a month ago!!

Rumor is that a new "largest known prime" (mersenne prime number) number is found.. wait for a few days (about 2 weeks will be needed for it to be rechecked) till it gets checked out, and if so verified , it might hit the news.

Rye
BRFite
Posts: 1183
Joined: 05 Aug 2001 11:31

Re: BR Maths Corner-1

Postby Rye » 28 Sep 2008 18:15

Other than Public/private key encryption, what is the use of finding these large primes? Just time-pass for the bored mathematician or pointless curiosity?

Saral
BRFite
Posts: 1663
Joined: 16 Jan 2005 14:05

Re: BR Maths Corner-1

Postby Saral » 29 Sep 2008 04:36

This problem is based on a April 1997 Scientific American article on Murphy's Law. "The science of Murphy's law by Mathews". I cant get the article now but I recall it mentioned about how we tend to get stuck with odd socks (unpaired) after a while. So here's the problem I cooked up based on this article. You can check your answer by simulating the problem on a computer.

---
Suppose I have 6 pairs of new socks that I keep in a drawer at the beginning of the year. However, on any given day, there is a probability of 0.019178 that one individual sock is going to get lost and won't find its way back to the drawer. How many socks can I expect to have left at the end of the year ? What is the probability that there is not a single matching pair left in the drawer ?
---

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

Re: BR Maths Corner-1

Postby ArmenT » 29 Sep 2008 06:11

Rye wrote:Other than Public/private key encryption, what is the use of finding these large primes? Just time-pass for the bored mathematician or pointless curiosity?

You know, a lot of mathematics doesn't have any practical application (yet), but may become useful in the future.

G. H. Hardy (the chap who collaborated with S. Ramanujan) even wrote an essay called A Mathematician's Apology dealing with the topic. At the time, the applicability of number theory to cryptography was not yet discovered.

When S. Ramanujan wrote down his formulae, he probably had no idea that they would be used in string theory or crystallography.

Rye
BRFite
Posts: 1183
Joined: 05 Aug 2001 11:31

Re: BR Maths Corner-1

Postby Rye » 29 Sep 2008 07:47

ArmenT, I am talking about the specific motivation for finding large primes (which can be done algorithmically via "Eratosthenes's Sieve" which considers all the primes upto sqrt(N) to determine if N is a prime -- there are probably better techniques for filtering out composites than this one by now). These large primes are being sought for some application given the rather large incentive -- so was wondering why it is worth a lot of money...

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

Re: BR Maths Corner-1

Postby SK Mody » 29 Sep 2008 13:35

Rye, the same question occurred to me. I think it has more to do with the objectives of EFF (electronic frontier foundation) which is the one that is giving the reward. Nothing to do with primes but what are the political effects of having hundreds of thousands of networked computers working on some seemingly useless calculation. I don't know but perhaps it fits into their strategy somehow :?:

It is also an exercize in parallel processing.

Rye
BRFite
Posts: 1183
Joined: 05 Aug 2001 11:31

Re: BR Maths Corner-1

Postby Rye » 29 Sep 2008 18:51

Mody, I think this is for public/private key encryption -- not aware of any other uses for large primes. Inferring from the distributed nature of the computation, I wager they are doing some sort of "eratosthenes's sieve" like technique, i.e., Assume that you know all the primes until some very large N -- Take the next N^2-N numbers and if you have 1000 machines so that each machine is tasked with determining the primes from its assigned set of 1000 numbers between N and N^2, i.e., X numbers for each of the 1000 machines totalling to N^2-N. The computation can proceed in parallel on all 1000 machines to determine the primes between N and N^2-N

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

Re: BR Maths Corner-1

Postby ArmenT » 29 Sep 2008 21:40

A large distributed network could be used for the reverse as well (i.e.) factoring a large number into its prime factors. That would be of more interest to people trying to crack a message encrypted with public-key encryption.

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

Re: BR Maths Corner-1

Postby Nandu » 30 Sep 2008 01:27

Rye wrote:Other than Public/private key encryption, what is the use of finding these large primes? Just time-pass for the bored mathematician or pointless curiosity?



Just to be clear, the finding of new Mersenne primes have NO IMPLICATION AT ALL on any currently used schemes of encryption. In particular, it doesn't affect RSA in any way.

It is mostly a computational curiosity, but lot of good and foreseeable things eventually come from the "idle curiosity of bored mathematicians", so i wouldn't sneer at it either.

Rye
BRFite
Posts: 1183
Joined: 05 Aug 2001 11:31

Re: BR Maths Corner-1

Postby Rye » 30 Sep 2008 03:32

Thanks for the response, Nandu -- that's a lot money to give away as prize for just mathematical curiosity, typically. Anyway, I am not insulting, mocking, sneering or doing anything else to cause the gentle people here any khujli. O&O.

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

Re: BR Maths Corner-1

Postby Nandu » 30 Sep 2008 04:25

I don't see the edit button on that post any more, so let me clarify that I meant "good and unforeseeable things".

No offense was taken, Rye. It was merely a comment.

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

Re: BR Maths Corner-1

Postby Amber G. » 09 Dec 2008 03:00

FWIW - If any one is curious --

SK Mody wrote:
Amber G wrote:Given equivilateral triangle XYZ, and a point P inside, if PX=3, PY=4 and PZ=5 find h (height of equilateral triangle)



Maybe there is a more elegant way.

One easy way to do is Hint : Rotate small triangle XPZ 60 degrees clockwise (and similarly other three triangles) keeping Z at the same place and placing X on Y (and P is now outside) - Rest is simple = 2 (area of triangle XYZ ) = 3 (area of (3,4,5) triangle) + area of (3,3,3)+ area of (4,4,4)+ area(5,5,5).

One another note, the answer to the Sanjay/pratik nephew question is (13,4) (One can verify that)

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

Re: BR Maths Corner-1

Postby Amber G. » 09 Dec 2008 03:08

Wrt to Merserene primes and interest in number theory, here is a related problem:

A telephone number ( A seven digit positive integer, that is greater than 999999 and less than 10000000) has this property: If you add the squares of number represented by first 3 digits and add it to the square of last 4 digit number, you get the number it self.

That is, suppose the number (written in ordinary decimal notation) is abcdefg (a,b,c,d are just decimal digits) and we have

(abc)^2 +(defg)^2 = abcdefg

(again abc is not product of a,b,c -- it is just a number represented by digits abc)

See if this can be done without any help of a computer program (or use the computer program just to find a hint) - The problem is meant to be solved without calculator etc.

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

Re: BR Maths Corner-1

Postby Amber G. » 16 Dec 2008 05:10

With respect to the above, problem: here is something which may arise curiosity in all those who love vedic (or otherwise) math -

1/17 to eight places of decimals is: 0.05882353

but 588^2+2353^2 = 5882353
(It is answer to the above problem, but why?
(IOW can you give mathematical justification or explain it)

SaiK
BRF Oldie
Posts: 36415
Joined: 29 Oct 2003 12:31
Location: NowHere

Re: BR Maths Corner-1

Postby SaiK » 30 Dec 2008 23:27

negi sahib, i x-posting..

SaiK wrote:etch-quizz-me nayak, please ignore my post. unable to find the math thread

math/algo question. how many guesses it takes to arrive within a given positive number N (>0), if for each guess the answer is too high, too low..? any formula?


negi wrote:Saik sir please elaborate with an example, from whatever I understood answer will be Infinity as number system is limitless hence the number of guesses too.


============

of course that N was with an intention to know what would be the algo, lets get some finite numbers like 1000, 10,000, etc. is there a relationship or a fixed/variable/formula "number of guess" for all positive values. lets keep infinity out of this question./sorry.

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

Re: BR Maths Corner-1

Postby Amber G. » 31 Dec 2008 01:28

FWIW - Unless I am missing something trivial - for "Yes/No" question the answer would be simply (log (to the base 2) n) or IOW, n questions needed for a any number from (1 to 2^n )

Also - for the earlier question of mine - Another Hint, 5882353 = (10^8+1) /17 ..
But why does this gives interesting property 588^2+2353^2 = 5882353 ?

SaiK
BRF Oldie
Posts: 36415
Joined: 29 Oct 2003 12:31
Location: NowHere

Re: BR Maths Corner-1

Postby SaiK » 31 Dec 2008 03:36

thanks amber, so 1000 -> 10 guesses (1024=2^(10)). log(10) = 1x10 = 10. am i correct?

mnag
BRFite -Trainee
Posts: 75
Joined: 01 Jan 2009 01:18

Re: BR Maths Corner-1

Postby mnag » 01 Jan 2009 12:58

Hi Amber
Regarding your problem (abc)^2 +(defg)^2 = abcdefg , I've worked out the solution. please let me know if it looks fine

from the answers, i could work out the solution. but i think i am missing some theorems here (i remember using lots of them during olympiad days, but cant recollect now). One thing i did notice is that 2353 = 4*588+1

lets denote abc by x and defg by y.

the problem is to solve

x^2+y^2 = 10000x+y

This means to find y and x such that
y^2 - y = 10000x -x
y(y-1) = x(10000-x)
such that x ranges from 100 to 999 and y range from 0 to 9999

since y >> 1 and x << 10000, we can simplify it to
y(y-1) = x(10000-x) => y^2 = 10000x => y = 100*sqrt(x)



i think there is some theorem which states that when you have y(y-1) = x (constant - x), and y is not a multiple of x, y-1 is a multiple of x and (a-x) is a multipe of y.

lets use y-1 = kx where k is a constant.

since we approximated y=100*sqrt(x),
using the ranges of x from 100 to 999, y ranges from 1000 to 3000 and k ranges from approx 3-10

y -1 = kx (k ranging from 3 to 10)
y = kx + 1

substituting

y(y-1) = kx(kx+1) = x(1000-x) => x = (1000-k)/(k^2+1)

for k=2 to 10 as found previously, only k=4 yields integer values. so k=4

so x = 588, y=4k+1 = 2353

Let me know if i am missing something

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

Re: BR Maths Corner-1

Postby Amber G. » 08 Jan 2009 09:03

mnag – Nice work but the problem can be solved without trial and error type method. (It was meant to be solved without calculator/computer)

Here is one method (which I had in mind)
As you started, one has to solve (for positive integers)
x^2 +y^2 = 10000 x + y
or x^2-1000x+y^2-y = 0
or (4x^2 – 4*10000x +10000^2 ) + (4y^2 -4y + 1) = 10000^2+1
or (2x-10000)^2 + (2y-1)^2 = 10000^2+1

So basically the problem is to how to find cases (all cases) where sum of squares of two numbers is 10^8+1. One thing, as I given a hint that this number is divisible by 17

How do we solve it, We use a method first given by Brahmgupta – Or use factoring in Guaisan Integers.

If one is not familiar with these, they are fun, and wikipedia (or any good book on Number theory) has good article(s) For example Please see
brahmgupta link

For Gaussian Integers Intro:
http://en.wikipedia.org/wiki/Gaussian_integers

or how to find the two squares see Mud math facts:
http://www.math.hmc.edu/funfacts/ffiles/20005.5.shtml

Also:
http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares


Any way here is basic theorem (easy to check)
Product (a^2+b^2)(c^2+d^2)
can be written as (ac+bd)^2 +(ad-bc)^2 (or ac-bd)^2 + (ad+bc)^2)

(If a number is prime, (and is odd, and is of the form 4k+1) there is one and only one way to write it – If the number is product of two primes, and if you can write each as sum of two squares, you can write it as sum of two squares (in 2 ways – as shown above)

So


We have: 100000001 = 17 * 5882353 = (1^2+4^2) (588^2+2353^2) (see note 1)
=(1*588+4*2353)^2 + (1*2353 – 4*588)^2 = 10000^2+1^2
and also = (1*588-4*2353)^2 + (1*2353+4*588)^2 = 8824^2+4705^2

First gives, 2x-10000 = (+- ) 10000 ==> x= 10000 or 0
and (2y-1) =(+-) 1 = => y = 1 or 0

Second gives 2x-10000 = (+-) 8824 ==> x = 588 or 9412
And (2y-1) = (+-) 4705 == > y = 2353

So only solutions are (10000,0), (0,0),(10000,1),(0,1) (which are trivial)
And only 7 digit number is 5882353 ( other one also works 9412^2+2353^2 = 94122353 but is 8 digits)

Hope this helps and is fun.

(Note 1 - To get the values, gaussian integer trick is easy - you know (we are taking i=sqrt(-1)

10000^+1 = (10000+i)(10000-1) is divisible by 17 = 16+1 = (4+i) (4-i)
so (4+i) must divide 10000+i or 10000-i, we indeed see that (1000+i)/(4+i) is indeed an guassian integer = 2353-588i etc)

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

Re: BR Maths Corner-1

Postby Amber G. » 08 Jan 2009 09:14

If one looks carefully (and use a number theory) one would see/prove , that in general
solutions of x^2+y^2 = px + y
in integers are given, if you can find factors of p^2+1.
If (a^2+b^2) N = p^2+1
Then (a^2*N) is a solution of (px+y) ...
For example if you see 10000+1 = 73*137 and 73=3^2+8^2
You can find the number like 3^2*137 = 1233 has the property 12^2+33^2 = 1233
(Also since 137=11^2+2^2 , another such number is 11^2*73 = 8833 = 88^2+33^2)

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

Re: BR Maths Corner-1

Postby ramana » 20 Feb 2009 09:14

Has anyone read the book "The Universe and the Teacup" by K.C. Cole of UCLA?

Mort Walker
BRF Oldie
Posts: 8422
Joined: 31 May 2004 11:31
Location: The rings around Uranus.

Re: BR Maths Corner-1

Postby Mort Walker » 20 Feb 2009 09:40

Its gotten bad reviews on Amazon.

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

Re: BR Maths Corner-1

Postby SK Mody » 23 Feb 2009 21:11

The reviews either rate is very high or very low. The non-math people seemed to have liked the book.
I find the title intriguing - perhaps a indication of the philosophical depth of the author. Also her emphasis on symmetries which is the key to understanding conservation laws in physics. Lot of powerful ideas, but from appearances, it seems more of an inspirational book than one that is trying to convey a specific idea. Seems like the sort of book that is best read in the bookstore and left on the shelf :mrgreen: . Also, from the reviews the book appears to have a political slant.
Last edited by SK Mody on 23 Feb 2009 21:33, edited 1 time in total.

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

Re: BR Maths Corner-1

Postby SK Mody » 23 Feb 2009 21:25

(a) Give a short proof (no need to dwell on technicalities, just intuitive clarity) that the volume of an n-dimensional parallelopiped formed from the vectors a_1, a_2, ... a_n in n-dimensional real space is det(A), where A is the matrix whose columns are the vectors a_i, i =1,2, .... n.

(b) What is the "area" of a k-dimensional parallelopiped formed from the vectors a_1, a_2, ... a_k in n-dimensional real space. (k <= n).


Return to “Technology & Economic Forum”

Who is online

Users browsing this forum: No registered users and 3 guests