Wednesday, June 18, 2008

Two Interesting "Bathroom" Problems!

A Problem I conceived in the Bathroom.

Consider a tub that hold a Volume V(i) litres of water intially at temperature T(i).We pour hot water at temperature T(h) at the rate of v(h) litres per second. We have a facility of removal of water from the tub at any rate (even infinite). It is required to have V(f) litres of water at temperature T(f) at the end. Give a method to find out the optimum rate at which water must be removed from the tub to reach the final state as quickly as possible.

Assumptions: Some of these might be very unrealistic :P
1) The total heat in the hot water and cold water is conserved at all times.There is no loss whatsoever. (Ha ha ha!)
2) There is NO difference in the specific heats of hot and cold water.
3) As soon as the hot water in poured in or water from the tub is poured out, the remaning water has uniform temperature everywhere.That is there is no loss of thermal equilibrium at any point.

In addition it can be considered whether it is better to start with lots of cold water (that is greater than V(f)) or very little cold water (less than V(f)).


2. Well..this is an extension of the 3 priests and 3 cannibals problem.

So on a bank of a river there are n priests and n cannibals.The cannibals would eat the priets if at any side the number of cannibals exceeds that of the priests.There is a boat in the river than can carry p people at a time.The boat, of course, can't run without atleast 1 person.Give a method to transport all the n cannibals and priests alive to the other side.
Of course the problem demands as less a value of p as possible.Also for a particular p the number of trips must be minimized.

It is quite interesting to see that this problem can be easily solver for p=2 and n=3.The question is can it be done for p=2 and any n? If not, what is the least value of p for a particular n to make it possible.

Here is one interesting idea.This problem can be modelled as a decision tree problem with (p+1) children of each node.

3 comments:

Ero-Sennye said...

well for the first question Provesh. According to your problem statement, we can draw out a few quick conclusions. 1) the temperature of the bath tub water can only rise, whatever we do. 2) the volume of the water can increase at a finite rate, but decrease spontaneously without loss of time. 3) Temperature can only increase when volume of hot water is added.

Now, consider the following situation. Suppose we cannot remove any water, then there will exist a unique V(i) such that when water is added at v(h) and T(h), the net result T(f) , V(f) is obtainable. Lets call this value of V(i) as V_o. Now, any V(i) less than V_o would in your question, never lead to (V(f) , T(f)). Also, any value of V(i) greater than V_o would require us to pour more hot water proportional to time, to bring about the temperature change that we require. Now, suppose that we actually had V_o when we started, and all your rules apply. It is easy to see, that we cannot take out any water now, and also, for this time situation, this is the most optimal condition. Next, we pour some more hot water. This new state now is V(t), T(t). The good thing about this state is that this also satisfies the fact that it is also the optimal state to be in! We can't afford to take out any water, any also, had we had anything more than V(t), we would have had to add more hot water, which would have taken more time.

Well, I don't know if am making myself clear but I hope you understand. The solution will be to take out all water from V(i) to make it V_o. Then, simply pour the hot water. However, if V(i) < V_o, then whatever we do, we will never have exactly V(f) and T(f).

Pravesh said...

Indeed! Well I understand that in the present setting this does lead to a dissection of the problem. I will have to think of circumventing this to get a new and good problem.

Thanks man :) .. I will love to have some ideas for the second problem.

Ero-Sennye said...

I pretty much believe (:P) that the answer is min. { 4, greatest-integer(n/2)+1 } . We know very simply that 4 would suffice for any n. It would mean, 2P + 2C one way, and 1P+1C coming back. Now, how did I get greatest-integer(n/2)+1 ? I think, that we should consider the problem as trying to keep a quantity = number of priests - number of cannibals as >=0 on both side. Also, an important observation is that on both sides, initially this quantity is 0. Now, its impossible for any solution if we didn't have a very important clause - that is, this quantity P-C can be negative only when P = 0 . Hence, its apparent that the only solution that can be constructed must use this clause. Once we use this clause, we know we have an excess of cannibals exists on one side, the destination say. To counter this, we must therefore send atleast that many priests to the other side, and at once. Say this is possible, and this number, to maximize our solutions, is 'p', the same notation that you use. Now, since we say we have a balance of P and C on the destination side, we have a similar problem to what we started out with. Hence, we must have to use the clause of having P-C negative, with P = 0 some point in time again. However, we understand a very important thing. this situation differs from the initial conditions in that the number of priests on the destination side is not = 0 . Hence, the only way has to be, to apply the clause on the source side sometime in the future, i.e., we are left with no P and only C on the source side. For this to happen, we have to remove all the priests once again simultaneously, and hence we can take 'p' priests away, and slowly bring the cannibals to complete our job. Now, in all this, we realised, we used our special clause twice, to safely transport 2*p +- 1 number of P and 2*p +- 1 number of C, i.e, p P and C in the beginning of the job and p P and C at the end of the job. Say this leaves us with a finite number n - 2*p P and C to transport in the middle of the job. Now, this is the same question, with only one important difference, that the special clause cannot be used since on both source and destination, there exist a finite number of P. But, without using this clause, we can Never make a net transport of P and C without violating P-C>=0. Hence, the only other way, is to have n = 2*p - 1. The one, comes because the boat cannot be ridden by itself. Hence, the argument, is complete. Ofcourse, it needs to be alot more rigorous than this, but I think this should be close to the real arguments.