TOPIC 1 : COMPUTATIONAL PROBLEM SOLVING
1.1 COMPUTATIONAL PROBLEM SOLVING AND ALGORITHM
ASSIGNMENT 1.1.1 : PROBLEM SOLVING EXERCISES
1 . The King ordered his servants to fill up his treasury. Each of the 3 servants, had to go to the treasury, count how much gold coins there was at that moment, and then triple it and leave. But then the King felt sorry for them and thought that he should probably reward the servants in some way, so he let each of them take 1 gold coin out before leaving. Once again the King had a good luck. He collected exactly 500 gold coins in the treasury. How much gold coins did he have before the order.
SOLUTION
Let initially coins be = x
a servant has to make thrice of them, which means, coins should be = 3x
and a servant is allowed to take 1 coin, which leave the total coins to = ( 3x - 1 )
Next servant comes and does the same thing of making the count of coins to 3-times, which makes the present count to = 3 ( 3x - 1 )
and when he take 1-coin out , then the present count becomes = ( 3 ( 3x - 1 ) - 1 )
Finally the 3rd servant comes and make the present count to thrice again making it =
3 ( 3 ( 3x - 1 ) - 1 )
and when he also takes 1-coin out, the total count becomes = ( 3 ( 3 ( 3x - 1 ) - 1 ) -1 )
At last, it was found that the total count of the coins = 500
which means our expression ( 3 ( 3 ( 3x - 1 ) - 1 ) -1 ) = 500
solving this expression step by step :
( 3 ( 9x - 3 - 1) - 1 ) = 500
27x - 12 - 1 = 500
27x -13 = 500
27x = 513
x = 513 / 27
x = 19
since ' x ' is the number of coins initially present in the treasury. It means 19 coins were initially present in the treasury.
2. John decided to start working. He was hired on the following terms: during 30 days, for each day John works, he gets 6 dollars, for each day he doesn't work,he pays back 9 dollars. At the end of the month, when they counted his wages, it turned out that he had not got anything. How many days did John actually work?
SOLUTION :
Let the number of days for which Jhon worked be = x
This implies, the number days for which Jhon didn't work = 30 - x
Jhon gets 6 $ for each day he works
therefore, his total wages for his working days become = 6x
Jhon has to pay back 9 $ for the day he don't work
therefore, he has to pay back total of = 9( 30 - x )
Since Jhon gets nothing at the end of the month as the money he has to pay back balances the money he earned, which means :
6x = 9( 30 - x )
6x = 270 - 9x
15x = 270
x = 270 / 15
x = 18
Since, we assumed ' x ' to be the number of days for which Jhon worked, and it comes out to be 18 days for which Jhon worked for the company.
3. Smith's boss proposed to pay him in the following way: "See, there is some money in the purse. Every day I'll add 5 dollars to it, and then you'll take out half of what's in it”. Three days later it turned out that there were6 dollars left in the purse. How much did Smith get for three days' work ?
SOLUTION :
Let the amount of money present in the purse initially be = x
1st day The boss added 5 $ to the purse and the total amount becomes = x + 5
The employee took half of the total amount , which means, he took = ( x+ 5 ) / 2.............(i)
Money left behind in the purse = (x + 5 ) - ( x + 5 ) /2
2nd day The boss added 5 $ again to the purse, which makes the total amount present in the purse to = 5 + ( x + 5 )/ 2 = (10 + x + 5) / 2 = ( x + 15 )/ 2
The employee took half of the amount present in the purse , which means, for this time, he took-
( x + 15 )/ 2*2 = ( x + 15 )/ 4................................(ii)
Money left behind in the purse = ( x + 15 )/ 2 - ( x + 15 )/ 4 = ( x + 15 )/ 4
3rd day The boss added 5 $ again to the purse, which makes the total amount present in the purse to = 5 + ( x + 15 )/ 4 = ( x + 35 ) / 4
The employee took half of the amount present in the purse , which means, for this time, he took-
( x + 35 ) / 4 *2 = ( x + 35 ) / 8..............................(iii)
Money left behind in the purse = ( x + 35 ) / 4 - ( x + 35 ) / 8 = ( x + 35 ) / 8
Since money left in the purse on 3rd day = ( x + 35 ) / 8
and it is given that on 3rd day money present in the purse = 6 $
which means :
( x + 35 ) / 8 = 6
x + 35 = 48
x = 13
Since, we assumed ' x ' as the money present in the purse initially, which means there were 13 $ present in the purse initially.
We've to find out the amount earned by the employee on 3rd day, which we can calculate by adding (i), (ii) and (iii) expressions above as :
( ( x+ 5 ) / 2 ) + ( ( x + 15 )/ 4 ) + ( ( x + 35 ) / 8 )
Putting 13 in place of x, we get the expression as :
( ( 13 + 5 ) / 2 ) + ( ( 13 + 15 ) / 4) + ( ( 13 + 35 ) / 8)
( 18/ 2 ) + (28 / 4 ) + (48 / 8 )
9 + 7 + 6
22
This implies the total of 22 $ earned by the employee. and If we see the amount only for 3rd day, it comes out to be : ( x + 35 ) / 8 = ( 13 + 35 ) / 8 = (48 / 8 ) = 6
4. Two friends who have an eight-quart jug of water wish to share it evenly. They also have two empty jars, one holding five quarts, the other three. How can they each measure exactly 4 quarts of water ?
SOLUTION :
Step-1:
First of all water from 8-quart jug is poured into 3-quart jar, so now the values are :
8-quart jug = 5-quart water
3-quart jar = 3-quart water
5-quart jar = 0-quart water
Step-2 :
Now, water from 3-quart jar is poured into 5-quart jar, so now the values are :
8-quart jug = 5-quart water
3-quart jar = 0-quart water
5-quart jar = 3-quart water
Step-3:
Now again, water from 8 quart jug is poured into 3-quart jar, so now the values are :
8-quart jug = 2-quart water
3-quart jar = 3-quart water
5-quart jar = 3-quart water
Step-4:
Now, water from 3-quart jar is poured into 5-quart jar, Notice this time, since the 5-quart jar is left with only 2-quarts of capacity, therefore, 3-quart jar will be able to pour only 2-quarts of water, leaving 1-quart behind. So now the values are :
8-quart jug = 2-quart water
3-quart jar = 1-quart water
5-quart jar = 5-quart water
Step-5:
Now, the whole of water from 5-quart jar is poured back into 8-quart jug, which will set the values to :
8-quart jug = 7-quart water
3-quart jar = 1-quart water
5-quart jar = 0-quart water
Step-6:
Now, pour the water from 3-quart jar into 5-quart jar, making the values to :
8-quart jug = 7-quart water
3-quart jar = 0-quart water
5-quart jar = 1-quart water
Step-7:
Now again, fill the 3-quart jar by pouring water from 8-quart jug, making the values to :
8-quart jug = 4-quart water
3-quart jar = 3-quart water
5-quart jar = 1-quart water
Step-8:
Now, fill this 3-quart of water from 3-quart jar to 5-quart jar, and see it yourself that we have successfully divided 8-quarts of water into equal halves, so that both friends can get exactly 4-quarts of water. And the values can finally be seen as :
8-quart jug = 1-quart water
3-quart jar = 3-quart water
5-quart jar = 4-quart water
5. The bin packing problem is an example of a wide set of problems. The task is to find how many set sized bins are required to hold a number of differently sized boxes. How many bins (10 units high) are required to contain the following boxes (1,3,4 and 5 units high) ?
SOLUTION :
Since, we've to put 1,3,4 and 5 units high boxes into 10 units high bins.
As can be seen, we can put
1.) 1,4 and 5 units high boxes into 10 units high bin( all these boxes completely fit into bin w/o leaving any space behind )
2.) Now we're left with only 3 unit high box, which we've to put it into another 10 unit high bin, as we've no other option.
SOLUTION
Let initially coins be = x
a servant has to make thrice of them, which means, coins should be = 3x
and a servant is allowed to take 1 coin, which leave the total coins to = ( 3x - 1 )
Next servant comes and does the same thing of making the count of coins to 3-times, which makes the present count to = 3 ( 3x - 1 )
and when he take 1-coin out , then the present count becomes = ( 3 ( 3x - 1 ) - 1 )
Finally the 3rd servant comes and make the present count to thrice again making it =
3 ( 3 ( 3x - 1 ) - 1 )
and when he also takes 1-coin out, the total count becomes = ( 3 ( 3 ( 3x - 1 ) - 1 ) -1 )
At last, it was found that the total count of the coins = 500
which means our expression ( 3 ( 3 ( 3x - 1 ) - 1 ) -1 ) = 500
solving this expression step by step :
( 3 ( 9x - 3 - 1) - 1 ) = 500
27x - 12 - 1 = 500
27x -13 = 500
27x = 513
x = 513 / 27
x = 19
since ' x ' is the number of coins initially present in the treasury. It means 19 coins were initially present in the treasury.
2. John decided to start working. He was hired on the following terms: during 30 days, for each day John works, he gets 6 dollars, for each day he doesn't work,he pays back 9 dollars. At the end of the month, when they counted his wages, it turned out that he had not got anything. How many days did John actually work?
SOLUTION :
Let the number of days for which Jhon worked be = x
This implies, the number days for which Jhon didn't work = 30 - x
Jhon gets 6 $ for each day he works
therefore, his total wages for his working days become = 6x
Jhon has to pay back 9 $ for the day he don't work
therefore, he has to pay back total of = 9( 30 - x )
Since Jhon gets nothing at the end of the month as the money he has to pay back balances the money he earned, which means :
6x = 9( 30 - x )
6x = 270 - 9x
15x = 270
x = 270 / 15
x = 18
Since, we assumed ' x ' to be the number of days for which Jhon worked, and it comes out to be 18 days for which Jhon worked for the company.
3. Smith's boss proposed to pay him in the following way: "See, there is some money in the purse. Every day I'll add 5 dollars to it, and then you'll take out half of what's in it”. Three days later it turned out that there were6 dollars left in the purse. How much did Smith get for three days' work ?
SOLUTION :
Let the amount of money present in the purse initially be = x
1st day The boss added 5 $ to the purse and the total amount becomes = x + 5
The employee took half of the total amount , which means, he took = ( x+ 5 ) / 2.............(i)
Money left behind in the purse = (x + 5 ) - ( x + 5 ) /2
2nd day The boss added 5 $ again to the purse, which makes the total amount present in the purse to = 5 + ( x + 5 )/ 2 = (10 + x + 5) / 2 = ( x + 15 )/ 2
The employee took half of the amount present in the purse , which means, for this time, he took-
( x + 15 )/ 2*2 = ( x + 15 )/ 4................................(ii)
Money left behind in the purse = ( x + 15 )/ 2 - ( x + 15 )/ 4 = ( x + 15 )/ 4
3rd day The boss added 5 $ again to the purse, which makes the total amount present in the purse to = 5 + ( x + 15 )/ 4 = ( x + 35 ) / 4
The employee took half of the amount present in the purse , which means, for this time, he took-
( x + 35 ) / 4 *2 = ( x + 35 ) / 8..............................(iii)
Money left behind in the purse = ( x + 35 ) / 4 - ( x + 35 ) / 8 = ( x + 35 ) / 8
Since money left in the purse on 3rd day = ( x + 35 ) / 8
and it is given that on 3rd day money present in the purse = 6 $
which means :
( x + 35 ) / 8 = 6
x + 35 = 48
x = 13
Since, we assumed ' x ' as the money present in the purse initially, which means there were 13 $ present in the purse initially.
We've to find out the amount earned by the employee on 3rd day, which we can calculate by adding (i), (ii) and (iii) expressions above as :
( ( x+ 5 ) / 2 ) + ( ( x + 15 )/ 4 ) + ( ( x + 35 ) / 8 )
Putting 13 in place of x, we get the expression as :
( ( 13 + 5 ) / 2 ) + ( ( 13 + 15 ) / 4) + ( ( 13 + 35 ) / 8)
( 18/ 2 ) + (28 / 4 ) + (48 / 8 )
9 + 7 + 6
22
This implies the total of 22 $ earned by the employee. and If we see the amount only for 3rd day, it comes out to be : ( x + 35 ) / 8 = ( 13 + 35 ) / 8 = (48 / 8 ) = 6
4. Two friends who have an eight-quart jug of water wish to share it evenly. They also have two empty jars, one holding five quarts, the other three. How can they each measure exactly 4 quarts of water ?
SOLUTION :
Step-1:
First of all water from 8-quart jug is poured into 3-quart jar, so now the values are :
8-quart jug = 5-quart water
3-quart jar = 3-quart water
5-quart jar = 0-quart water
Step-2 :
Now, water from 3-quart jar is poured into 5-quart jar, so now the values are :
8-quart jug = 5-quart water
3-quart jar = 0-quart water
5-quart jar = 3-quart water
Step-3:
Now again, water from 8 quart jug is poured into 3-quart jar, so now the values are :
8-quart jug = 2-quart water
3-quart jar = 3-quart water
5-quart jar = 3-quart water
Step-4:
Now, water from 3-quart jar is poured into 5-quart jar, Notice this time, since the 5-quart jar is left with only 2-quarts of capacity, therefore, 3-quart jar will be able to pour only 2-quarts of water, leaving 1-quart behind. So now the values are :
8-quart jug = 2-quart water
3-quart jar = 1-quart water
5-quart jar = 5-quart water
Step-5:
Now, the whole of water from 5-quart jar is poured back into 8-quart jug, which will set the values to :
8-quart jug = 7-quart water
3-quart jar = 1-quart water
5-quart jar = 0-quart water
Step-6:
Now, pour the water from 3-quart jar into 5-quart jar, making the values to :
8-quart jug = 7-quart water
3-quart jar = 0-quart water
5-quart jar = 1-quart water
Step-7:
Now again, fill the 3-quart jar by pouring water from 8-quart jug, making the values to :
8-quart jug = 4-quart water
3-quart jar = 3-quart water
5-quart jar = 1-quart water
Step-8:
Now, fill this 3-quart of water from 3-quart jar to 5-quart jar, and see it yourself that we have successfully divided 8-quarts of water into equal halves, so that both friends can get exactly 4-quarts of water. And the values can finally be seen as :
8-quart jug = 1-quart water
3-quart jar = 3-quart water
5-quart jar = 4-quart water
5. The bin packing problem is an example of a wide set of problems. The task is to find how many set sized bins are required to hold a number of differently sized boxes. How many bins (10 units high) are required to contain the following boxes (1,3,4 and 5 units high) ?
SOLUTION :
Since, we've to put 1,3,4 and 5 units high boxes into 10 units high bins.
As can be seen, we can put
1.) 1,4 and 5 units high boxes into 10 units high bin( all these boxes completely fit into bin w/o leaving any space behind )
2.) Now we're left with only 3 unit high box, which we've to put it into another 10 unit high bin, as we've no other option.
No comments:
Post a Comment