The 3 little pigs have recently established their own construction company.
Their new client is the wolf, now a real estate entrepreneur. The wolf would like to contract the pigs to build a house. The pigs provide the following conditions on their work:
Under the 3 pigs' conditions, what is the least amount of money (in $) the wolf can invest to complete this project?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
I found it easier with the number work to divide the house into 144 units (LCM of 9, 12 & 16), so A does 16 units per day, B 12/day, C 9/day. After that, much as other solutions.
The correct answer is 2800. Pigs B and C working together have productivity 1/12 + 1/16 = 7/48 house/per day. Together they work X days, and 1 day alone when the other has a day off. So, we have 7X/48 + 1/12 + 1/6 = 1. X = 41/7 = 6 days, and total cost is 6 *(250 +150) + 150 + 250 = 2800.
Log in to reply
I did not consider that exactly 2 pigs work on the house each day
"To pay the least possible amount of wages, the wolf should employ pigs B and C as long as possible." Not true, as you subsequently demonstrate. This is an integer program. Pig A needs to work at least 2 days. And because of how the prices work out, substituting one day of Pig A for Pig C works. But so does substituting two days of Pig A for two days of Pig B.
Maximizing the B,C combination is nothing more than a heuristic. Once that fails to produce an optimal solution, you have to test all the substitution patterns.
Log in to reply
This assumption is derived only from the first assumption: Exactly 2 pigs work on the house each day (so that the other pig can call for help if something happens).
You can see that I am dealing with each assumption subsequently.
I used Excel to list and test the possible combinations. Pig A works 1 day. Pig B works 2 days. Pig C works 12 days. The house is completed for $2650.
Log in to reply
This is not possible because EXACTLY 2 pigs must work EACH DAY.
There is just 1 error in your solution. You stated "To avoid being charged another full day's wage (which is $250+$150=$400 at least, larger than any pig's individual daily wage), we may substitute pig B or C by pig A for 1 day." This is incorrect. To avoid being charged an extra day, only pig C may be substituted. If pig B we're to be substituted the house would remain incomplete at the end of the day by 1/48.
Log in to reply
I meant to show whether pig B or pig C should be substituted based on calculations. Before calculations, we don't know if it is possible to substitute pig B by pig C, to complete the work at a lower wage surge.
What, if the oldest and the middle work together for one day, the oldest and the youngest work together for one day, and the middle and the youngest work together for four days? The total cost will then be 2700 dollars.
As shown above, 7/144 of the work will remain under your arrangement.
Let A be the eldest pig, B be the middle pig, and C be the youngest pig. Then for one day:
A & B builds 1 4 4 2 8 of the house for $600
A & C builds 1 4 4 2 5 of the house for $500
B & C builds 1 4 4 2 1 of the house for $400
By the pigs' conditions, each pig must have at least 1 day off and 2 pigs must work on the house each day, so there must be at least 1 day of A & B, 1 day of A & C, and 1 day of B & C, for a total of 1 4 4 7 4 of the house built at $1500.
This leaves 1 4 4 7 0 of the house remaining, which can be done minimally in 3 more days by either 2 more days of B & C and 1 day of A & B, or by 2 more days of A & C and 1 more day of B & C, both scenarios costing the wolf $1400 more. Either way, the total cost is $1500 + $1400 = $2900 .
After the house was built, the wolf discovered that two of the pigs substituted unauthorized straw and sticks for bricks, and confronted each of them at their private residences rather huffily ...
Haha...so this riddle is actually a prologue of the fable tale then. :)
Log in to reply
Yes, the wolf decides he doesn't want to pay these extortionate rates for a house that is partly brick, partly sticks and partly straw. He goes to ask for a reduction on the rates to make up for the mixed quality workmanship, but the pigs refuse because he was the one that demanded such strange working conditions. He takes this the wrong way. the morale of the story is that he should have just paid the extra $500 for a brick house from the eldest pig in the first place.
This is how I did it too.
Let x be the number of days pigs A , B work together, y be the number of days pigs A , C , and z be the number of days pigs B , C , respectively.
Since the pigs need a day off some time in this period, x , y , z can't be 0. Otherwise, such pig would work throughout the whole construction length.
In order to avoid the full-day charge, we have to calculate the way this job is complete within full total days, and the work portions done in each day will equal to 9 1 , 1 2 1 , and 1 6 1 for pigs A , B , C respectively. That is, x , y , z will be non-negative integers as in this Diophantine equation:
( 9 1 + 1 2 1 ) x + ( 9 1 + 1 6 1 ) y + ( 1 2 1 + 1 6 1 ) z = 1
Multiplying by the least common multiple of 1 4 4 , we will obtain:
( 1 6 + 1 2 ) x + ( 1 6 + 9 ) y + ( 1 2 + 9 ) z = 1 4 4
2 1 ( x + y + z ) + 7 x + 4 y = 1 4 4
Since 1 4 4 = 2 1 × 6 + 1 8 , we can conclude that 6 = x + y + z . Then we will have to rewrite the remainder 1 8 as a Diophantine equation of 1 8 = 7 x + 4 y . Because 1 8 is not a multiple of 7 or 4 , x , y must be positive integers, and clearly with a little force, there is only one way to write 1 8 = 2 × 7 + 1 × 4 .
Thus, x = 2 and y = 1 , leading to z = 3 .
Then for each day x , it will cost 3 5 0 + 2 5 0 = $ 6 0 0 .
For each day y , it will cost 3 5 0 + 1 5 0 = $ 5 0 0 .
For each day z , it will cost 2 5 0 + 1 5 0 = $ 4 0 0 .
Finally, the total payment will be: 2 × 6 0 0 + 1 × 5 0 0 + 3 × 4 0 0 = $ 2 , 9 0 0 .
Nice problem and solution (+1)! Thanks for posting it. :)
Log in to reply
Thank you. It's been a while since we've talked. :)
Very nice problem! Just a small detail - you assume in your solution you have to avoid the full-day charge, but you don't prove it. In this case, it doesn't actually affect the total, but there are other solutions, namely x = 0 , y = 5 , z = 1 and x = 0 , y = 1 , z = 6 . These both come to the same total, $ 2 , 9 0 0 , but the pigs finish before the end of the last day.
Log in to reply
Ah, I see you've amended the problem so that all pigs have to have a day off - that does indeed make the solution unique, but the assumption that a whole day solution is the best solution still needs to be justified (this is actually an integer programming optimisation problem; the first equation in your solution should be an inequality)
Log in to reply
OK. Thank you for your comment. I'll emphasize it in the solution again. :)
Log in to reply
@Worranat Pakornrat – Even with the pigs having a day off, your solution is not unique. x = 1 , y = 3 , z = 2 yields the same $ 2 , 9 0 0 solution, with the pigs finishing shortly before the end of the last day.
Log in to reply
@Timothy Smith – Oh, OK. Thank you for your alternative option. Well, at least that doesn't change the minimum wage needed then.
Pardon me for my ignorance. But what is the criteria that is applied here to assure that we have the least cost? There are other solutions (with only part work being done in the last day). Some simple calculations show that those are more expensive. But what is the minimisation criteria that is being applied here?
Log in to reply
We can optimize the pig's efficiency for a house job by their profile:
A: 9*350 = 3150
B: 12*250 = 3000
C: 16*150 = 2400
So in theory, pig C is the most efficient (cheapest for the same work but not fastest), followed by pig B, A. Thus, we should using pigs B,C as much as possible, with 6 days to spend as the fastest option. However, due to rest day issue, pig A must substitute either one at some point during these 6 days. With scenario of pig A working for only 2 days, the calculation will ultimately lead to excess day 7. Thus, pig A must work for at least 3 days to complete the work in 6 days, as he's the fastest nonetheless. Then pig A can substitute pig B for 2 days and C for 1 day (other option will again lead to day 7 or is more expensive).
I think there should not be Diophantine equation, but inequality: 28x + 25y + 21z >= 144, because changing amount of days in the problem will cause wrong solution to the equation (in integers it probably won't exist). You didn't use "If the job is done before the end of the last day, the wolf is still charged a full-day rate for that day."
Log in to reply
Ok. Thank you for your comment.
Log in to reply
Right, what we end up with is a (linear) integer programming problem. Unfortunately, this is NP hard.
If we didn't have the restriction that we need integer solutions, then we can simply check the boundary points formed by the constraints, which may yield non-integer solutions. However, with the restriction, we have to analogously check the "convex hull of lattice points", which is much harder to do.
Pig A costs $ 3 1 5 0 per unit house built, Pig B costs $ 3 0 0 0 per unit house built, and Pig C costs $ 2 4 0 0 per unit house built. To minimise cost, we want to Maximise the use of Pigs B & C , and minimise the use of Pig A .
If we only used Pigs B & C every day, they would build a house within 7 days, costing $ 2 8 0 0 . However, as each Pig needs one day off, the cheapest we could do it in 7 days is 2 , 6 & 6 days working between Pigs A , B & C respectively, costing $ 3 1 0 0 .
Next, we try to reduce the number of days:
Let's assume it can be done in 6 days, with a baseline of 2 , 5 & 5 days working, with a cost of $ 2 7 0 0 . However, this does not quite complete a house in that time.
The cheapest way to build faster, would be by swapping either B for A or C for B for 1 day, costing an extra $ 1 0 0 . However, only swapping a single day does not save enough time to complete the house in 6 days: for that, we need 2 swaps, costing us $ 2 0 0 extra, resulting in a total cost of $ 2 9 0 0 .
We cannot build a house in fewer days than this, as the fastest option of 4 , 4 & 2 is only able to build ~ 1 0 9 of a house in that time.
The pigs need to work in pairs, their productivity is:
Team composition | house per day | cost in $ per day | value in microhouse per dollar |
A: pigs 1 and 2 | 9 1 + 1 2 1 = 1 4 4 2 8 | 600 | 1 0 0 0 0 0 0 1 4 4 • 6 0 0 2 8 ≈ 3 2 . 4 |
B: pigs 1 and 3 | 9 1 + 1 6 1 = 1 4 4 2 5 | 500 | 1 0 0 0 0 0 0 1 4 4 • 5 0 0 2 5 ≈ 3 4 . 7 |
C: pigs 2 and 3 | 1 2 1 + 1 6 1 = 1 4 4 2 1 | 400 | 1 0 0 0 0 0 0 1 4 4 • 4 0 0 2 1 ≈ 3 6 . 5 |
Since each team must be active for at least a day, this accounts for building 1 4 4 7 4 of a house. Note that team C offer the most value for money, then team B, then team A. The cheapest way to realise the other 1 4 4 7 0 of the house is however to hire team B for two more days, and team C for 1 more day, that way they could produce 1 4 4 2 1 + 2 5 + 2 5 = 1 4 4 7 1 of a house.
So together he hires team A for 1 day, team B for 3 days and team C for 2 days. The cost will be 1 × 6 0 0 + 3 × 5 0 0 + 2 × 4 0 0 = $ 2 9 0 0 .
Let
(1) x be the number of days for the pair (1,2), the amount of completed work=x(1/9)+x(1/12)=x(7/36),
(2) y be the number of days for the pair (1,3), the amount of completed work=y(1/9)+y(1/16)=y(25/144),
(3) z be the number of days for the pair (2,3), the amount of completed work=z(1/12)+z(1/16)=z(7/48).
Write the total work =1 as the sum of above three pair of works:
x(7/36)+y(25/144)+z(7/48)=1.
Solve the above Diophantine equation using WolframAlpha to get solution:
x=2, y=1 and z=3 and the total cost as:
2 (350+250)+(350+150)+3 (250+150)
=2900
Answer=2900
I just joined. Don't see how to add a new solution. So using this comment box.
This problem can be generalized and solved as an integer programming problem. The integer decision variables are the pig-pair days worked: p12, p13, p23. The cost per day of each pig-pair is 600, 500, 400. So the objective function is to min total cost: (600 p12) + (500 p13) + (400 p23). The daily construction rate for each pig-pair is: 0.1944, 0.1736, 0.1458. So the build one house constraint is: (0.1944 p12) + (0.1736 p13) + (0.1458 p23) >= 1 (round up to at least 1). The total number of days to build the house is p12 + p13 + p23. The side constraints to give each pig at least one day off: p12 + p13 <= total days - 1 for pig1, p12 + p23 <= total days - 1 for pig2, p13 + p23 <= total days - 1 pig3
Solving gives one solution p12 = 1, p13 = 3, p23 = 2, duration = 6 days, cost = $2,900
Log in to reply
If your answer is accepted as correct, then, under discussion, you could write or paste your solution. You can still do it.
That's how, I am doing it.
Problem Loading...
Note Loading...
Set Loading...
Firstly, organize the information as below:
To pay the least possible amount of wages, the wolf should employ pigs B and C as long as possible. However, as both pigs have to rest for at least a day, the work will be done by pigs A & C and A & B on the respective days. Therefore, we have:
Solving Equation:
n ( 1 2 1 + 1 6 1 ) + ( 9 1 + 1 2 1 ) + ( 9 1 + 1 6 1 ) = 1 n = 3 1 3 = 4 . 3 3 3 …
Put n=4, we find that the total work done= 1 4 4 1 3 7 , with 1 4 4 7 remaining.
To avoid being charged another full day's wage (which is $250+$150=$400 at least, larger than any pig's individual daily wage), we may substitute pig B or C by pig A for 1 day.
Daily work done by Pig A is more than that of Pig B by 9 1 − 1 2 1 = 3 6 1 Daily work done by Pig A is more than that of P i g C by 9 1 − 1 6 1 = 1 4 4 7
Therefore, if Pig C is substituted by Pig A for 1 day, the work can be done in 6 complete days, while keeping the wage as low as possible.
The arrangement is therefore:
The least possible amount of wage= 3 5 0 × 3 + 2 5 0 × 5 + 1 5 0 × 4 = ( $ ) 2 9 0 0