INFOSYS FOUNDATION TRAINING PROGRAM (FTP) SOLUTION FOR LAB-GUIDE ASSIGNMENT PROBLEM SOLVING AND LOGIC BUILDING- part-2

TOPIC 1 : COMPUTATIONAL PROBLEM SOLVING

1.1 COMPUTATIONAL PROBLEM SOLVING AND ALGORITHM

ASSIGNMENT 1.1.1 : PROBLEM SOLVING EXERCISES ( part-b )

1. In an objective type programming contest, following are the rules

a. It will have multiple rounds.

b. In each round, every participant will get a set of 10 question out of which

one question is marked as star question (The toughest one).

c. The participant will get the next set, only if 50% of the questions are

marked correctly in the previous round or he attempted the star question

correctly. Otherwise he will be out of the contest.

It is found that in each round 50% of the participants are not able to attempt 50%

of the questions correctly but one out of those 50% participants, attempts the

star question correctly.

If only 4 participants are left for the 5th round what was the number of

participants in the first round?

SOLUTION :

Let the students appeared for 1st round be = x

Students appearing for the 2nd round :

Since half of them made for the 2nd round, which constitute = x / 2

and 1 candidate who attempted star question

So, total students who made for the 2nd round are = x/ 2 + 1 = (x + 2)/ 2

Students appearing for the 3rd round :

Since half of the previous round students made for the 3rd round, which constitute = ( (x + 2)/ 2 )/2

and 1 candidate who attempted star question

So, total students who made for the 2nd round are =  ( (x + 2)/ 4 ) + 1 = (x + 6)/ 4

Students appearing for 4th round :

Since half of the previous round students made for the 3rd round, which constitute = ( (x + 6)/ 4 )/2

and 1 candidate who attempted star question

So, total students who made for the 2nd round are =  ( (x + 6)/ 8 ) + 1 = (x + 14)/ 8

Students appearing for 5th round :

Since half of the previous round students made for the 3rd round, which constitute = ( (x + 14)/ 8 )/2

and 1 candidate who attempted star question

So, total students who made for the 2nd round are =  ( (x + 14)/ 16 ) + 1 = (x + 30)/ 16

Since it is given that the number of students appeared for the 5th round are =  4

This implies the expression we got for the 5th round i.e. (x + 30)/ 16 becomes = 4

i.e.                                                   (x + 30)/ 16 = 4

                                                         (x + 30 ) = 64

                                                            x = 64 - 30

                                                               x = 34

Since we assumed ' x ' to be the number of students present during the 1st round, which came out to be = 34. It means there were total of 34 students present in the 1st round.

2. A farmer had a lazy son. The farmer wanted his son to work in the farm. So he offered that the son will work for 50 days, for each day the son works, he will get 10 rupees, for each day he will not work, he need to pay back 15 rupees to his father. At the end of 50 days, when the son counted his income, it turned out that he had not got anything. How many days did the son actually worked?

SOLUTION :

Let the son worked for =  x days
money earned for x days = 10x

No. of days on which he didn't work = (50 - x)
Money he lost for days he didn't work = 15 ( 50 - x )

It is given in that the money he earned balances the money he paid back, which means :

                                                      10x = 15 ( 50 - x )
                                                       10x = 750 - 15x
                                                            25x = 750
                                                           x = 750/25
                                                              x = 30
Since we assumed ' x ' to be the number of days for which son worked, which came out to be = 30 days. Therefore, Son worked for 30 days.

INFOSYS FOUNDATION TRAINING PROGRAM (FTP) SOLUTION FOR LAB-GUIDE ASSIGNMENT PROBLEM SOLVING AND LOGIC BUILDING

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.