Math Problem: You have 2 pipes...

[maziwanka]

i think xUCIxDaiSHi method of solving this problem is better than m4h's.

both are "clever" brute force methods.

 

[chuckywang]

Originally posted by: JustAnAverageGuy

Originally posted by: chuckywang
I cannot believe this thread has over 60 responses. IT'S A FREAKIN' TWO VARIABLE EQUATION!!!!

You have one equation and two variables. You know the two variables must be positive integers, so you don't have an infinite number of answers. Now, from these two pieces of information, you have to determine which set of integers works for the given equation. Hard? Don't think so.

Ok solve this one if you're soooo good at it.

You need to make a pipe of a length of 140 meters.

You are given pipes of lenths 2.8m and 1.3m. Assume is takes no length to put the pipes together.

How many pipes of each type do you need?

Solve.

Dude, could you pick easier numbers? The first thing that I noticed was that 140 is a multiple of 28. So it would take 50 pipes of length 2.8m to make 140 meters.

 

[SaturnX]

It's already been mentioned before, but yeah all this is a 1st Order Linear Diophantine equation, whipped up a solution with the extended euclidean algorithm to generate a general solution for ALL integers solutions, applied the limit that both x, and y must be greater than 0, thus you arrive at the solution you have.

basically you can start off with the following:

1x + 0y = 3.9
0x + 1y = 5.9

Use the EEA and you're set.

--Mark

 

[DrPizza]

Here's a problem posted in highly technical a few weeks back...
Here are ninety 25-digit numbers. (the first digits are allowed to be zero)
It is PROVEN that for ANY set of 90 such numbers (25 digits long) there must be at least two different subsets (actually there are many more) such that the sum of the numbers in one subset is equal to the sum of the numbers in the other subset. For all of you thinking that NDee's problem was a high school level problem (well, actually solving it by brute force was, but not the explanation for a more elegant solution), this problem is 2nd grade level... provided they get big calculators. All you need to do is add up some numbers on this list a "few" times until you get the same sum using different numbers. I GUARANTEE that there are several correct answers. I'll bet there isn't a person in this forum who can find them. C'mon - there are only 90 numbers here.
20480135385502964448038 3171004832173501394113017 5763257331083479647409398 8247331000042995311646021
489445991866915676240992 3208234421597368647019265 5800949123548989122628663 8496243997123475922766310
1082662032430379651370981 3437254656355157864869113 6042900801199280218026001 8518399140676002660747477
1178480894769706178994993 3574883393058653923711365 6116171789137737896701405 8543691283470191452333763
1253127351683239693851327 3644909946040480189969149 6144868973001582369723512 8675309258374137092461352
1301505129234077811069011 3790044132737084094417246 6247314593851169234746152 8694321112363996867296665
1311567111143866433882194 3870332127437971355322815 6814428944266874963488274 8772321203608477245851154
1470029452721203587686214 4080505804577801451363100 6870852945543886849147881 8791422161722582546341091
1578271047286257499433886 4167283461025702348124920 6914955508120950093732397 9062628024592126283973285
1638243921852176243192354 4235996831123777788211249 6949632451365987152423541 9137845566925526349897794
1763580219131985963102365 4670939445749439042111220 7128211143613619828415650 9153762966803189291934419
1826227795601842231029694 4815379351865384279613427 7173920083651862307925394 9270880194077636406984249
1843971862675102037201420 4837052948212922604442190 7215654874211755676220587 9324301480722103490379204
2396951193722134526177237 5106389423855018550671530 7256932847164391040233050 9436090832146695147140581
2781394568268599801096354 5142368192004769218069910 7332822657075235431620317 9475308159734538249013238
2796605196713610405408019 5181234096130144084041856 7426441829541573444964139 9492376623917486974923202
2931016394761975263190347 5198267398125617994391348 7632198126531809327186321 9511972558779880288252979
2933458058294405155197296 5317592940316231219758372 7712154432211912882310511 9602413424619187112552264
3075514410490975920315348 5384358126771794128356947 7858918664240262356610010 9631217114906129219461111
3111474985252793452860017 5439211712248901995423441 7898156786763212963178679 9908189853102753335981319
3145621587936120118438701 5610379826092838192760458 8147591017037573337848616 9913237476341764299813987
3148901255628881103198549 5632317555465228677676044 8149436716871371161932035
3157693105325111284321993 5692168374637019617423712 8176063831682536571306791

 

