advanced math problem

>>So does this mean there's only one solution?
I don't know.

EDIT: Deleted incorrect information generated by bug in program.

When set to resolve to three decimal places the program now returns:
-->New closest match: (3.00, 1.00)
Accuracy: 0.000065169

Obviously this accuracy is still not zero and assumably if we go far enough we will find a more correct solution. Going beyond 0.001 granuality with brute force will take some time. Anyone got a super computer?

The program does not take in 4 of the six lines so it is entirely possible that we are missing something.

>I guess brute force can solve anything.
Only when programming, only some of the time, and its tacky.

>Hopefully we can find an algebraic solution.
I agree!

Can the original poster please at least confirm or deny if there is a nice solution to this enigma?

Thanks for the response guys, had to get some sleep myself.

The correct answer should be (3,1)

Will look over your answers once I've eaten some breakfast :)

I really cranked up the granuality and severly limitied the search and came up with this:

Code:

-->New closest match: (2.9999905500000454000000000, 1.0000484590037266000000000) Accuracy: 0.000000001

And that is about as good as you are going to get.

Quote:

Originally posted by golfinguy4
To the original poster, have you ever studied earthquakes? If not, you just found the same procedure that is used to find the epicenter of earthquakes. Different stations make measurements and draw circles according to the data. Using the intersections of the circles, one is able to find the epicenter of the earthquake.

This is a very interesting suggestion which I will look into straight away :)

Great job anonytmouse.

I am almost certain that there is only 1 solution to each set of parameters.

I think there is an elegant solution to the problem.

Sure is nice to have computers when you can't find an elegant solution.

If I figure out the pretty solution, I will post.

-SavageAg

1 Attachment(s)

>I am almost certain that there is only 1 solution to each set of parameters.

I agree. Part of the trouble is that I was working with laasunde's
figures which are very approximate. I will paste the correct figures for (3,1) which might help.

Code:

3.1622776601683793319988935444327 to point one 7.0710678118654752440084436210485 to point two 3.9087901516970959120095500766165 time difference 3.1622776601683793319988935444327 to point one 9.4868329805051379959966806332982 to point three 6.3245553203367586639977870888662 time difference -->New closest match: (3.000, 1.000) Accuracy: 0.000000000

If you watch the program the difference reduces as it gets closer to the result. This strongly suggests there is a solution. Certainly the program could be changed to take a homing approach. This would be quite efficient.

I think the key is to work out how one triangle is solved. We can solve it for the straight line situation. If the point is not on this straight line it gets longer. We need to work out the equation for this.

Thoughts

I wish that my alegbra skills were better. I have not used those skills for almost 20 years, so they are rusty.

There is a set of formula's (Heron's forumula's) which are good for this problem. They allow you to find the height of a triangle and also the distance between the line to the height and the end of the triangle along the base, just from the lengths of the sides. (I hope that made sense). If it did not make sense look at the following web site (If you care).

http://jwilson.coe.uga.edu/emt725/Heron/Heron.html

We know one side (10) and the other two sides can be expressed in terms of x (where x is time/distance to the first node). I put it all together to work it out, but making it evaluate to x=? is pretty much beyond my algebra skills. It should be possible to make a formula to find x given what we are given.

Once you get x it is very easy to find the coordinates to the transmitter.

I am still interested to see an elegant solution, but not sure I am going to be able to be the provider.

anonytmouse, please don't take my words to mean that I was not impressed by your solution. In the real world, you are able to answer the question quickly and correctly for any input. I just like pretty solutions to problems.

-SavageAg

What happened laasunde? Did you find a solution. Please don't leave us frustrated without a solution.
I have another idea.

I went back to how I originally guessed at the answer. My guess was reasonably close so I thought if I follow the same thought process there might be something in it.

First, I came up with the straight line solutions. That is, if the point was on the line 1 to 2, then where would it be. The equation for this is simply 2x + time difference = total distance (10).

So the two straight line solutions for lines 1 to 2 and 1 to 3 are roughly:
straigth line 1 to 2 = 3.05
straight line 1 to 3 = 1.85

