Bharat Rakshak Forum Announcement

Hello Everyone,

A warm welcome back to the Bharat Rakshak Forum.

Important Notice: Due to a corruption in the BR forum database we regret to announce that data records relating to some of our registered users have been lost. We estimate approx. 500 user details are deleted.

To ease the process of recreating the user IDs we request members that have previously posted on the BR forums to recognise and identify their posts, once the posts are identified please contact the BRF moderator team by emailing BRF Mod Team with your post details.

The mod team will be able to update your username, email etc. so that the user history can be maintained.

Unfortunately for members that have never posted or have had all their posts deleted i.e. users that have 0 posts, we will be unable to recreate your account hence we request that you re-register again.

We apologise for any inconvenience caused and thank you for your understanding.

Regards,
Seetal

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.
sudarshan
BRFite
Posts: 1430
Joined: 09 Aug 2008 08:56

Re: BR Maths Corner-1

Postby sudarshan » 17 Sep 2016 22:38

Yes, a=1, b=18 worked for me. So that means any multiples will also work - a=2, b=36; a=3, b=54; etc. (Of course not a=7, b=126, since that would break the condition that neither a nor b is divisible by 7).

What I did was to expand (a+b)^7 binomially, subtract out a^7+b^7, end up with:

7*a*b*(a^5+3*a^4*b+5*a^3*b^2+5*a^2*b^3+3*a*b^4+b^5)

I completed the fifth power, to end up with:

7*a*b*((a+b)^5 - 2*a^4*b - 5*a^3*b^2 - 5*a^2*b^3 - 2*a*b^4)

which is:

7*a*b*(a+b)*((a+b)^4 - a*b*(2*(a+b)^2-a*b))

Simplifying and factoring gives:

7*a*b*(a+b)*(a^2+ab+b^2)^2