[DrPizza]

p.s. For anyone wishing to solve the above problem by brute force - go for it. Sissies. 100 to 1 you'll fail.

 

[jman19]

Originally posted by: DrPizza
p.s. For anyone wishing to solve the above problem by brute force - go for it. Sissies. 100 to 1 you'll fail.

Heh, there's no doubt about it that anyone here who tries to do this via brute force will fail.

 

[Howard]

Originally posted by: jman19

Originally posted by: Howard
We need MadRat to come in here and wax philosophical on the meaning of a pipe.

OMG, please, GOD, do not let MadRat come into another math related thread. He crapped all over the .999 = 1 thread with his "belief" about what infinity is :roll:

I'm glad somebody got the reference.

 

[chuckywang]

Originally posted by: DrPizza
p.s. For anyone wishing to solve the above problem by brute force - go for it. Sissies. 100 to 1 you'll fail.

I think I posted my thoughts on this problem. The professor is hedging his bets. He knows nobody will be able to solve this problem. The computational complexity is simple too high. This is precisely why some cryptography algorithms work.

 

[jman19]

Originally posted by: chuckywang

Originally posted by: DrPizza
p.s. For anyone wishing to solve the above problem by brute force - go for it. Sissies. 100 to 1 you'll fail.

I think I posted my thoughts on this problem. The professor is hedging his bets. He knows nobody will be able to solve this problem. The computational complexity is simple too high. This is precisely why some cryptography algorithms work.

Yeah, you're right about crypto algos... it's not that they're unbreakable theoretically, but realistically, they cannot be solved using brute force methods in a reasonable amount of time.

 

[Brutuskend]

Pipe B?

 

[vtqanh]

Solution:

rewrite the equation as 39x + 59x = 2120. Any pair of x,y that satisfies this equation will satisfy the original one as well.

Find the greatest common divisor of (59,39):
59 = 39 * 1 + 20
39 = 20 * 1 + 19
20 = 19 * 1 + 1
1 = 1 * 1 + 0
-> gcd(59,39) = 1;
Now we need to find a and b such that: 1 = a*39 + b*59
From the next-to-last step above: 1 = 20 - 19 = 20 - (39 - 20) = 2*20 - 39 = 2*(59-39) - 39 =
= -3*39 + 2*59
-> The initial solution x0, y0 for the above equation is x0 = -3*2120 = 6360 y0 = 2 * 2120 = 4240
Now any (x,y) that satisfies: x = x0 + 59*t and y = y0 + 39*t (where t is an integer) will be the solution of the above equation. However, we need x and y to be greater than 0. With that constraint, we have:
-6360 + 59*t > 0 ----> t > 107.8
4240 + 39*t > 0 ----> t < 108.7
Since t is an integer, t must be 108
With t = 108, we have x = 12, y = 28. This is a unique solution since we have a unique value of t

 

[DrPizza]

Originally posted by: vtqanh
Solution:

rewrite the equation as 39x + 59x = 2120. Any pair of x,y that satisfies this equation will satisfy the original one as well.

Find the greatest common divisor of (59,39):
59 = 39 * 1 + 20
39 = 20 * 1 + 19
20 = 19 * 1 + 1
1 = 1 * 1 + 0
-> gcd(59,39) = 1;
Now we need to find a and b such that: 1 = a*39 + b*59
From the next-to-last step above: 1 = 20 - 19 = 20 - (39 - 20) = 2*20 - 39 = 2*(59-39) - 39 =
= -3*39 + 2*59
-> The initial solution x0, y0 for the above equation is x0 = -3*2120 = 6360 y0 = 2 * 2120 = 4240
Now any (x,y) that satisfies: x = x0 + 59*t and y = y0 + 39*t (where t is an integer) will be the solution of the above equation. However, we need x and y to be greater than 0. With that constraint, we have:
-6360 + 59*t > 0 ----> t > 107.8
4240 + 39*t > 0 ----> t < 108.7
Since t is an integer, t must be 108
With t = 108, we have x = 12, y = 28. This is a unique solution since we have a unique value of t