Next I dragged out the lines. For example, take line 1 to 3 and drag its point(y=1.85) out to 3.05. We can visualise that due to the acuter angle that the line from point one will have to come out on to reach this point that it will gain more length proportionally than the line to point 3. We know that this will throw off the timing so we have to drag the point closer to station one.

We can do the same thing with the 1 - 2 line and we can get a pretty good approximation without explicitly using any maths.

Therefore, I propose that if the solution can be solved visually (albeit roughly) with just these two numbers then it can also be solved mathematically with just these two numbers.

The maths is beyond me but at this moment I believe it is possible. It all depends on the angles as the acuter the angle the closer the point will need to become.

P.S Now, as we only have four numbers, we need a brute force equation solver. I'll have a look on the web.

P.P.S That Heron's equation sounds promising when it claims to be able to figure out triangles from their perimeters but my maths are no where near good enough to use it.

Sorry for not replying to this thread but I've been away for the weekend with no Internet connection.

Just like to thank everyone for their brilliant contribution.

anonytmouse program looks like a possible solution, I do however agree with other users that it would be better if it's possible to get a smarter and maybe even quicker solution.

Will re-read the whole thread and post back my thoughts.

Will you ever know the answer?

laasunde,

Will you ever know the answer to the problem you outlined?

Is that something you were doing in school? If so, will the professor give the elegant answer?

Did you use the code given as your answer? If not, did you find a better way to solve the problem?

I think it would be nice to answer these questions for the people who took the time to work on your problem.

savageag,

This is not an assignment given at school so I wont get an elegant answer by a professor. It's might be a solution to part of a project Im doing at uni.

I very much appreciate the excellent response I've gotten from many people on this forum. It's given me lots of ideas to work on.

At the moment Im working on a possible solution which I will post on here once I get it right. Because of my lacking math skills this is taking more time than expected.

Please dont give up on me yet :)

Quote:

Originally posted by laasunde
Sorry for not replying to this thread but I've been away for the weekend with no Internet connection.

NO INTERNET CONNECTION? WHAAAAA???? IS THAT POSSIBLE. lol,
jus kidding...:p :p

Hello everyone.

Hope you guys havnt given up on me yet. I think I have a solution now that might work, not sure if it's any better than anonytmouse suggestion but it's a bit different. Must admit I have not tested it very thoroughly yet but it seems to work on the 'few' test runs I've done.

My idea is this, using the time difference between receiver1 and receiver2 I can calculate an arc of difference possible points between the two points. These samples I then place inside an array. The I do the same thing between receiver1 and receiver3. Now I have two arc's that at one point meet, which is the coordinate of the sender.

I apologise for the lack of comments in the code.

Would appreciate any comments or advice.

Code:

//main.cpp #include <iostream> #include <cstdlib> #include "ratio.h" using namespace std; int main(int argc, char *argv[]) { double time1=0; double time2=0; double time3=0; cout << endl << "Enter the time registered at receiver1 (0,0) : "; cin >> time1; while (!cin) { cout << endl << "Not a number! Enter time for receiver1 again : "; cin.clear(); cin.ignore(0x7FFFL,'\n'); cin >> time1; } cout << endl << "Enter the time registered at receiver2 (0,10) : "; cin >> time2; while (!cin) { cout << endl << "Not a number! Enter time for receiver2 again : "; cin.clear(); cin.ignore(0x7FFFL,'\n'); cin >> time2; } ratio receiver1(time2 - time1, 0); receiver1.calculatePath(); cout << endl << "Enter the time registered at receiver3 (10,0) : "; cin >> time3; while (!cin) { cout << endl << "Not a number! Enter time for receiver3 again : "; cin.clear(); cin.ignore(0x7FFFL,'\n'); cin >> time3; } ratio receiver2(time3 - time1, 1); receiver2.calculatePath(); if (receiver1.interception(receiver2)) { cout << endl << "intercpection" << '\t'; cout << "x = " << receiver1.getInterceptionX() << "\ty= " << receiver1.getInterceptionY() << endl << endl;; } else { cout << endl << "no interception...failed" << endl << endl; } system("PAUSE"); return 0; }

Code:

