A brain teaser just for fun
"Melon" was a donkey I received for my 4th birthday.
He was a very smart a$$ but with weird tempers. He liked melons and ate only melons, nothing but melons. As matter of fact, that was how he got his name. It wouldn't be a problem because our farm grew melons of all kinds. He always could have as much melon as and when he wanted. However, it would be problematic when I drove him to work for other farms.
Anyway. here comes the problem.
One day, I harvested 40 melons, round and sweet. I wanted to sell them in the market 20 miles away so that I could buy a pink pony. But:
1. Melon, the donkey could haul 20 melons at most;
2. he ate one melon every mile her pull;
Not knowing what to do, I had a deal with him - if he could figure out how to pull the maximum number of melons to sell in the market, then I will set him free in the market.
Do you know how? the smart donkey did.
2.一隻驢 能載２０瓜 但一里吃一瓜
4. 問題：要怎載運 才可以賣最多瓜？
He was set free at the market and last time I heard, he was somewhere in New Mexico shewing away the sweet melons there.
2.一隻驢 能載２０瓜 但一里吃一瓜 有載瓜沒載瓜往東往西往南往北 都一樣 一里吃一瓜
I will file a lawsuit against Dr. Choi for animal cruelty.
- 7 年前最佳解答
Before I start writing down the answer, first, I would like to credit the answer to Cookie. I just give the reader a better idea the logic Cookie used to solve this problem!
First, we need indicate a location on this 20 miles road by x as shown:
Due to the restrictions:
(1)donkey can only carry 20 melons
(2)donkey eats one melon for every 1 mile (no matter which direction it goes)
It will need 2 trips to move melons to location x:
1st trip: 20-2x
(donkey carries 20 melons, pulls x miles, and goes back to the starting point, so it eats 2x melons, only has (20-2x) melons left at location x)
2nd trip: 20-x
(it moves the remaining 20 melons and pull x miles, so only (20-x) melons left when it reach location x)
Now, at location x, there are (20-2x)+(20-x) = 40-3x melons left.
the key point is donkey will spend least amount of distance to move these melons. Hence it will carry the remaining melons at location x to the market in ONE trip. With this restriction, can conclude that
40-3x <= 20
(it means the remaining melons at location x shall be less or equal to 20, otherwise it will need ANOTHER trip)
Hence x >= 20/3
(it means, location x has to be equal or more than 20/3 miles).
Hence, donkey will carry (40-3x)-(20-x)=20-2x melons to the market.
(40-3x) is the remaining melons at location x
(20-x) is the miles that donkey will pull, it is also the amount of melons it will enjoy as it pulls the remaining melons to the market.
Now, if you combine the condition and formula for melons leftover at the market:
by trial and error, you will find the maximal possible value for (20-2x) is about
6.67 (when x=20/3). Since you cannot sell melons partially eaten by donkey, so you only have 6 melons to sell at the market.
- KookieLv 57 年前
you're right, still can't figure out how to write an algorithm to solve the problem.
2013-09-09 21:29:01 補充：
My method might be intuitive.
Set relay point at X
Total miles the donkey has to pull: 3x + 20 - x
The best position of x is at 20/3 miles.
2013-09-09 21:41:22 補充：
Because after consuming 20 melons to get as far as x can be, there are still 20 melons left at X point and from X to the market is a one-way pull.
The number of melons reach the market is 20 - (20 - 20/3) = 20/3
2013-09-09 21:49:35 補充：
(ignore x 20 shown on comment # 30)
|-----------X-------------------------------| 20 miles (market)
2013-09-09 23:05:15 補充：
Thanks DaSaGwa, Very good explanation.
One request: Can we ask DaSAGwa II to post the good explanation on the ANSWER area for there might be no one to come to the rescue.
Have a nice day!!!
- 知足常樂Lv 77 年前
知識長ＡＰ，nice setting, but I think DSG cannot eat so many melons... =P
- 7 年前
On your comment 001, at mile 10, you had 10 melons. But if you unload all 10 melons, the donkey will have no melons to walk back 10 miles. As matter of fact, he could consume all 10 melons walking back 10 miles.
2013-09-09 12:15:29 補充：
To a donkey, pulling 1 mile is 1 mile. It does not know if it is east or west.
If walking backward did not cost me a melon, then I will have it hauling around the globe backward for 23980 miles to the market and it will not cost me anything.
2013-09-09 12:17:26 補充：
Melon must have been a bad student - I said 1 melon per mile. Did I have to say the direction?
2013-09-09 12:57:16 補充：
Ok, let me make it clear. One mile, 1 melon.
And you cannot load 20 melon and walk 1/2 mile for free. After 1/2 mile, he consumed 1/2 melon and you will have 19.5 melon left. If you drop all melons, he will refuse to pull forward or backward - for you don't have no melons for him.
2013-09-09 12:58:38 補充：
> Don't ask me the algorithm, I haven't been optimizing it yet.
What do you mean? Must I ask for sure.
2013-09-09 17:53:18 補充：
@melon dude - but Cookie seems to claim that it is a easy question?
@cookie - my dad always said "if you cannot describe it quickly & easily, you probably do not know it well."
@happy cat - I think the donkey is eating melon alive.
2013-09-09 22:05:43 補充：
I think we've got a winner here (as smart as the Melon) indeed.
I thought anyone knowing Calculus should find it intuitive:
1. to move all Y melons X miles (when X is small) will cost Z*X melons where Z = (2* floor(Y/X) + 1).
2013-09-09 22:06:31 補充：
Note: floor function is to truncate the fraction part of a floating point number.
2013-09-09 22:10:10 補充：
and the location where Cookie @comment 032 was referring to was where Z changes from 1 to 0.
2013-09-09 22:16:49 補充：
Opps, I had a typo on 034. Correction below.
1. to move all Y melons X miles (when X is small) will cost Z*X melons where Z = (2* floor(Y/20) + 1).
2013-09-10 05:02:12 補充：
Please do answer the question, then.
2013-09-11 08:16:49 補充：
floor() = truncate() is to truncate the fraction part of non-integer to the next largest integer.
the algorithm basically is:
at any location with Y melons using donkey of max load M, to move distance d(x) will cost:
(floor(Y/M)*2+1) * d(x) melons
- DaSaGwaLv 77 年前
This is an optimization question. I am NOT sure what the answer shall be, but if I have time, I will trial and error by carrying 20 melons and let the donkey walk 10 miles, and unload the 10 melons (if drop-off is allowed). Then walk back to load the rest 20 melon and walk 10 miles again.
2013-09-09 11:32:42 補充：
At the 10 miles, pick up that 10 melons and walk the rest of 10 miles. Hence, you will have 10 melons to sell. However, this is not the best answer, you have to keep trying by cutting the distance to 5 miles, carrying 10 melons and repeating the first trial.
2013-09-09 11:33:26 補充：
I think, one of the trial-and-error processes will produce the optimized answer.
2013-09-09 11:37:37 補充：
As for me, I need to make sure that donkey will NOT eat up all my melons.
2013-09-09 11:51:36 補充：
I think it over, repeating the process might NOT produce the optimized answer. Maybe, the trick is to tell donkey to carry 20 melons to market and give it the remaining 20 melons to eat :-) ...
2013-09-09 11:55:03 補充：
Or best of all, ask donkey to carry all 40 melons to the market and it can be set free to eat those melons AFTER you sell them.
2013-09-09 12:00:09 補充：
I found this is very similar to Jeep problem, but I have NOT figured out how to apply it to this question.
2013-09-09 12:09:41 補充：
You didn't say it doesn't matter which way it walks will eat melons! If that is part of the condition, then ignore my #001 answer. I will try to find the application of Jeep problem to this one.
2013-09-09 12:23:58 補充：
You say 1 mile to the market, because you said, "She pulls", if there is nothing to pull, then I assume, no melon is needed. Anyway, I will take this restriction into consideration.
2013-09-09 12:24:47 補充：
Oh! By the way, congratulation! You have been promoted to "知識長"
2013-09-09 12:43:22 補充：
I have a question, what if, donkey walks less than 1 mile, will it still eat ONE melon?
2013-09-09 12:49:32 補充：
For example, if it carries 20 melons and walk 1/2 mile, and drop all 20 melons, then go back 1/2 mile to pick up another 20 melons. It eats ONE melons or TWO melons?
2013-09-09 13:53:09 補充：
Master AP, I think your question will end up to be zero melon. To be able to get melons to the market, you will need melons amount at least 3 times of distance it travels.
2013-09-09 13:56:51 補充：
The point of the question is to find a way to carry the watermelons to the market with the least possible amount of walking. Hence, you have to set up intermediate drop points. However, without enough of melons, it will be impossible to have any melon left for sale at the market.
2013-09-09 21:15:48 補充：
You guys are giving me a good motivation!
2013-09-09 22:13:09 補充：
I conquer that Cookie's method is perfect. He (or she) didn't have a step by step explanation, but the logic is very nice.
Let me detail his (or her) method
Based upon the drawing he (or she) has:
2013-09-09 22:15:08 補充：
assuming at X drop point, it will achieve the optimized amount of melons:
to move melon to X, it needs two trips:
1st: 20-2x (because it needs to go back to pick the next 20 melons)
2013-09-09 22:19:11 補充：
there at point X, there will be (20-2x)+(20-x) melons left. Since we need the minimal trip, so from point x to the market, we can only have one trip, this give us the constrain 40-3x <= 20. Otherwise, it will two trip for the second leg.
2013-09-09 22:22:06 補充：
for the second leg, it will carry (40-3x)-(20-x) = 20-2x melons to the market after consuming its share of melon.
Hence, the best drop point will be x >= 20/3
2013-09-09 22:23:10 補充：
Then you trial and error to find the optimized answer. It shall be between 6 and 7
2013-09-09 22:23:40 補充：
Since you cannot sell eaten melons, so the answer is 6.
2013-09-09 22:26:24 補充：
Cookie! Thanks again, you have inspired me again!
2013-09-09 22:31:02 補充：
by the way, "<=" means "less or equal". ">=" means "greater or equal"
2013-09-09 22:34:42 補充：
for (40-3x) - (20-x):
(40-3x) is amount of melons left at point x
(20-x) is the remaining distance from x to market.
(40-3x)-(20-x) means the amount of melons will have at market.
2013-09-09 22:36:07 補充：
I hope my explanation is what the logic used by Cookie!
2013-09-10 00:56:49 補充：
Look like master AP now is facing the dilemma whether to sell melons or donkey!
2013-09-10 01:01:00 補充：
Certainly! If master AP doesn't mind, DSG II always takes advantage of Cookie and DSG.
2013-09-10 10:35:13 補充：
60 melons, 21 miles to the market. All others the same. What is the answer?
I think, the answer is 7.
This donkey really eats too many melons!
2013-09-10 10:46:09 補充：
master AP! Cookie's method is simply logical thinking. You deal with lots of algorithm, how would you program it to optimizer it. After all, this kind of question can vary from one situation to the other. Logical way might NOT accommodate more complicate situation.
2013-09-10 10:48:23 補充：
For example, if you make the distance longer with more melons, then the drop point will be multiple. Logical thinking might be too complicated and too time consuming to figure the answer.
2013-09-10 11:01:34 補充：
By the way, in #039, you use "floor(y/20)". Is it the algorithm you use? It is NOT very clear to me, can you explain a little.