it's been so long - what's the name of the bolded algorithm?
btw, great answer!

edit: it's sad to realize that the best of my students would benefit from seeing such elegant solutions to problems such as find a gcd, but they're lumped into the same class as the regular level students and thus are taught "on your calculator, try dividing by 17... now 16... now 15... " - I'm happy if 100% of the students even *know* what a gcd is.

 

[vtqanh]

Originally posted by: DrPizza

edit: it's sad to realize that the best of my students would benefit from seeing such elegant solutions to problems such as find a gcd, but they're lumped into the same class as the regular level students and thus are taught "on your calculator, try dividing by 17... now 16... now 15... " - I'm happy if 100% of the students even *know* what a gcd is.

That is true for the lab sessions that I'm teaching as well. Good students dont want to go to class because we're teaching stuff (for everybody in the class) that is too simple for them to be worth the effort coming to class.
Btw, the bolded algorithm is the Euclidean algorithm

 

[Lord Evermore]

Dangit. I started out thinking it needed to be multiplied by 10 on both sides. And that the common divisor needed to be found. But I'd get lost after that.

 

[TheLonelyPhoenix]

Originally posted by: Brutuskend
Pipe B?

Damn Brutus, you'll just take any excuse to link to that pic again, won't you?

 

[Brutuskend]

Originally posted by: TheLonelyPhoenix

Originally posted by: Brutuskend
Pipe B?

Damn Brutus, you'll just take any excuse to link to that pic again, won't you?

Pretty much.

 

[maziwanka]

Originally posted by: vtqanh
Solution:

rewrite the equation as 39x + 59x = 2120. Any pair of x,y that satisfies this equation will satisfy the original one as well.

Find the greatest common divisor of (59,39):
59 = 39 * 1 + 20
39 = 20 * 1 + 19
20 = 19 * 1 + 1
1 = 1 * 1 + 0
-> gcd(59,39) = 1;
Now we need to find a and b such that: 1 = a*39 + b*59
From the next-to-last step above: 1 = 20 - 19 = 20 - (39 - 20) = 2*20 - 39 = 2*(59-39) - 39 =
= -3*39 + 2*59
-> The initial solution x0, y0 for the above equation is x0 = -3*2120 = 6360 y0 = 2 * 2120 = 4240
Now any (x,y) that satisfies: x = x0 + 59*t and y = y0 + 39*t (where t is an integer) will be the solution of the above equation. However, we need x and y to be greater than 0. With that constraint, we have:
-6360 + 59*t > 0 ----> t > 107.8
4240 + 39*t > 0 ----> t < 108.7
Since t is an integer, t must be 108
With t = 108, we have x = 12, y = 28. This is a unique solution since we have a unique value of t

its been more than a year since i've used number theory but this method is excellent. great job dude.

 

[SithSolo1]

2+2=5

god I hate math. Someone help the poor soul, not all of us are math wizzes.

 

[ndee]

Originally posted by: MercenaryForHire

Originally posted by: ndee

Originally posted by: MercenaryForHire

Originally posted by: Mermaidman
I think we need a second relationship. Are you sure the teacher didn't say that A+B=40?

If we had two equations:
3.9A+5.9B=212
A+B=40

Then it's much easier

No, it's solvable without it.

I've been sitting on a proof without "guess the integer" as well, but I'd like to see if ndee can do his own damned homework first.

- M4H

As I told you, I got the answers, it's not about solving the problem, it's about the way to get there. I don't grasp that. Told ya you couldn't do it... TARD BOY!