class ratio { public: ratio(double delay, int pos); ~ratio(); void calculatePath(); bool interception(ratio &obj); inline double getInterceptionX() { return collisionX; } inline double getInterceptionY() { return collisionY; } inline double getPositionX(int counter) { return coordinates[X][counter];} inline double getPositionY(int counter) { return coordinates[Y][counter]; } private: void showarray(); double getA(); double getB(); double getC(); double getPos(); double solve(double a, double b, double c); bool isAnswerCorrect(double value); double delay; static const int X = 0; static const int Y = 1; static const int GRID_SIZE = 10; static const double RESOLUTION = 0.05; static const int POINTS = (int) (GRID_SIZE / RESOLUTION); static const double SPEED = 1.0; static const double UNCERTAINTY = 0.002; double coordinates[2][POINTS+1]; double index; double collisionX; double collisionY; int posistion; };

Code:

#include "ratio.h" #include <iostream> #include <cmath> using namespace std; ratio::ratio(double d, int pos) : delay(d * SPEED), posistion(pos) {} ratio::~ratio() {} void ratio::calculatePath() { int counter=0; for (index = 0; index <= (GRID_SIZE); index += RESOLUTION ) { if (posistion == 0) { coordinates[X][counter] = getPos(); coordinates[Y][counter] = index; } else if (posistion == 1) { coordinates[X][counter] = index; coordinates[Y][counter] = getPos(); } counter++; } // showarray(); } void ratio::showarray() { for (int counter=0; counter <= POINTS; counter++ ) cout << "X"<<counter<<" = " << coordinates[X][counter] << '\t' << "Y"<<counter<< " = " << coordinates[Y][counter] << endl; } double ratio::getPos() { double a = getA(); double b = getB(); double c = getC(); // cout << '\t' << a<<"x^2 " << b << "x " << c << endl; return solve(a, b, c); } double ratio::getA() { return (pow((GRID_SIZE / delay), 2) - 1); } double ratio::getB() { return -2 * (( ( (GRID_SIZE*GRID_SIZE) - pow(delay,2)) / (2 * delay) ) * (GRID_SIZE / delay)); } double ratio::getC() { double temp = ( (GRID_SIZE*GRID_SIZE) - pow(delay,2) ) / (2 * delay); return pow (temp, 2) - pow(index,2); } double ratio::solve(double a, double b, double c) { // cout << a << '\t' << b << '\t' << c << endl; double x1 = (-b - sqrt( pow(b,2) - (4*a*c) )) / (2*a); double x2 = (-b + sqrt( pow(b,2) - (4*a*c) )) / (2*a); // cout << "x1= " << x1 << "\tx2 = " << x2 << endl; if ( isAnswerCorrect(x1) ) return x1; else if (isAnswerCorrect(x2)) return x2; else return 0; } bool ratio::isAnswerCorrect(double answer) { double left = sqrt( pow((GRID_SIZE - answer),2) + pow(index,2) ); double right = delay + sqrt( pow(answer,2) + pow(index,2) ); // cout << endl << "left = " << left << "\tright = " << right << '\t'; if ( fabs(right - left) < UNCERTAINTY ) return true; else return false; } bool ratio::interception(ratio &obj) { for (int index=0; index < POINTS; index++) { for (int index2=0; index2 < POINTS; index2++) { if (fabs(getPositionX(index) - obj.getPositionX(index2)) < UNCERTAINTY) { if ( fabs(getPositionY(index) - obj.getPositionY(index2)) < UNCERTAINTY) { collisionX = getPositionX(index); collisionY = getPositionY(index); return true; } } } } return false; }

To some extent, that is still brute force isn't it laasunde?

EDIT: Could you write a small overview of the code? I see some quadratic formula (or something like that), and some arrays, but I can't see what's really happening.

bennyandthejets,

I agree it's kind of a 'brute force' algorithm. However my suggestion only checks along two arc's while anonytmouse suggestion checks the whole area. Like I said above I havnt tested this enough so for all I know my suggestion is much slower than anonytmouse code. My code is more of a first draft and probably has lots of possible areas of improvements speed wise and bug wise.

I will get back to you with the math behind the whole thing with maybe a picture to illustrate.