Help on hw...

[signaly]

Help on homework...

I'm doing homework and i am stuck on one problem and was hoping if one of you guys could help. Okay for the problem... You have 2 tins one can hold 4qts and one holds 9 and you want to get 6 qts. Okay here's the tricky part. You can not measure a specific amount in the answer meaning if you said pour 1 qt in, bla bla bla you can not do that. Please help.

 

[Robert]

this one is wrong

Spoiler

Fill the 4 qts and pour them in the 9qts tin, now you have 4qts in the 9qts tin and and empty 4qts tin. Fill the 4 qts again and pour it in the 9qts, now 4+4=8 and 8>9 so you still have 1qt on the 4qt tin, now fill the 9 qts tin and pour that to the 4qts tin so you have full 4qts tin and 6qts on your 9qts tin.

Thats it

 

[badmephisto]

thats a pretty nice little problem. I dont want to spoil the problem for you by just giving you the answer, that would be unfair.
You just have to devise a sequence of "pourings" from one tin to another. Also try to think about how you could reduce the problem. You need 6 in the end. What are all the ways to get 6 at the end? 5+1 ? Thats a possibility, but analyze it more closely... it wont take you too long to convince yourself that thats impossible. Maybe 4+2 ? You can always get 4 because of the 4qts tin... So now you only need to somehow get 2 into the 9qts. How could you do that?

edit: by the way thats not how I solved it, I just went through all possible things you can do that make remote sense and at the end it just worked out But the above is a more methodological way, or a general approach that you could follow in these types of problems.

 

[signaly]

Okay I'll try that. =D

 

[Robert]

spoil the problem for you by just giving you the answer, that would be unfair.

whops, i thought thats what he wanted

 

[badmephisto]

spoil the problem for you by just giving you the answer, that would be unfair.

whops, i thought thats what he wanted

Robert I dont even see how your solution works...
you pour 4 and 4 into 9. How do you get 1 into the 4qts again?

 

[Robert]

yeah, its totally wrong, i dont know what i was thinking.

Spoiler

So its pour 4 twice to the 9 tin to get 8, then pour the 4 again to get 3 on the 4 tin, empty the 9 and pour the 3 you had and then 4, pour another 4 so you have 2 on the 4, empty the 9 and pour the 2 you had in the 4 tin, then fill the 4 tin and pour it to the 9 tin to get the 6.

sorry for the wrong answer

 

[davegocube]

I had that as an interview question once.

 

[blgentry]

Come on didn't you see Die Hard With A Vengance? That was one of my favorite parts!

Robert's second answer works, but takes a lot more steps than another solution. It's interesting that there are several ways to do this.

Brian.

 

[badmephisto]

Come on didn't you see Die Hard With A Vengance? That was one of my favorite parts!

Robert's second answer works, but takes a lot more steps than another solution. It's interesting that there are several ways to do this.

Brian.

hmm what is it? It certainly escaped me

 

[hait2]

robert's answer sure is confusing

have you actually tried to solve this yourself? these types of 'riddles' basically solve themselves for you
just pour something into other and see what #s you get

here's the sequence i came up with in the span of about 10 seconds
0-9
4-5
0-5
4-1
0-1
1-0
1-9
4-6

giving you a 6 in the end. probably nowhere close to optimal

now THAT would make for an interesting problem:
given a container that holds N units and another that holds M(M>=N), you have to get Q in one of the containers where Q<=M. How do you find the optimal # of pourings to determine Q? (given the usual cant-measure-except-using-N-or-M stuff)

edit: tbh i have no idea. ill simplify the question for myself: given N and M volumes, can you get Q for all Q <=M? i.e. can u get 0, 1,2...Q-1,Q, no matter how many moves it takes you?

nvm you can't do the 2nd part so the first clearly doesn't have a sol'n unless Q is made such that it's possible to get.. sigh

 

[Robert]

Maybe its confusing how i explained it.

My sequences would be like

________________
| 9 qts ..| ..4qts ....|
----------------------
|.. 0 .....|.... 4 ......|
|.. 4 .....|.... 4 ......|
|.. 8 .....|.... 4 ......|
|.. 9 .....|.... 3 ......|
|.. 3 .....|.... 4 ......|
|.. 7 .....|.... 4 ......|
|.. 9 .....|.... 2 ......|
|.. 2 .....|.... 4 ......|
|.. 6 .....|.... 0 ......|
-----------------------
Or something like that, im not so good explaining

 

[cmhardw]

here's the sequence i came up with in the span of about 10 seconds
0-9
4-5
0-5
4-1
0-1
1-0
1-9
4-6

giving you a 6 in the end. probably nowhere close to optimal

