   Shlemiel the Painter Shlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. "That's pretty good!" says his boss, "you're a fast worker!" and pays him a kopeck. The next day Shlemiel only gets 150 yards done. "Well, that's not nearly as good as yesterday, but you're still a fast worker. 150 yards is respectable," and pays him a kopeck. The next day Shlemiel paints 30 yards of the road. "Only 30!" shouts his boss. "That's unacceptable! On the first day you did ten times that much work! What's going on?" "I can't help it," says Shlemiel. "Every day I get farther and farther away from the paint can!" ---- The puzzle? Tell me the a set of correct numbers to replace 300/150/30 in this joke. Joel Spolsky Tuesday, December 11, 2001 I don't get it?  What rules (other than that the first number  has to be ten times the last number ) are in effect? Why can't I just say 500 250 and 50? Michael Pryor Wednesday, December 12, 2001 The constraint is that you can assume he walks at a constant rate, paints at a constant rate, and needs to return to the paint can every time he paints a constant number of yards... Joel Spolsky Wednesday, December 12, 2001 BTW it may be the case that there are lots of combinations of three numbers that work, but also lots of combinations of three numbers that don't work. I don't actually know the answer to this puzzle but somebody needs to work it out so I can tell this joke in a mathematically plausible way. Joel Spolsky Wednesday, December 12, 2001 The big thing we're missing is how much can he paint on a refill.  If we get that answer, we can find out how far he walks in a day.  If we assume that he painter one yard on a refill then: He walked about 90300 on the first day painting 300 yards. He walked about 90750 on the second day painting about 125 yards. He walked 90912 on the third day painting about 96 yards. To get the first day I used: a = 0 b = 0 while (b < 300) do   b += 1   a = a + (b) * 2 end p "Walked for #{a}" p "Painted #{b}" To get the second day: a = 90300 b = 300 while (a > 0) do   b += 1   a = a - (b) * 2 end p "Walked for #{a}" p "Painted #{b}" And to get the third day change b to 425 Joseph Erickson Wednesday, December 12, 2001 OK, let's put down some values: WR = walking rate, in seconds per yard. PR = painting rate, in seconds per yard. PD = paint distance (per brush-full), in yards. PT = total paint distance so far. TIME = total time worked. Well have some more assumptions about how Shlemiel works: every times he shows up for work, he starts his day at the same spot he left the day before. Also, he keeps his paint brush in a humidifier overnight so that he can pick up his work were he left. He his dumb, but hard-working, as per the original joke... Let's see how much time each paint pass (brush-full) takes. pass0 (start): TIME = PT = PD = 0 pass1: TIME = PD * PR pass2: TIME = PD * 2 * WR + PD * PR (note: 2 * WR to walk back and return from the can). pass3: TIME = 2 * PD * 2 * WR + PD * PR and so on. Now we define the time for pass N given pass N-1. The formula for pass n, were PT(n) is the distance painted so far at the end of pass n, is: passN: TIME = (PT(n-1) + PD) * 2 * WR + PD * PR Since we know that PT(0) is 0, we can plug that in, do the summation for n from 1 to N, and use the fact than a summation of 0 to N is equal to N*(N-1)/2, which gives us: TIME = N * (N-1) / 2 * PD * 2 * WR + N * PD * PR Grouping the N together to have the classic algebraic form: N^2 * PD*WR + N * (PD*PR+PD*WR) - TIME = 0 Solving for N: N = { -(PD*PR+PD*WR) + sqrt[(PD*PR+PD*WR)^2-4*(PD*WR)(-TIME)]}/2*PD*WR Let's use the values: WR = 0.6 s/yrd PR = 7.2 s/yrd PD = 5yrd TIME = 3600*8 * days = 28800*days After 1 day: n = 91.7, total distance = 458.5 After 2 days: n = 132.2, total distance = 661 After 3 days: n = 163.3, total distance = 816.5 So the numbers of yards painted each day are 458.5, 202.5, 155.5. Not quite the 10 times factor as in the original joke. The problem here is that the square law is on the passes not the days. Since there are so many passes on the first day, the big rate drop off happens all in the first day, so the other days do not seem as bad. Analyzing the formulae, we see that the only way to get a number around one for the second day (so the big drop is on the third) is to have a painting rate higher than the walking rate. This would be absurd, so there is no logical way to make the joke as it is work in real life. There is a way, which makes the joke even more ridiculous: shlemiel paints the road with a special truck, but goes back to the paint-shop for the refill on foot (or by bus)! This way his paint rate can be higher than his walking rate... we could get this by making his boss tell him that he must use the truck only for painting the road. Weither that makes the joke funnier (because the fault lies with the boss) is debatable. Pierre Baillargeon Wednesday, December 12, 2001 Since we have to start with some assumptions about how fast Shlemiel works, let's just say that he actually did paint 300 yards in the first day. Let's also assume that he has to go back to the paint can after every yard painted. Let's not make things anymore confusing either by getting into details about what kind of lines he's painting (since, because we're working out relative numbers, and not absolutes, it's not really relevant). Assume it is a straight line, 300 yards long. We're also going to assume that his walking rate and painting rate are the same. First, we figure out how much Shlemiel can walk/paint in a day: Starting out, then, he paints one yard, then walks back one yard to the paint bucket, then forward a yard and paints a yard, then walks back two yards, etc. So we get: 1+1+2+2+3+3+...+299+299+300+300 = 2 x (1+2+3+...+299+300) = 2 x (301 x 150) = 90300 yards walked (pretty impressive...that's just over 51 miles) Now, given that he is capable of walking/painting 90,300 yards in a day, we can work out how much he did the second day. He walks 300 yards to the end of his line, paints a yard, and walks back 301 yards, and so on. It looks like: 301+301+302+302+...+n-1+n-1+n+n =2(301+302+...+n-1+n) =2(301+n)(n+1-301)/2 =(301+n)(n-300) =n^2 + n - 90300 No we just solve for this equation equalling 90300: n^2 + n - 90300 = 90300 n^2 + n - 180600 = 0 Digging up the quadratic equation formula (which I won't bother to reproduce here), we get: n=424.471 or -425.471 So at the end of his second day he was 424 yards from the paint bucket, which meant that he covered 124 yards in his second day. For the third day, we get: n^2 + n - (425x424) = 90300 n^2 + n - 270500 = 0 n=519.596 So on the third day he walked 519-424= 95 yards So in this joke, 300, 124, and 95 are more reasonable numbers. Brad Greenlee Wednesday, December 12, 2001 Looking at it from another direction (not that this actually works, but food for thought): How fast would Shlemiel have to walk & paint to paint 300, 150, and 30 yards each day, respectively? Unfortunately, since there's only two variables, this won't be consistent with three days.  If only there was a third variable... But, for the curious, here's how it works out: ASSUME: - Shlemiel starts and finishes at the paint bucket. - Shlemiel paints one yard per trip. - Shlemiel works 8-hour days (with no breaks!) x = Number of yards walked (this INCLUDES the yard he walks while painting it) y = Amount of ADDITIONAL time painting each yard requires (this includes the additional time needed to top up the paint brush each trip) Remember, there are 28,800 seconds in eight hours. Yardage totals are calculated as: Day 1: 2(1+2+...+300) Day 2: 2(301+302+...+450) Day 3: 2(451+452+...+480) Thus, we have three equations: (1) 90,300x + 300y = 28,800 (2) 112,650x + 150y = 28,800 (3) 27,930x + 30y = 28,800 Solving equations (1) and (2), x = 16/75 sec, y = 64 16/75 sec. Solving equations (1) and (3), x = 1 13/35 sec, y = -316 4/5 Solving equations (2) and (3), x = 4 4/15 sec, y = -3,012 4/15 In other words...impossible. Just for fun, though, with equations (1) and (2), with x = 16/75 seconds, that means Shlemiel was walking at 9 207/352 km/h (5 68/71 miles/h for you Americans) - which is fast, but not completely unreasonable... Darryl Ballantyne Wednesday, December 12, 2001 This is why I ain't a programmer. ;) Meryl Wednesday, December 12, 2001 Obviously Shlemiel walks farther the more trips he makes back to the paint can.  If he did the entire 300 yards all in one shot, that would be a lot less walking than painting the 300 yards but making a trip back to the can every inch or so.  We can make assumptions about the length of the line he paints, but I would generalize it out with an integral to get at the fundamental "n squaredness" of the problem.  The first job is figuring out what one day's work is equal to: One day's work = int(0, 300) x dx ... = 300^2 / 2 = 45000 I'm gonna leave that answer unitless because it really isn't a measure of physical distance, it's just a number.  The next day, he does the same amount of work (I hope!), but the limits on the integral change.  Let y = the distance we want to solve for. int(300, y) x dx = 45000 y^2 / 2 - 45000 = 45000 y^2 = 180000; y = 424 So Shlemiel painted 124 more yards on the second day.  Then on the 3rd day: int(424, y) x dx = 45000 y^2 / 2 - 90000 = 45000 y^2 = 270000; y = 519 So Shlemiel painted 95 yards on the third day. In general on day "x" Shlemiel paints up to yard 300*sqrt(x), or paints 300*(sqrt(x)-sqrt(x-1)) yards on any given day. This answer is identical Brad's answer, which did the same thing but with summations. Alyosha` Wednesday, December 12, 2001 I wrote this while my network connection was down, so I rehash a concept that Brad Greenlee already covered.  But the second to last paragraph contains a new thought that may interest you… Here is what Shlemiel is doing:  Standing at the paint can, he dips his brush in the paint, walks to the next stripe, then walks back to the paint can and does it again.  Of course, each time he does so, the distance he must walk increases, so his productivity smoothly decreases as he works.  This is a math/logic puzzle, so we are allowed to make some simplifying assumptions, so we'll assume that dipping the paintbrush in the can takes no time, and that our painter paints as quickly as he walks.  This also has the effect of rendering unimportant the length of the stripes, leaving only the number of stripes per unit of distance as significant.  Later on, we will pick a simple stripes to distance rate that will illustrate the problem cleanly.  The last crucial assumption is that Shlemiel can paint only one stripe before having to go back to the paint can to wet the brush with more paint.  This also can be flexible, but believe me, it'll be simpler just to accept this for now.  OK.  Let's start off with a simple example.  Imagine that Shlemiel is going to paint 3 stripes to a specification of 10 stripes per hundred yards.  This means that he must paint a stripe every 10 yards.  So, Shlemiel dips the brush in the paint, walks 10 yards forward to paint his stripe, and walks the 10 yards back to the can.  He dips the brush in the paint, and this time walks 20 yards forward to paint the next stripe, then walks the 20 yards back to the can.  After wetting the brush, he walks 30 yards out to make the last stripe, and walks back to the can.  Finished!  Let's see how far he walked.  Well, he walked 10 yards out, 10 yards back, then 20 yards out and 20 yards back, and finally 30 yards out and 30 yards back.  That's 10 + 10 + 20 + 20 + 30 + 30 = 120 yards.  Not a very efficient a way to paint, you might say, but then, the state Department of Transportation pays Shlemiel by the day, so maybe he's not so dumb after all.  Anyway, being smarty pants programmers, we are compelled to see if there is a way to solve this problem without having to count the yardage up on our fingers.  And, there is!  This is an example of summing a series.  Notice that for every stripe, the distance walked is 2 * (L * n) where n is the ordinal of the stripe and L is the length of the stripe interval (this is what we called earlier the stripe to distance rate, and in our example is 10 yards).  For example, the distance walked for the third stripe is 2 * (10 * 3) = 60.  If we want to figure out the distance walked for more than one stripe, we need to sum up the distance for each.  There is a notation to express this sum, but it involves a big uppercase sigma and some little letters and numbers and I don't think I can do it in HTML and if I can I'm too lazy to look up how.  For the present problem we'll just say in English that we want to calculate the sum of 2 * (10 * n) over a range of n=1 to n=3.  Notice that 2 * (10 * n) reduces to 20 * n.  So, for the whole series we add up (20 * 1) + (20 * 2) + (20 * 3).  The result is 120 (yards).  In this case, there isn't any easier way to calculate the answer other than by adding up each stripe then summing them separately.  What information is given to us in the joke and what is left unspecified?  First of all, we don't know how long is the stripe to distance rate, or stripe interval.  So, we are free to assign a value that makes the calculation simple.  Let's assign it to be one half a yard per stripe, or L = 0.5 yards.  We know from the joke that Shlemiel was able to make 300 yards of progress on the first day.  Of course, we throw out the production numbers of the subsequent days, since those are the values that we are trying to calculate!  Since our painter produced stripes to a spec of 1 per half yard, his 300 yards of progress means he did 600 stripes the first day.  So, how far did Shlemiel walk the first day?  He walked 2 * (0.5 * n) summed over the range of n=1 to n=600.  This is actually really easy to calculate by hand, because of our crafty choice of stripe interval.  Notice that 2 * (0.5 * n) reduces to just n.  Now that's simplicity.  So, we just have to calculate n summed over the range of n=1 to n=600.  We could add it up like this, 1 + 2 + 3 + 4 ... but there is a much easier way.  We need to add up all the integers between 1 and 600.  An insight into this long addition problem is that if you add the smallest and biggest number in that range, you get 1 + 600 = 601.  OK, now let's add the next smallest and next largest numbers, 2 + 599 = 601.  And the next pair?  3 + 588 = 601.  Hmm.  There are 300 such pairs of numbers between 1 and 600, so the sum of those numbers is 300 * 601 = 180300.  So, Schlemiel walked 180300 yards the first day.  Great, now what?  Well, the whole point of the joke is that our Schlemiel was really working just as hard each day, but that his work plan was very bad.  So we will say that he walks 180300 yards each day, back and forth, painting as many stripes as possible.  So how many stripes did he really do on the second day?  The problem gets much harder here.  We already know the sum of the range, it's 180300, and we know that n starts at 601 since Shlemiel finished 1 through 600 the first day.  So, we must solve for x in the problem of "n summed over the range of n=601 to n=x is equal to 180300".  There is probably some easy way to solve this that every math whiz knows, but I don't, so I think it's time for the pragmatic developer to eschew the elegant solution and turn to instead to a powerful tool: Microsoft Excel.  I made a spreadsheet with columns for Stripe ordinal, Distance traveled to make stripe, Cumulative distance traveled, and Cumulative road finished.  I made other cell elsewhere that I called "stripe interval."  I filled out the Stripe ordinal column with integer literals 1 through some big number, of course.  I created the correct formulas for the other columns and copied them a long ways down.  Scrolling down the Cumulative road finished column, I saw that, indeed, at 300 yards of road finished, the stripe ordinal was 600 and the Cumulative distance traveled was 180300.  Since we know that the distance traveled the second day should be the same as the first, I scrolled down to where Cumulative distance traveled was twice as much as 180300, or 360600 saw that the cumulative road finished at that point was 424, which is 124 yards further than the 300 yards Shlemiel had covered at the end of the previous day.  Using the same technique, I found that the third day, he finished 95.5 yards.  However, for my money, specifying accurate numbers for the yardage of each day when telling the joke adds just enough of a pedant's touch to suck the humor right out of it.  Use with caution.    Really the problem is best expressed as the following inequality: The sum of 2*L*n over the range of n=1 to n=F is greater than or equal to the sum of 2*L*n over the range of n=F+1 to n=x.  F a constant equal to the first day's stripe output.  Solve for the greatest possible x.  Subsequent days are solved in the same manner.  One note: the numbers looked up using the spreadsheet slowly drift off from the correct value, since the spreadsheet assumes that Shlemiel picks up from work right where he left off the previous day, even through he was probably in the middle of walking to stripe or can.  The real Shlemiel would return to his paint can, punch out, and go home.  He would start the next day at the paint can.  This shows that painters, like programmers, suffer productivity losses when interrupted.  For the precisely correct answer, use the inequality expressed above to get the answer one day at a time.      Interestingly, the spreadsheet shows that the number of days required to accomplish the same amount of work as the first day increase by two days every time that amount of work is achieved.  In other words, on the first day, Shlemiel finished 300 yards.  It took another 3 days for him to achieve another 300 yards.  Then it took 5 more days to do another 300.  Then 7 more days to finish 300 more.  Then 9 days.  That's as far as I checked, but I'm confident that the relationship will hold.  This linear increase in the change of inefficiency shows that this is indeed an n-squared algorithm. (Note: Aloysha already proved this.) Ethan Herdrick Thursday, December 13, 2001 I believe that there is a problem with the logic in the prior response. If Schlemiel walks out x yards to paint his strip, doesn't he walk back x yards + the length of the stripe? Luke Miller Thursday, December 13, 2001 Shlemiel is being paid in kopecks, and it is late enough that have paved roads with dotted lines down the middle, so the units should be meters, not yards. Aron Insinga Thursday, December 13, 2001 Luke:  The length of the stripe is just part of the total stripe interval.  The stripe interval is just the length of a stripe plus the space to the next stripe.  So, longer stripe, shorter space, shorter stripe, longer space; same thing as long as total length is static.  Ethan Herdrick Thursday, December 13, 2001 One complication we ignore is that the act of painting is different from the act of walking.  Painting is intuitively slower.  However, if we use physics, we can use "work" equations, and not deal with messy velocity-laden equations.  In fact, it makes more sense, since a person doesn't do a fixed Distance per day, she does a fixed amount of physical Work per day.  With just minor variations during some small interval of workdays. We treat walking exactly the same as painting, except that painting has friction.  Therefore work done by going against friction is just a single term in our equations, which goes up linearly with the number of passes.  If friction is 0, then the answer should equal Brad's & Alyosha's answers. There must be multiple solutions due to friction, because just knowing he went 300 yards the first day does not provide enough information to solve the next day's distance.  We can see that the greater friction there is, the closer Shlemiel is to doing 300 yards every single day.  So one solution would be 300, 299.9999999, 299.9999999. That's all I'll write, because I haven't studied enough formal math or physics to solve this quickly, with equations all exact. :-)  In fact I'd go for an algorithmic solution rather than solving an equation, like Joseph did. forgotten gentleman Friday, December 14, 2001 Another thing I don't see anoyone account for is paint dripping off / drying between each of his trips.  This would reduce the amount of work he could accomplish on the second and third day.  Perhaps one of the math literate could introduce a dry rate variable, and calibrate it so the second day really did work out to 150, then we'd see how much he would be able to do on the third day... (The drip/dry rate would mean that he could paint less per trip the farther he is from the bucket) Noah Bast Friday, December 14, 2001 What about the fact that he gets more tired each day or had a big night out on the second day? Can we assume a constant level of stamina/fitness? Paul Berger Friday, December 14, 2001 I have what I think is a reasonable method for solving this problem, but in the grand tradition of great mathematicians I'm not going to give an answer. Instead, I'm going to let the engineers get the actual numbers for themselves. First: the tedious algebra! I'll use Pierre Baillargeon's notation. Note that Shlemiel must start every day at the pot to get a fresh load of paint. If he is a true work-shy layabout then he will leave his brush in the pot at the end of each day. If you don't like that assumption then the following argument can be easily modified to accomodate a different one. Let t(n) be a function for the amount of time it takes for Shlemiel to make his nth trip from the pot and back. The formula for t(n) must be: t(n) = PD ( ( 2n + 1 ) WR + PR ) because he must walk to the end, paint a bit and then walk the whole way back. Now let T(a, b) be a new function for the time it takes to paint b times given that Shlemiel has already gone to paint a times. Because I can't write a sigma in ASCII, I'll write sums as: Sum(r, a, b, x) where r is the (dummy) variable we are summing over, a and b are the limits and x is the formula for the sum. Then T can be expressed as: T(a, b) = Sum (r, 1, b, t( r + a)) Now we substitute in the formula for t(n), which gives us a very hairy formula with lots of sums. This can be simplified by noting that: Sum(r, 1, b, 1) = b Sum(r, 1, b, r) = 0.5*b*(b+1) So we eventually get: T = PD ( WR*b^2 + ( 2 ( a+1 ) WR + PR ) b ) This is a quadratic, so we can solve it for b. However, the formula is so complicated that I just can't write it. Now lets actually start solving this problem! We assume that all work days are of equal length, and we will use the above formula to calculate b. Hence we must fix T(a, b) at some constant value. If we measure our speeds in "yards per working day" then we can put T(a, b)=1 to make things a bit easier. We now have a formula for b (which I can't write), call it F. b = F ( a, WR, PR, PD ) Then PD*F is the distance worked in one day haing painted some number of stripes already. We assume that WR, PR and PD are constant, so we create another function B where: B(a) = F ( a, WR, PR, PD) for the sake of berevity, and another function D where: D(a)= PD * B (a) which gives us the distance done in a day. Finally, let D1, D2 and D3 be the distances painted on each of the three days. Then we have that: D1 = D( 0 ) = PD* B( 0 ) D2 = D ( B (a) ) = PD * B( B( 0 )) D3 = D ( B( B(a) ) ) = PD * B( B( B( 0 ) ) ) and from the question: D1=10 * D3 which gives us the final formula: B( 0 ) = 10 * B( B( B( 0 ) ) ) So, to solve the problem we must simply(!) apply the quadratic formula to the quadratic equation for T, then apply this formula recursively to itself three times, and then finally pick values of PD, WR and PR that get the above equation to balance. We can then compute D1, D2 and D3 using function D(n). OK, I admit, this isn't really a solution at all, but it does reduce the problem down to that of solving just one extremely hairy equation. I'm sure that solving equations by approximation is a CS technique that you're all familiar with (heh) so there should be C program that can compute the answer. You have plenty of variables to play with. The most challenging part will be to actually write the equations in ASCII without making a mistake. Chris Hooper Friday, December 14, 2001 hi joel, this was an interview question for me at deshaw. my answer was fibonacci series! Jawahar Mundlapati Saturday, December 15, 2001 Further to Noah Bast's comment about drying and dripping of the paint.  The drying factor would be affected by the psychrometric conditions as Shlemiel worked.  The temperature and humidity would change through the day and would change more dramatically if a weather front passed through.  However, a simple formula based on average values for the time of year could be used.  To account for these factors, you would probably have to rely on empiricaly derived drying rates provided by the paint manufacturer.  The relative wind speed as Shlemiel walked would be another factor, which would be further affected by the "wash" as vehicles drove past him. You would prbably find that there was a threshold distance from the paint tin (let's hope he replaces the lid after each visit) at which the drying effect became significant. Max Hudson Monday, December 17, 2001 guys, you have waaaay too much time in your hands ;) eV Wednesday, December 19, 2001 Someone's project is running late ! Matt Thursday, January 3, 2002 Software engineers, I knew the answer from the moment I read this. Shlemiel painted 80% of the road on the first day, and took the next few months painting the remaining 20%. Christopher Shepherd Friday, January 4, 2002 It was just the helplessness factor what made Shlemilel work less hard each day. (Having to walk back to the paint can each time must be pretty frustrating). So 300, 150 and 30 are, in that sense, realistic numbers. I bet the fourth day he quit. sergio acosta Thursday, April 4, 2002 nice to read it :-) Friday, May 24, 2002 You do realize, we're trying to sum up Stupidity as a Mathematical Equation. Danny B Monday, July 15, 2002 That's all OK, but nobody has found the real question: - How many stripes can Shlemiel paint before the soles on his shoes wear out? Tarek Zein Wednesday, November 13, 2002 On the first day he paints 300 yards. This is the most he can paint in one day. On the second day he paints half that distance. From this we can conclude that he spends half the time painting, and half the time covering the initial 300 yards. So on the third day he would spend half the time covering the initial 300 yards again, half of the remaining time (a quarter of a day) covering the 150 yards from the second day, thereby leaving a quarter of a day to paint. Which should be 75 yards painted on the third day. So each day, he paints half as much road as he did the day before. If you express that as a mathematical sequence, then the actual values become slightly irrelevant and you have your answer. The upper limit of the total road distance that Shlemiel can paint (given 300 yards maximum in one day) will be 600 yards and he will spend his entire life doing it. There is not enough information given to draw any other (logical) conclusion without making an excessive number of assumptions. Andrew Thursday, November 14, 2002 all of you are wrong this shlemiel painted 300 the first day got a little lazy the second day and only painted 150 but the guy still paid him a kopeck so shlemiel being the crafty guy he is thinks why do i need to work so hard if i still get paid the same so on the third day he does only 30 and when the manager gets pissed he makes up a damn good excuse and all you manager types out there trying to find a mathematical formula to figure out if you're getting cheated. Pak Thursday, November 14, 2002 Of course, everyone has ignored that the further he walks, the more paint he looses by the dripping and the more paint dries on the brush, requiring him to clean his brush more often, so the original numbers are easily possible... Hauke Thursday, November 14, 2002 The definitive answer: The ratios are as follows: n^2 : n^2 + n(n+1) : n^2 + 2n(n+1) : .... Basically the ratio follows close to this series: 1 : 0.5 : 0.23 .... or 300 : 150 :69... BTW the first few solns were quite interesting reads but IMHO didn't get the soln right, because they got lost in all the definitions. The only definition you need is: Assume Sclemiel can paint "x" stretch of road each time before he has to go back to can to reload. HTH. Syed Saturday, November 16, 2002 So, people, you don't know about integral calculation? common method : T = L/V = E ( (2 * x) / V ) dx from X0 to X1 = 1 1th day : X0 = 0; X1 = 300 => 300^2 / V = 1 => V =1/90000 (day/yard ;-)) 2nd day : X1= 300 ; V=1/90000 (X1^2-300*300)/V = 1 This means, that X1 = 300 * SQRT(2) = 124... next day : (X1^2-2*X0)/V = 1 From this - X1 = 300*(SQRT(3)-300*SQRT(2)) = 95... And so on, an Nth day painted length will be 300 (constant ;-)) * (SQRT(N)-SQRT(N-1)). This give us a aproximate value of Ln = 300*(1/(2*N)) in infinity. That is clear as result, if think a little ;-). In this case, a result of 30 yards will be only an 10th day ;-) Alexander Saturday, December 28, 2002 A! Is need also to say, that for this solution Shlemiel get time only for _transport_ a paint from bottle to point to paint. In another case (if painting get a big part of total work time), result will be... bether ;-). Why - this means, that speed of Shlemiel is more that calculated 90000 'yards' (realy there are 'yards' only if they paint one yard each time ;-)) per day, because they take a littler part of time for walking, and more - for painting. This give us a more opthimistic result. In case, if they walk two times faster, and other time paint - this means, that they will paint a next day not 124, but about 160-170 yards, using day at 3/4 for walking, and other time for painting. Alexander Saturday, December 28, 2002 To Andrew: 300 isn't the most he could draw. He could have painted much more, if he carried the can with him after every line he painted.  Astrid Thursday, January 16, 2003 You guys sure know how to ruin a joke. Whats purple and Concord the World? Alexander the Grape! Monday, January 27, 2003 Speaking of which: the answer is, of course, "whatever distances make the joke the funniest". My sense of humor indicates that the original numbers are about right. Unless, of course, the purpose of the joke was actually to illustrate Joel's point about strcat :-). Ray Trent Monday, February 24, 2003 The answer is 42, of course. T.J. Sunday, September 21, 2003 Of course, the answer is 42. But do you know the question? Peter Wednesday, October 29, 2003 There are no correct numbers. Shlemiel should have the can in his hand while walking and painting. Evgeny Tuesday, February 3, 2004 Since there is still no GENERAL and exact SOLUTION: First of all, this is an n^2 problem. Inverse is sqrt(t), derivative: ~1/sqrt(t), this is proportional to the number of yards he can paint in a small interval around t. Quotient of evaluation at t and t+delta_t: sqrt(t+delta_t)/sqrt(t). As t gets bigger, the quotient gets smaller and NOT bigger. So, 300/150 = 2, 150/(x|x<2) > 75 and certainly not 30. That's also why this joke doesn't work at all with correct numbers because we want to see dramatic relative decreases but can't get them no matter how fast Shlemiel paints or how slow he walks. Now, what are reasonable distances? This is how he walks/paints: x - - x - - - - x - - - etc. x are units he paints, - are units he walks. We assume that he always returns to the paint can after a unit is painted even at the end of the day and walks and paints at constant (yet different) speeds. As you can see, the number of units he needs to walk to paint n units can be expressed as two sums or n(n+1)/2 + (n-1)n/2 = n^2 units. Hence, the time t(n) it takes to paint n units is: t(n) = t1*n + t2*n^2 t1: time it takes to paint one unit t2: time it takes to walk one unit We then have the following equations: t(n) = t1*n + t2*n^2 = 1 (day) t(a*n) = t1*n*a+  t2*n^2*a^2 = 2 (days) t(b*n) = t1*n*b+  t2*n^2*b^2 = X (e.g. 3 days) There are of course far too many unknowns in there. At this point, you can just insert t1 and t2 into equation 1 if you want, you'll get n and 2 more quadratic equations. However, if you want all solutions you can solve the system partially. t1 and t2 depend on n and either a or b. t1 = (a^2 - 2)/(n*(a^2 - a)) (in days!) t2 = (2 - a)/(n^2*(a^2 - a)) a and b only depend on each other. Solving for b, we get the quadratic equation: (2-a)*b^2  + (a^2-2)*b - X*(a^2-a) = 0 ============================== This means that if we know the number of yards he paints the first day and on the second day, it is determined how far he'll get on day X. The absence of n in that equation means that for ANY given distance, the length of the lines he paints  doesn't matter, he just has to walk faster (or slower). So, we can now insert some numbers: day1: 300 yards day2: 150 yards a: 450/300 = 1.5 => b = 1.886 = 565.8/300 day3: 565.8 - 450 = 115.8 yards !!! Or if you really want to have 30 yards the third day: day1: 300 yards day3: 30 yards => a = 1.11716 => b = 1.21716 day2: 35.15 yards!!! The 300/424.5/520 solution is also correct. Either way, the joke is ruined. Basil Achermann Thursday, March 11, 2004 Hi, all! (Sorry for not so good English :) (I used meters instead of yards, i suppose it makes no difference.) If he paints 1 meter per once, so he should walk first day: 2*(1+2+...+300) = 301*300 ~= 90,000 meters = 90 km - impossible!! Suppose he paints 5 meters per once, we would walk: 2*(5+10+15+...+300) = 10*(1+2+...+60) = 61*30 ~= 18,000 meters = 18 km - it could be. Suppose his speed is 4 km/h, so he spend on walk 18/4 = 4,5 hours. Let's suppose he works 8 hours/day and add 1/2 hour on rest :) So he spend on painting 8 - 4,5 - 0,5 = 3 hours (on 300 meters) or 1/20 hour on 5 meters (1 strip). On the second day he made N walks, so he would walk: S = 2*300*N + 10*(1+2+...+N) = 600*N + 5*(N+1)*N meters Totally he spends 8 hours on walking and painting: S/4000 + N/20 = 8  => N^2 + 161*N - 6400 = 0  => N ~= 33 So on the second day he advances on 33*5 = 165 meters. On the third day we get: N^2 + 227*N - 6400 = 0 N ~= 25 So on the second day he advances on 25*5 = 75 meters. (It seems to me that figures 300, 150, 75 (someone already put) are more correct :) Good luck!  Peter Huggy Tuesday, April 20, 2004 > 2*(1+2+...+300) = 301*300 ~= 90,000 meters = 90 km - impossible!! Rubbish, I've walked 50 miles (80km) in a day before now (whilst talking to a girl and that's far more hard work than painting.) rjp Friday, November 19, 2004 The answer that I got was 300 yards on the first day, 125 yards on the second day, 96 yards on the third day, and 81 yards on the fourth day. It really doesn't matter how fast the painting is compared to the rate of walking as the walking quickly becomes the majority of the work. The interesting thing with this equation is that the largest drop off (in terms of total yards and largest percentage) is between the first and second day. Each day the drop off is a little bit less. So if you were to get Shlemiel's progress reports on days 7,8,9 and 10 you would likely not complain about the small drop off - even though he worked more efficiently there would be great savings. I wonder how that translated to some of our practices developing code. Ralph Miner Monday, December 13, 2004 Basil is right, too bad, I liked the joke very much. Marc-Andre Lafortune Tuesday, December 14, 2004 What the joke does not account of is that each day, Shlemiel adds less and less distance to be covered on the following day, because he only ever paints a constant length before another trip back and forth. Indeed, the sharpest drop-off happens after the very first strip. Let me explain: Oh -- I'll note that all this assumes an equal speed of painting and walking. His paint:walk ratio is infinite at first -- at the end of the first strip he has pained one yard and walk no yards. By the end of his second strip he has painted two yards and walked two yards. At the end of the third strip, he is at three yards painted, six yards walked, after the fourth he is at four yards painted, twelve yards walked. You can see where this goes -- n/n(n-1), or 1/(n-1). His efficiency is inversely proportional to to amount of work already done. A funny consequence is that if you try to make the joke's numbers more plausible by accounting for the fact that paint drips off his brush as he walks, you actually make them more *im*plausible because you get a 1/(n-1)^x ratio (where x > 1) so the initial drop-off is even more dramatic and the slope of the resulting curve flattens out even more. Of course, this is reality, not mathematics, so a dripping brush imposes a sharp cut-off at some point since Shlemiel will not be able to paint an infinitely short strip with the infinitely small amount of paint still left in his brush after making an infinitely long trip to paint the (infinite+1)-th strip. A funny consequence of the funny consequence is that to make the joke's numbers plausible, you need his efficiency to be 1/(n-1)^x where x < 1 -- in other words, he must paint a *longer* strip with each roundtrip. Any way you turn it (you can do the same analysis using varying speeds), there is no plausible way to make the drop-off during subsequent days worse than the one during/after the first day. In fact, the more factors like dripping you try to take into consideration, the more dramatic the drop-off during/after the first day becomes, as opposed to the following days. There is only one other notable point in the curve: at some point, a the end of the last strip is so far that the length of a day or the amount of paint his brush can hold or some other factor is too small to allow him to reach it at all, at which point he is unable to paint a single extra yard. Aristotle Pagaltzis Wednesday, December 22, 2004 You could possibly fix the joke if the section of road he was painting was an increasingly steep hill. But for most people the complication wouldn't improve the joke. J Thomas Friday, December 24, 2004 I think the 'walks back to paint can and paints X yards before refilling' approach is definitely the easy way to do the problem, and interesting because whether he can paint 1 yard or 1000 yards on a brush, you converge to the same answers of 300, 150, and 75 if you use 300 and 150 like givens. However, I propose that the numbers in the original problem are correct. Here's an interesting, fanciful alternative for the problem with additional information provided.  And a completely different idea of what's taking so much time.  It is also completely useless, as it ignores such trivialities as geometry and walking back and forth by using a really big brush.  But who cares if math problems are useless? The new story: Shlemiel Kent (He uses the name Clark in his other job at the Daily Planet to evade the IRS) has been charged with painting dots down a roadway, and in order to paint he jumps almost instantly from place to place at a very high rate of speed.  However, this erattic motion shakes a significant portion of the paint off his brush each time he does it.  The further he jumps, the more paint is shaken off his brush and falls back into the can. His brush, however, is enormous, measuring at 300 yards long, with enough paint on it to do 300 yards in each direction.  Which is acceptable, because Shlemiel is also very strong.  As such, he must be extremely careful when painting the dots on the road. To further complicate matters, he must wait for the remaining paint to drip from his brush, which becomes increasingly time consuming as the brush runs low.  However, he cannot jump back to the can because that would drop MORE paint onto the road and ruin the work he has done. The first day Shlemiel is at his paint can and paints the far away dots very carefully with his super vision and enormous strength, constantly refilling his brush because he is at the paint can and doesn't have to worry about it being lost onto the roadway.  The exacting job takes 8 hours to paint 300 yards, and greatly pleases his boss. The next day, he jumps to the 300 yard line, leaving behind some of his paint, which falls innocently back into the can.  His brush deposits paint semi quickly at first because it is still partly full, however by the time he finishes, it is slow going. He has made only half the progress of the first day. The third day, he jumps to the 450 yard line, leaving behind most of his paint.  He toils furiously, rubbing at the ground and waiting for the paint to leech out of his enormous brush.  He makes only 1/5 of the progress of the second day, and his boss angrily fires him because he's too stupid to move the can. Now. We have given proportions and relations and can calculate some exponential relations.  Here's the relevant numbers to the problem, the number crunching comes later. The capacity of the brush is 600 yards of paint. There is a graph which can be created of paint left in the brush vs. time which is exponentially decreasing.  This is the rate at which the paint leaves the brush and roads are dotted.  The paint left in the brush at time 0 is 600 yards worth.  The instantaneous velocity of this paint at time = 0 is -300 yards/8 hours, which is negative because the paint is LEAVING the brush.  There is an area in the brush graph where a span of 8 continuous hours yields 150 yards of paint.  There is another area in the brush graph where a span of 8 hours yields 30 yards. The initial points of time where 8 continuous hours yield 150 and 30 yards in 8 hours are used to determine how much paint leaves the brush when Shlemiel jumps 300 and 450 yards, respectively.  With the interest calculation equation from micro-econ (Also the half-life calculation equation from chemistry): I = P*e^rt You then the complete brush equation. Now comes the number crunching. Paint Left = 600yards * e^r*t, but you have to solve for R using the instantaneous velocity, PaintLeft'(0) = -300.  You find out R is -1/2 without very much calculation. So Paint Left = 600yards * e^(-0.5 t), this is our brush equation. Time is in units of 8 hours. Integrating the brush equation to find 8 hours of painting that gives you 150 yards is a bit tricky if you haven't done math in a while.  You have to integrate and find a particular beginning time which gives you the right # of yards in eight hours, then use that beginning time in the Paint Left equation to figure out how much paint is still in the brush when Shlemiel leaps the distance and begins painting. You end up with an equation that looks like X = 472 * .607^T, where X is the number of yards you want to paint in eight hours and T is what you need to calculate the paint in the brush. For X = 150 yards of painting, you have to have to start with about 190 yards of paint in the brush. For X = 50 yards of painting, you have to start with about 63 yards of paint in the brush.  You can then create an equation that says how much paint he loses when he jumps, assuming that he loses no paint if he jumps 0. (0,0), (300,410), and (450,557) are your points, and there is an exponential line that happens to fit all 3 of these points.  Excel could do the regression, but I cannot, unfortunately. William Cox Tuesday, January 4, 2005 must be 3 integers from a expnonencial series, that's all radomiro Friday, February 4, 2005 Perhaps Shlemiel's job description is putting people off the original purpose of this example, that is to say, the traversal to the end point took much longer than the doing of the thing at the end. As such perhaps Shlemiel should be a road worker, and Shlemiel the road worker could put out traffic markers, and on the first day he is able to put out all 300 markers before work starts, however on the second day he puts out only 100, and on the thid day he only puts out 20. All because he has a total of 300 which are left in the site office on the side of the road, and he only collects one at a time to put out/return. The numbers still are not right, just the action more plausable. Gorf Thursday, February 10, 2005 Recent Topics Fog Creek Home