This should be a multiple of 7^7, which means (a^2+ab+b^2) has to be a multiple of 7^3. I just tried b=18 (because it's the largest square below 7^3), and the other number turned out to be 1.

But there could be other combinations of numbers which also satisfy (a^2+ab+b^2) being a multiple of 343 (7^3). How do you eliminate that possibility (if at all)?

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

Re: BR Maths Corner-1

Postby Amber G. » 18 Sep 2016 07:51

Good work. Few comments:

yes, (a+b)^7-a^7-b^7 = 7ab(a+b)(a^2+ab+b^2)^2 :)
(Pattern, (a+b)^2-a^2-b^2=2ab; (a+b)^3-a^3-b^3=3ab(a+b);
(a+b)^5-a^5-b^5=5ab(a+b)(a^2+ab+b^2) ityadi..)
In fact for any prime p (>3) ; (a+b)^p-a^p-b^p has p, a,b,(a+b)(a^2+ab+b^2) as factors.
(This is easy to prove, as mentioned in the previous posts, if one substitute a=0 (or b=0), or (a+b)=0, or a=bw or a=bw^2 the expression comes out to be zero. Here w is cube root of 1 that is 1+w+w^2 = 0 and w^3=1.

(Thus for example (1+w)^7-1-w^7 = (-w^2)^7-1-w^7 (remember 1+w=-w^2 from 1+w+w^2=0)
or -w^14-1-w^7 = -w^2-1-w = 0 (remember w^3=1)) QED.
So factoring is actually very simple.

***
(18,1) works as a solution, as any multiple of those will too. This is same family of solutions.
There is another family (generate infinite for any one given above) which is again VERY easy to generate. Again that is trivial. (Hint: if (18,1) is solution, one get infinite more { Look it ONLY if you want to, It is rather trivial so you may be able to guess it right away } ===
(18, 243+1=244)

***
But there is another family of solution(s). Put in another way, there is/are other family of solution(s) even when b=1, Can one find it/them (without computer perhaps) in a systematic way.

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

Re: BR Maths Corner-1

Postby Amber G. » 18 Sep 2016 23:26

sudarshan wrote:
But there could be other combinations of numbers which also satisfy (a^2+ab+b^2) being a multiple of 343 (7^3). How do you eliminate that possibility (if at all)?


As I said before, there indeed is another combination of numbers. If one thinks the "right way" the answer is easy to guess, but it may be not obvious otherwise.

I will give a hint, to see if people like to find the theory by themselves, but I will give one example:
10,180 works (as pointed in S's post - any multiple of (1,18) will work)
but so is (10,153) will (check it out yourself ..

*****

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

Re: BR Maths Corner-1

Postby Amber G. » 23 Sep 2016 20:24

Some final comments on the above problem..

If we restrict ourselves to b=1, and a<243 we have two solutions, (18,1),(324,1).
(Of course, any multiple of both numbers is a solution, and also one can add 7^3=243 to any number and that will be a solution too.

Note that 324=18^2.

(Note that Hint I gave, (153,10) is same as (3240,10) because if you divide 3240 by 343 remainder is 153)

Basically the problem is to make students excited about modulo math. And just like there are three cube roots of 1 in complex numbers, there are three "cube roots' of 1 modulo 343.

For those who had no chance to study modular math in high-school or college, again any good book or this wiki article may be of interest.

https://en.wikipedia.org/wiki/Modular_arithmetic

One way to find the answer is to check that a^3==b^3 (mod 343) is a solution. You have to find that 18^3 == 1 (mod 343)

Theory here, if you have not read before, is quite interesting, and I will give a hint to read it in any standard higher math book, or this wiki article:
https://en.wikipedia.org/wiki/Euler%27s_theorem

So one way to do it to notice that phi(343)=6*7^2=98, so (anynumber --prime to 7)^98 ==1 (mod 343), one can find, for example, 2^98
(which looks hard but really easy to do with hand as 2^10=1024==-5 mod 343, 2^20==25, 2^40 ==625 == -61 etc)


Hope some find this of interest.

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

Re: BR Maths Corner-1

Postby SaiK » 02 Nov 2016 04:53

dunno where our fizzic dhaaga disappeared.. my searches didn't result in any.
However, I found the GDF fizzic dhaaga. I am taking this oppty in math dhaaga to call all gurus to visit GDF and answer few questions.

TIA

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

Re: BR Maths Corner-1

Postby Amber G. » 05 Nov 2016 22:49

x-post from Mangalyaan : ISRO's Mars Orbiter Mission thread. Interesting formula from Ramanujan regarding perimeter of an ellipse.

Amber G. wrote:Nowadays one just let a computer calculate the orbits but when we studied these there were not even calculators for us.. (as I tell my son, we used bamboo slide rules and stuffs like that :)). The path where there is only one body to worry about (like when MoM is close to earth, or Mars, or in between but far enough from both planets) -- aka elliptical orbits with "minor" perturbation are easier -- that's what astronomers did using these methods.

One rather interesting tidbit. There is no easy formula to calculate the length (perimeter) of an ellipse. One can use series expansion which is okay for computers but not that convenient when one does by hand. One of my favorite and remarkable formula comes from Ramanujan. He just writes the formula, does not explain it, does not even give a clue how it came to him but is fairly accurate. ( Don't worry for Mangalyaan orbit my approximation is within a few percentage)

The formula is:
perimeter (path) = pi((a+b)+3(a-b)^2/(10(a+b)+sqrt(a^2+b^2+14ab))) + small correction.
(See my previous post, a is AM, and b is GM of perigee and apogee)

Remarkably he gives the "correction" = 3ae^20/ 68719476736

As usual Ramanujan never explained his “empirical” method of obtaining this approximation, neither in his published work, nor in his Notebooks.. and kept many mathematician busy..(I still see papers trying to get insight in this approximation and numbers like 68719476736... How does one get that number ???.) (The formula is a final sentence of Ramanujan’s famous paper Modular Equations and Approximations to π, but he does not write anything else, and people who searched his notebooks did not find any clue what what his thinking!!

****

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

Re: BR Maths Corner-1

Postby Amber G. » 04 Apr 2017 12:12

(Could not see Physics Thread but Abrikosov was a mathematical Physicist too) Sad to see this news

NYTimes - Alexei Abrikosov, Nobel Laureate in Physics, Dies at 88 Image
Alexei Abrikosov, who shared the Nobel Prize in Physics in 2003 for important insights into how certain materials conduct electricity without resistance, died on Wednesday at his home in Sunnyvale, Calif. He was 88.

Happen to know him and learned a lot from him - (was a close friend of one of Math/physics guru) first time met in Delhi. (I Think he met his wife in Delhi around that time)

vnms
BRFite -Trainee
Posts: 99
Joined: 15 Aug 2016 01:56

Re: BR Maths Corner-1

Postby vnms » 07 Apr 2017 23:45

One colleagues kids is preparing for math Olympiad. Can anyone suggest a few online resources for this? Thanks in advance.

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

Re: BR Maths Corner-1

Postby Amber G. » 08 Apr 2017 07:48

^^^ Are they in US or India? Are they qualified for USAMO or InMO?
Some like a few good online courses/resources (for example WOOT (Worldwide Online Olympiad Training).. Depending on if you are in US or India, best is if you have good/inspiring coach..
***
(Time flies like anything .. Just realized it is about 20 years since I got interested in working with these bright students -- started when my eldest son participated and there very few people who were qualified and/or interested, I volunteered.)

If there is a good math person available to them, ask questions and work with old problems. There are books by T. Andreescu, Kiran. Kedlaya, P. Zeitz, Feng etc.. (Just google "IMO problems and solutions" - several books cover all the way from 70's to now) with problems and solutions with some tools/techniques/theory/methods not usually available in regular text-books).

Actually this dhaga (Math thread), if I may say so, is good resource. Look from very beginning. It has *many* good problems (many did appear in olympiad exams) with fun solutions.
***

vnms
BRFite -Trainee
Posts: 99
Joined: 15 Aug 2016 01:56

Re: BR Maths Corner-1

Postby vnms » 15 Apr 2017 01:21

Amber G. wrote:^^^ Are they in US or India? Are they qualified for USAMO or InMO?
Some like a few good online courses/resources (for example WOOT (Worldwide Online Olympiad Training).. Depending on if you are in US or India, best is if you have good/inspiring coach..
***
(Time flies like anything .. Just realized it is about 20 years since I got interested in working with these bright students -- started when my eldest son participated and there very few people who were qualified and/or interested, I volunteered.)

If there is a good math person available to them, ask questions and work with old problems. There are books by T. Andreescu, Kiran. Kedlaya, P. Zeitz, Feng etc.. (Just google "IMO problems and solutions" - several books cover all the way from 70's to now) with problems and solutions with some tools/techniques/theory/methods not usually available in regular text-books).

Actually this dhaga (Math thread), if I may say so, is good resource. Look from very beginning. It has *many* good problems (many did appear in olympiad exams) with fun solutions.
***

Thank you very much Amberji.

They are in the US. I'll pass on your information to my colleague.

Neshant
BRF Oldie
Posts: 3974
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby Neshant » 16 Apr 2017 13:51

Image

I need some help from you high rolling mathematicians as I'm stumped.

I have 8 points in blue from a set of points that forms the above graph.
4 blue points correspond to the point where the graph from a level position starts dipping.
4 blue points correspond to where the graph starts rising back up and leveling off.

I've kind of drawn the graph with perfectly straight lines.
But the red & blue points are actually more scattered than what's shown. i.e. its a signal
Nevertheless the points when connected with straight lines forms the graph shape shown reasonably well.

Lets call a set of 4 blue points :

X1, Y1
X2, Y2
X3, Y3
X4, Y4

Now here's the question :

How do i figure out the exact span of the dip shown in green. i.e. from edge to edge?

My algorithm can figure out the span to the nearest (X,Y) point on either side of the dip. But that's not accurate enough.
How do i interpolate between those 4 blue points on either side of the dip to figure out the exact span of the dip.

Any better way to determine the span of the dip or any other ideas welcome.

Dipanker
BRF Oldie
Posts: 2439
Joined: 14 May 2002 11:31

Re: BR Maths Corner-1

Postby Dipanker » 16 Apr 2017 20:30

I am no mathematician by any stretch but it seems to me you can solve this problem by finding the equation of 3 lines and then solving for 2 intersections of these lines and finally finding the distance between these intersection points.


1. find equation of line (L1) the two level points on either side of the the trough ( X1 Y4)

2. Find equation of the dipping line (L2) on left (X2,X3 etc.)

3. Find equation of the dipping line (L3) on right (y2,y3 etc.)

4. find intersection I1 of L1 and L2.

5. find intersection I2 of L1 and L3.

6. Find distance between I1 and I2


Note:
Since points are supposed to be scattered
1. In step 2 you can have 3 lines (X2,X3), (X2,X4), (X3,X4), so you will get 3 intersections with L1
2. Similarly in Step 3 you can have 3 different lines. (Y3,Y2), (Y3,Y1), (Y2,Y1)
3. This approach will give 3X3 solutions, you can pick the smallest/largest which you think is appropriate.
4. In step 2 and 3 you can also solve for parabolas (quadratic) passing through the 3 points if you think
that will be more appropriate. Then find the intersections of the parabolas with the level line. You will get one solution in this case.

O.k. I know this is two simplistic, but I told you I was not a mathematician!

vsunder
BRFite
Posts: 584
Joined: 06 Sep 1999 11:31
Location: Ulan Bator, Mongolia

Re: BR Maths Corner-1

Postby vsunder » 17 Apr 2017 23:29

One can perhaps re-phrase the problem as follows: Given ANY two sets E and F, (in your case E is say the set of 4 blue points to the left, F is the set of 4 blue points to the right), what is the HAUSDORFF distance between the two sets E, F? The Hausdorff distance is a measure of the largest separation between two sets. A way/algorithm of computing this distance and examples with pictures can be seen here:

https://en.wikipedia.org/wiki/Hausdorff_distance

This works in any metric space and is the preferred tool in many problems like in Computer vision problems. In effect better estimates of the separation can be made by choosing E, F wisely in your case. For example if you allow some red dots in E say, the Hausdorff distance will go up obviously, so you must exclude them.

Neshant
BRF Oldie
Posts: 3974
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby Neshant » 18 Apr 2017 08:47

Dipanker wrote:I am no mathematician by any stretch but it seems to me you can solve this problem by finding the equation of 3 lines and then solving for 2 intersections of these lines and finally finding the distance between these intersection points.


Sounds like a good idea.

Note:
Since points are supposed to be scattered
1. In step 2 you can have 3 lines (X2,X3), (X2,X4), (X3,X4), so you will get 3 intersections with L1
2. Similarly in Step 3 you can have 3 different lines. (Y3,Y2), (Y3,Y1), (Y2,Y1)
3. This approach will give 3X3 solutions, you can pick the smallest/largest which you think is appropriate.


I was thinking of doing a least squares algorithm to get a "line of best fit" from those dipping points. Ditto for the "level" region of the graph - which is jagged rather than perfectly level as drawn.

4. In step 2 and 3 you can also solve for parabolas (quadratic) passing through the 3 points if you think
that will be more appropriate. Then find the intersections of the parabolas with the level line. You will get one solution in this case.


Yes i had the vague notion of having an arc roughly fit through those points on the level & dip.
And then do some Calculus black magic to get the tangent to the arc.
But I have no clue how to derive the equation of an arc or parabola from x,y cartesian points.
Anyway this method would probably be slower than the method up top.

O.k. I know this is two simplistic, but I told you I was not a mathematician!


That is about the maximum level of math I can digest!
Thanks for your help.

Neshant
BRF Oldie
Posts: 3974
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby Neshant » 18 Apr 2017 08:54

vsunder wrote:One can perhaps re-phrase the problem as follows: Given ANY two sets E and F, (in your case E is say the set of 4 blue points to the left, F is the set of 4 blue points to the right), what is the HAUSDORFF distance between the two sets E, F? The Hausdorff distance is a measure of the largest separation between two sets. A way/algorithm of computing this distance and examples with pictures can be seen here:

https://en.wikipedia.org/wiki/Hausdorff_distance


Thanks, I will look up Hausdorff separation distance algorithm.

It seems mathematicians have solve all kinds of problems and have ready solutions for them.

But 99.9% of us have no idea these solutions even exists.

Dipanker
BRF Oldie
Posts: 2439
Joined: 14 May 2002 11:31

Re: BR Maths Corner-1

Postby Dipanker » 18 Apr 2017 21:07

Neshant wrote:I was thinking of doing a least squares algorithm to get a "line of best fit" from those dipping points. Ditto for the "level" region of the graph - which is jagged rather than perfectly level as drawn.


I had that in mind too but thought there were not enough points. But theoretically least square fit sounds like better option than my somewhat arbitrary approach.

Yes i had the vague notion of having an arc roughly fit through those points on the level & dip.
And then do some Calculus black magic to get the tangent to the arc.
But I have no clue how to derive the equation of an arc or parabola from x,y cartesian points.
Anyway this method would probably be slower than the method up top.


A second degree polynomial of the form a * x**2 + b * x + c ( parabola ) passing through 3 point can be analytically solved since you have 3 unknown (a,b,c) and you have 3 points giving you 3 equations to solve for a,b,c. In matrix notation this is equivalent to solving for X in AX = B i.e X = Inverse(A) *B.
Matrix A can be set up by having x**2 in first column, x in second column, and 1's in third column. B's are just y co-ordinates.

For a more general least square curve fitting the equation in matrix form is:

X = Inverse (transpose(A) * A) * transpose(A) * B

Finding equation of a tangent to a curve at any given point is easy as slope at any point on the curve is first derivative of the curve evaluated at that point and then using the point/slope formula for a line.
But in your case how will be you decide the point to evaluate the tangent at ?

Yes, least square curve fitting as opposed to least square line will be computationally somewhat more expensive as it would involve 2 extra matrix multiplication and 1 transpose operation. You can try both, the least square lines and the least square curve to see which gives you better solution.

Of course If you think your problem is akin to finding the Hausdorff_distance then that should give the best answer.

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

Re: BR Maths Corner-1

Postby Amber G. » 19 Apr 2017 05:45

vnms wrote:Thank you very much Amberji.

They are in the US. I'll pass on your information to my colleague.

You are welcome.
So I assume they are participating in USAMO. Good luck. I believe the test starts tomorrow (4/19 and 4/20). Just curious, how did they do in their AIME.
Keep in mind, if they have qualified for USAMO, it is quite an achievement. (Schools like MIT give quite a bit of weight for scores in AIME - in fact everyone I know who has been qualified for USAMO had no trouble getting into schools like MIT).

For people in US and India, if you know anyone who is bright in Math and Science, let them appear in AMC (in US open to *all* and good high schools regularly participate -- but many schools and parents do not know about it) or its equivalent in India. If you qualified you are invited for AIME (RMO in India) and USAMO (InMO in India) which selects the team for IMO.

FWIW: Here are some practice problems

***
Many problems posted by me here in Math dhaga are from (or inspired or based on) such competitions.

Just for fun, let me (re)post two problems from GDF Math dhaga as that problem has appeared in such a contest. (The solutions and/or hinrs are in GDF dhaga so don;t look there). This is a relatively "easy" problem as IMO problems go. (No calculators, computer searches are allowed)

-- There are three numbers. All are whole numbers (greater than 0, positive integers). If you multiply any two of them and subtract the third, you get a perfect power of 2. Find all such numbers.

-- Factor the number (5^1985-1) into product of three integers, each of which is greater than 10^60.

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

Re: BR Maths Corner-1

Postby Amber G. » 19 Apr 2017 11:13

Image
One of the professor who inspired me and many others to learn computers was a math/physics professor (In those days there were no "computer scientists) who was a pioneer to start computer science education in India.

Professor Harry D Huskey, an Honorary Fellow of the Computer Society of India, founder of IIT Kanpur Computer Center, passed away on April 9, 2017, at the age of 101 at Santa Cruz, California. (See wiki entry for him for back ground)

Like many students then my first interaction with computers was 60's in IIT Kanpur. I learned to program in FORTRAN and enjoyed it.

Kanpur Indo American Programme (KIAP) in 60's -- the task of assisting India to set up an Institute of Technology at Kanpur. Professor Huskey lead a team to establish a computer centre at IIT/Kanpur. IBM 1620 arrived at IIT Kanpur in 1963. Y. (Prof. Huskey is at bottom right).
Image

Like many good things, KIAP died in 71 or soon after when USA foolishly supported murderers in Bangaladesh. US/India relationship took such a nose drive that even good programs which benefitted all came to an end.

A nice write-up about him is from the computer science museum in Mountain View, California near Google campus. (Link: http://www.computerhistory.org/atchm/harry-huskey-2013-chm-fellow/)

I am glad that many of IITK people were able to meet him recently as he remembered his India days very fondly. Here is a tribute by Dr Rajaraman.
link

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

Re: BR Maths Corner-1

Postby Amber G. » 20 Apr 2017 05:40

Okay, This was day one of USAMO (and USAJMO) (US Math olympiad and US Junior Math Olympiad for high school and Junior High students.
Since the first day of the contest is over and it is past 7PM local time, we are allowed to discuss problems now.
(For those who are not familiar, there are three problems given each day, time 4.5 hours - no calculators, computers etc)

Also din't I mention that that brf math dhaga is a good resource :) !... As I said..
Amber G. wrote:
You are welcome.
So I assume they are participating in USAMO. Good luck. I believe the test starts tomorrow (4/19 and 4/20).

***
*** Many problems posted by me here in Math dhaga are from (or inspired or based on) such competitions.

.


If one solved the problem at given at the top of this page one would have an easy time solving prob #2 (which curiously appeared for USAJMO -- easy enough for Junior High-schoolers :) (In my opinion, it is easier than the one discussed on the top of this page having similar ideas :))

Here is the problem: Try it for fun -

Consider the equation

[(3x^3+xy^2)(x^2y+3y^3)=(x-y)^7]
(a) Prove that there are infinitely many pairs (x,y) of positive integers satisfying the equation.
(b) Describe all pairs (x,y) of positive integers satisfying the equation


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

Re: BR Maths Corner-1

Postby Amber G. » 20 Apr 2017 06:29

Let me also post the prob #1 which is ought to be even easier :)

Given a and b are two relatively prime integers (both > 1 ) prove that there are infinite pairs (a,b) such that (a^b+b^a) is divisible by (a+b).

Neshant
BRF Oldie
Posts: 3974
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby Neshant » 20 Apr 2017 10:52

I was watching a documentary on the computer built by MIT for NASA for the first manned landing on the moon.

Computers of the day were huge and they had the task of shrinking it down into something the size of a briefcase to fit it on board the space craft.

Check it out :


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

Re: BR Maths Corner-1

Postby Amber G. » 21 Apr 2017 00:16

I posted two problems from this years USA(J)MO - just for perspective, here is one problem from India's National Math olympiad, this year -

Problem is relatively easy (2nd problem) as InMO problems go,

Given n >= 0 is an integer and all the roots of
x^3 + a x + 4 - ( 2 *2016^n = 0)
are integers. Find all possible values of a

Vayutuvan
BRF Oldie
Posts: 9705
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 23 Apr 2017 02:44

vsunder wrote:One can perhaps re-phrase the problem as follows: Given ANY two sets E and F, (in your case E is say the set of 4 blue points to the left, F is the set of 4 blue points to the right), what is the HAUSDORFF distance between the two sets E, F? The Hausdorff distance is a measure of the largest separation between two sets. A way/algorithm of computing this distance and examples with pictures can be seen here:


While I think this is the best bet, first Neshant has to come up with a separating plane (in this case a line) that separates the points into two sets. May be he can by eyeballing and drawing a line between those two sets. Any line will do. So a vertical line right in the middle of the trough, for example.

Dipanker
BRF Oldie
Posts: 2439
Joined: 14 May 2002 11:31

Re: BR Maths Corner-1

Postby Dipanker » 23 Apr 2017 23:23

Vayutuvan wrote:
While I think this is the best bet, first Neshant has to come up with a separating plane (in this case a line) that separates the points into two sets. May be he can by eyeballing and drawing a line between those two sets. Any line will do. So a vertical line right in the middle of the trough, for example.


Given the nature of the problem i.e. presence of a trough in the middle, the partitioning the points into two sets can be done by topologically sorting the points from left to right on x coordinate and then picking two points with min. y coordinates the left one (and all the points preceding it) belonging to the left set and the right one ( and all the points following it) belonging to the right set.

Of course that will be the ideal case assuming a convex bottom! Heuristical treatment will be needed if the bottom turns out to be concave i.e. there are points with higher y coordinates in the middle of two min. y coordinate points. But may be the problem domain is restricted to only convex bottom for the trough?

Neshant
BRF Oldie
Posts: 3974
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby Neshant » 24 Apr 2017 02:29

Yes these calculations to determine width have to be done at high speeds. It puts a limit on how many floating point operations (i.e. divisions or multiplication of decimal numbers) I can do for each measurement.

Finding the separating plane gets back to the question of where does the right & left set terminate.

What I drew was an idealized picture of the signal. The actual signal is somewhat jagged and the "trough" may look like an inverted (jagged) plateau/mountain of varying depths with over-shoots on edges. This is the pitfall of passive rather than active detection. But that's the sensor i have to work with. I can run a smoothing filter on the signal, but all that's going to do is degrade the accuracy further.

On top of that, particles of dust and other goodies flying by might momentarily distort the signal in random ways. My algorithm has to watch for that and reject that signal set.

Some other thoughts i had : Since the separating plane may not be easy to consistently define, I was thinking of collecting a set of 8 signals very rapidly, calculating widths of 8 sets as best i can and then doing some kind of Bell Curve statistical magic on it. The position of the material being detected will not have changed during the time taken to acquire those 8 signal sets.

Due to variation in separating plane identification from one set to another and other stuff, some widths might be slightly longer and others slightly shorter. But hopefully some good old statistics will yield the actual width answer to some degree of accuracy.


Return to “Technology & Economic Forum”

Who is online

Users browsing this forum: No registered users and 6 guests