Try scrolling up. :roll:

- M4H

Try READING. I didn't want a bruteforce method. And RaynorWolfcastle is right, it's the Diophantine Equation and our teacher gave us information about it but I just don't get it. That's all.

 

[ndee]

Originally posted by: DrPizza

Originally posted by: BigJ
Wheres DrPizza when you need him.

I'm right here. I looked at the problem for a few moments... had a brain fart.
For those of you claiming it's an easy problem, other than brute force, it's a difficult problem.
I believe it falls under Diophantine equations... been wayyy too long for me to recall. But, I do recall it's got something to do with relatively prime...

Good luck on the explanation... I'm just taking a time out from writing a paper, otherwise I'd read enough to recall how to do these. BTW, to those claiming these problems are easy, NDEE, why don't you give them a similar problem to solve...

Incidentally (since I'm not reading through all the idiots calling other people idiots in this thread) I'd like to point out that since they both end in .9, to have an integral length, there needs to be a multiple of 10 total pipes. Thus, for those looking for a 2nd equation, you could have A+B=30, A+B=40, A+B=50, etc.


Hmmm... someone above DID provide a link to 1st order Diophantine equations... I followed the link, it all came back to me Well, some of it.

NDee, follow the link
Reasonably simple explanation.

Thanks DrPizza, gonna read that link

 

[konakona]

vtqanh needs to be added to this list : http://forums.anandtech.com/me...rd1=what+are+you+known

 

[dym]

that's algorithm is named Diaphantine (not sure that i spelled it right)
And it is taught in Discrete Math classes.

 

[SaturnX]

The algorithm in bold, like I mentioned several posts above the solution posted, is the Euclidean Algorithm, or in this case a derivation of it being the Extended Euclidean Algorithm. The equation is a Diophantine equation, not the alogorithm.

--Mark

 

[MercenaryForHire]

Originally posted by: ndee

Originally posted by: MercenaryForHire

Originally posted by: ndee

Originally posted by: MercenaryForHire

Originally posted by: Mermaidman
I think we need a second relationship. Are you sure the teacher didn't say that A+B=40?

If we had two equations:
3.9A+5.9B=212
A+B=40

Then it's much easier

No, it's solvable without it.

I've been sitting on a proof without "guess the integer" as well, but I'd like to see if ndee can do his own damned homework first.

- M4H

As I told you, I got the answers, it's not about solving the problem, it's about the way to get there. I don't grasp that. Told ya you couldn't do it... TARD BOY!

Try scrolling up. :roll:

- M4H

Try READING. I didn't want a bruteforce method. And RaynorWolfcastle is right, it's the Diophantine Equation and our teacher gave us information about it but I just don't get it. That's all.

All you said was that you wanted us to solve it. I solved it, and a lot faster than anyone using a Diophantine equation. Applicable to every single class of equations? No. A hell of a lot faster? Yes. Solved? Totally. As long as there's a method to the madness (calcuations and not just number-crunching) an elegant brute-forcing is a valid proof in every university class I've ever seen.

And it's good to see that you're finally admitting to not just "not getting it" - but still "not getting it" after many explanations have been posted. Now unless you're in front of me at waist-height, how about you shut your mouth? :roll:

- M4H

 

[ndee]

Originally posted by: MercenaryForHire
All you said was that you wanted us to solve it. I solved it, and a lot faster than anyone using a Diophantine equation. Applicable to every single class of equations? No. A hell of a lot faster? Yes. Solved? Totally. As long as there's a method to the madness (calcuations and not just number-crunching) an elegant brute-forcing is a valid proof in every university class I've ever seen.

And it's good to see that you're finally admitting to not just "not getting it" - but still "not getting it" after many explanations have been posted. Now unless you're in front of me at waist-height, how about you shut your mouth? :roll:

- M4H

After the "normal" explanations, I asked for the diophantine way, (I also said no brute-force)etc. Anyway, I'm done with you. After you had the numbers, just assume thing is alot easier then to come up with them by yourself.

Have a nice day.