I use an algorithm for these:
1) fill the smaller container
2) pour the contents of the smaller container into the larger
3) repeat until the larger container is full
4) empty the larger container
5) pour the contents, if any, of the smaller container into the larger
5) start at step 1 again

This cycles through different numbers, and eventually returns to two empty containers. This method isn't optimal, and usually I deviate from it if I can intuitively think of a way to get to the number I need quicker. But I call this Hardwick's proposal, that if a number is reachable with two containers, then the above algorithm will find it before the containers both empty again.

now THAT would make for an interesting problem:
given a container that holds N units and another that holds M(M>=N), you have to get Q in one of the containers where Q<=M. How do you find the optimal # of pourings to determine Q? (given the usual cant-measure-except-using-N-or-M stuff)

edit: tbh i have no idea. ill simplify the question for myself: given N and M volumes, can you get Q for all Q <=M? i.e. can u get 0, 1,2...Q-1,Q, no matter how many moves it takes you?

nvm you can't do the 2nd part so the first clearly doesn't have a sol'n unless Q is made such that it's possible to get.. sigh

Add to this which numbers are and are not reachable with the two containers, and the optimal lengths to get to those that are reachable, and I am very interested. I want to start looking at this too to be honest. I also think that this problem has been solved fully already, most likely by the Anicent Chinese who did so much work with modular arithmetic and number theory.

Chris

 

[Swordsman Kirby]

Well, for containers of x and y capacity, the only numbers that can be formed are of the form

k*gcd(x,y) <= x+y (you can't get more than filling up the two containers to the brim)

where k is a positive integer.

This can be shown by noting that you should only fill the large one when it's empty and empty the small one when it's full (and pour from the large into the small). Then, assuming that x>y (without loss of generality), the number of times we fill up the x container and empty out the y container is given by the expression:

ax-by=d < x+y

where a and b are non-negative integers. Note that the gcd(a,b) must divide ax-by, so it must also divide d. Therefore, d is a multiple of gcd(a,b) as well.

General way of solving for a certain number of liters (containers of X,y: X>y (X=y is stupid)):

1. Fill X.
2. Pour X into y.
3. Empty y if it's full.
4. Repeat 2-3 until there's nothing left in X.
5. Repeat 1-4 until you get your desired amount.

The Euclidean algorithm is how you figure out how many times you'll fill X and empty y. Check out this example: Containers of size 87 and 5, making a desired amount of 3.

a = b*c + d
b = d*e + f
d = f*g + h
...

87 = 5*17 + 2
5 = 2*2 + 1
2 = 2*1 + 0

Now, since the last equation leaves no remainder, the right-most term on the previous line is the gcd(87,5): gcd(87,5) = 1

Now, let's look at the equation:

5 = 2*2 + 1, leads to:
1 = 5 - 2*2
1 = 5 - 2*(87 - 5*17)
1 = 35*(5) - 2*(87)
3 = 105*(5) - 6*(87)

Oh darn, I swapped it around. Whatever. This is just the opposite of my solution: filling up the smaller one and pouring it into the larger one until it's full. For this, you fill up the 5 container 105 times and empty the 87 container 6 times.

A particular solution to the diophantine equation 5x + 87y = 3 is (x,y) = (105,-6). The general solution is: (105 + 87/gcd(87,5)t,-6 - 5/gcd(87,5)t) where t is an integer. Then, we can choose t = -2 to get a solution of (-69,4). This would mean we fill up the 87 container 4 times and empty out the 5 container 69 (lulz) times.

Ugh, this is ugly, ask for clarification if you don't understand.

most likely by the Anicent Chinese who did so much work with modular arithmetic and number theory.

I'm Chinese, but by no means Ancient.

 

[hait2]

ah
brings back memories of algebra 1

i don't really like alg/calc i did well in them.. i just don't want to do it.. anymore. stats is more fun i think

but yeah once you re-word the problem into basic modular arithmetic, it becomes fairly easy to solve, since the solution is iterative

 

[signaly]

Okay thanks i tried the other answer but it was wrong however i do understand how to do it now, thanks. =D

 

[blgentry]

Come on didn't you see
Robert's second answer works, but takes a lot more steps than another solution. It's interesting that there are several ways to do this.

hmm what is it? It certainly escaped me

It's the same one that Hait2 typed out above:

Fill 9
pour 9 into 4
empty 4
pour 9 into 4 yielding 1 quart in the 9
empty 4
pour remaining 1 quart from 9 into 4
fill 9
pour 3 from 9 into 4 as this is all it will now hold. (3 + 1 = 4)
This leaves 6 in the 9 quart container.

Brian.