Post by: kamil9876 on July 01, 2009, 12:36:36 am
- There are 3000 apples at town A
- A truckie wants to deliver apples from town A to B
- |AB|=1000km
- Max Capacity of truck is 1000apples
- Every 1km truckie eats one apple
1.) What is the maximum number of apples he can deliver to B?
2.) What's the minimum value of apples that he should start of with (rather than 3000) at A so that he can deliver 1000 apples to B?
EDIT:
Lol ok, maybe I should add that he can drop off his load somewhere and leave it there without the apples rotting or being burgled :)
Post by: Over9000 on July 01, 2009, 12:38:52 am
Long story - short:1.)0, 2.) impossible?
- There are 3000 apples at town A
- A truckie wants to deliver apples from town A to B
- |AB|=1000km
- Max Capacity of truck is 1000apples
- Every 1km truckie eats one apple
1.) What is the maximum number of apples he can deliver to B?
2.) What's the minimum value of apples that he should start of with (rather than 3000) at A so that he can deliver 1000 apples to B?
Post by: kamil9876 on July 01, 2009, 12:40:22 am
Post by: Over9000 on July 01, 2009, 12:42:11 am
Lol ok, maybe I should add that he can drop off his load somewhere and leave it there without the apples rotting or being burgled :)Oh
Post by: Mao on July 01, 2009, 12:55:07 am
1) 500
2) 4000
^^ I have a feeling that is very very wrong though
Post by: kamil9876 on July 01, 2009, 01:09:11 am
Post by: /0 on July 01, 2009, 01:41:04 am
Post by: TrueTears on July 01, 2009, 01:42:04 am
Post by: kamil9876 on July 01, 2009, 11:14:43 pm
Post by: shinny on July 02, 2009, 01:23:43 am
EDIT 2: OK whoops errors. I've gotten 666 as my best. Yesno?
Post by: kamil9876 on July 02, 2009, 01:42:03 am
Basically, we're getting pretty close to my number, but I don't know how close we're getting in terms of ideas which is what I'm more interested in hehe
Post by: shinny on July 02, 2009, 01:52:10 am
| A | 667 | B |
| 3000 | 0 | 0 |
| 2000 | 333 | 0 |
| 1000 | 666 | 0 |
| 0 | 999 | 0 |
| 0 | 0 | 666 |
Basically, what I'm doing is grabbing 1k of apples, shipping them to the point whilst eating 1 per km, then driving back to A and not eating any apples because he has none on him atm (this is legit right?). You'll see that using 666 as the drop-off yields the same result, basically because these two numbers surround 666.6 recurring, the ideal number to ensure that you have 1000 apples at the drop off point. There's a bit more explanation to why I aimed to get 1000 apples at the drop off point (might be obvious to some of you), but it's redundant anyway if you've beaten 666 kamil =\. Mind sharing what you've got atm?
EDIT: Also works for 333.3 recurring, i.e. 334 and 333. Relies on the same principle really, but using these two numbers leaves 2k at the drop off, which ultimately gives the same answer I got above.
Post by: kamil9876 on July 02, 2009, 02:05:47 am
So far I have 750. I worked that out by working it out for 2000 (since 2000=1000+1000 so only 2 journeys required which is simpler) and then extending that by figuring out what to do with the extra 1000.
Oh and Q2 I just made up myself last night so I am even less certain of that haha. Let's just treat it as a "research question" haha.
Post by: shinny on July 02, 2009, 02:09:16 am
Yes sorry I forgot to add that if there are no apples in the truck he can drive without eating (I read this problem like four years ago and I was just reminded that it had the word "temptation" in it so that explains that). I didn't see the solution to it though because it was on some Math Genius's blog and there were no solutions lol and I don't think the page is around anymore, and so my answer is not 100% certain but I have heuristically convinced myself that it is.
So far I have 750. I worked that out by working it out for 2000 (since 2000=1000+1000 so only 2 journeys required which is simpler) and then extending that by figuring out what to do with the extra 1000.
Oh and Q2 I just made up myself last night so I am even less certain of that haha. Let's just treat it as a "research question" haha.
No revealing the magician's secret? ]: Stayed awake just to find out LOL I'll come back tmrw night then.
Post by: kamil9876 on July 02, 2009, 02:12:27 am
Post by: shinny on July 02, 2009, 02:13:43 am
Hahaha I'm staying up for /0. He's been at it for over 2hours now on "who's online" :P He shows promise :D
Jokes on you if he just afk'd LOL. I'm expecting some good quality posts when I come back tmrw though...this is starting to get interesting =T
Post by: TrueTears on July 02, 2009, 02:18:34 am
....or.... he got bored and went straight to his happy time.
or maybe he took a flight back to kazak to visit the PM.
Post by: kamil9876 on July 02, 2009, 02:19:31 am
edit: I was refering to shinny's post, I dont want to know what goes on in "happy time" D:
Post by: /0 on July 02, 2009, 02:44:17 am
Post by: TrueTears on July 02, 2009, 02:45:32 am
Yeah kinda massive post with inequalities but then i just cbf... I still have no idea how you got 750Ohhh at least post it, 2 hours of posting and you delete it all, that's a waste :(
P.S you know how much kamil was waiting for your post? He feels quite disappointed now. :knuppel2: :knuppel2:
Post by: /0 on July 02, 2009, 02:48:25 am
On the first journey you set up a checkpoint at
On th second journey you some of the apples from this checkpoint to setup another one at
Somehow I got
Post by: shinny on July 02, 2009, 02:57:01 am
(http://img7.imageshack.us/img7/5329/41756123.jpg)
It's basically what I did before; with
EDIT:
OK since SMF isn't letting me post for some weird reason, I'll just edit this in and expand on what I had last night and hopefully prove it (to myself even, I might have made a mistake)...
My working out last night had 2 distinct phases.
Phase 1: 0-500
You've got 3000 apples at A, and we're moving 1000 apples at a time, 1 kilometer at a time. If you move 1000 1 kilometer away, you've got 2000 at A, and 999 1 km away. Repeat this step to get 1000 at A and 1998 at 1 km away. Now move 1000 of the apples at the 1 km mark to the 2 km mark, so you've got 1000 at A, 998 at 1 km and 999 at 2 km. Now of course, move the 1000 at A to the 1 km mark, and you're at 1997 at the 1 km mark and 999 at the 2km mark. This of course follows with 997 at the 1 km mark and 1998 at the 2 km. If you keep repeating this 'shuffle' ,you'll notice that at the step I left off at, the number for the lower numbered checkpoint decreases by 2, but the greater number checkpoint stays constant at 1998 (look at rows 6, 9 and 13). Using this pattern, if 1 is 997, 2 is 995, 3 is 993, then basically if x is y...
Phase 2: 501-1000
Ok, screw the 1 apple, just ditch it. If we go back to fetch it, it'll be eaten anyway. Time to progress with the 1998 at 500 km. Do the same shuffle movement, just easier; pick up 1000 apples to the 501 km mark to get 999 there, and 998 left at the 500 km mark. Move the ones left behind at the 500 km mark, and we get 1996 at 501 km. Obviously, we're losing 2 apples per kilometer travelled (which makes sense, since we're making 2 distinct trips whilst carrying apples for each km). So if 500=1998, 501=1996, then using x=y again...
(http://img132.imageshack.us/img132/6089/43250668.jpg)
So, 999 apples. Anyone see anything wrong with this working out? Otherwise I guess I'm now in the lead =T
Post by: /0 on July 02, 2009, 02:58:35 am
Post by: TrueTears on July 02, 2009, 03:03:13 am
I did some research and apparently 533 is the best the source can come up with http://www.keymath.com/documents/daa1/CondensedLessonPlans/DAA_CLP_00.pdfNice document, is that part of a book or something?
Post by: /0 on July 02, 2009, 03:06:57 am
I did some research and apparently 533 is the best the source can come up with http://www.keymath.com/documents/daa1/CondensedLessonPlans/DAA_CLP_00.pdfNice document, is that part of a book or something?
dunno random googling lol
Post by: kamil9876 on July 02, 2009, 03:10:22 am
Take 1000 apples and put them at 500km mark. (we have 500 apples at 500km). Now take the next 1000 and put it at 750km mark(250 at 750km now). Now take the final 1000 apples and go to 500km. Pick up 500 apples (so you are full now). Then go to 750 and pick up the 250(you are full now). Then you just have 250 to go and hence 750 will be dropped off at B.
Notice how this is an extension of 2000apples at A. Because it's the same things just no 250apples at 750.
A lot of ideas sparked from this, but just like you I had a lot of inequalities and equations etc. But I think I have made a few interesting lemmas that are on the way to proving the general algorithm for any initial condition at A.
Post by: evaporade on July 02, 2009, 03:10:59 pm
Sigh, random burst of inspiration whilst attempting to try to get to sleep. Haven't proof read this working out, but it seems roughly about right I hope.
(http://img7.imageshack.us/img7/5329/41756123.jpg)
It's basically what I did before; with1000998 checkpoints. The aim is to ALWAYS be carrying 1000 apples within the truck where ever possible. And now to hopefully get a good night's rest now that this is off my back. Also, I assume (or maybe it's the sleep deprivation talking) that this can be improved upon when you don't use integers for the number of checkpoints (e.g. a checkpoint every half km, or with an infinite number of checkpoints even), but I'm not going to bother thinking into it too much.
EDIT:
OK since SMF isn't letting me post for some weird reason, I'll just edit this in and expand on what I had last night and hopefully prove it (to myself even, I might have made a mistake)...
My working out last night had 2 distinct phases.
Phase 1: 0-500
You've got 3000 apples at A, and we're moving 1000 apples at a time, 1 kilometer at a time. If you move 1000 1 kilometer away, you've got 2000 at A, and 999 1 km away. Repeat this step to get 1000 at A and 1998 at 1 km away. Now move 1000 of the apples at the 1 km mark to the 2 km mark, so you've got 1000 at A, 998 at 1 km and 999 at 2 km. Now of course, move the 1000 at A to the 1 km mark, and you're at 1997 at the 1 km mark and 999 at the 2km mark. This of course follows with 997 at the 1 km mark and 1998 at the 2 km. If you keep repeating this 'shuffle' ,you'll notice that at the step I left off at, the number for the lower numbered checkpoint decreases by 2, but the greater number checkpoint stays constant at 1998 (look at rows 6, 9 and 13). Using this pattern, if 1 is 997, 2 is 995, 3 is 993, then basically if x is y..., which means at x=499, y=1; which is the step I skipped to.
Phase 2: 501-1000
Ok, screw the 1 apple, just ditch it. If we go back to fetch it, it'll be eaten anyway. Time to progress with the 1998 at 500 km. Do the same shuffle movement, just easier; pick up 1000 apples to the 501 km mark to get 999 there, and 998 left at the 500 km mark. Move the ones left behind at the 500 km mark, and we get 1996 at 501 km. Obviously, we're losing 2 apples per kilometer travelled (which makes sense, since we're making 2 distinct trips whilst carrying apples for each km). So if 500=1998, 501=1996, then using x=y again..., so at x=998, y=2. This means the final few steps of this process would be;
(http://img132.imageshack.us/img132/6089/43250668.jpg)
So, 999 apples. Anyone see anything wrong with this working out? Otherwise I guess I'm now in the lead =T
in the first table, From step 9 onwards all wrong
Post by: evaporade on July 02, 2009, 03:18:41 pm
(1) 834
(2) 3666
Another question: If the capacity of the truck is 999, what is the max delivery to B?
Post by: kamil9876 on July 02, 2009, 03:46:27 pm
Post by: kamil9876 on July 02, 2009, 04:01:05 pm
Post by: evaporade on July 02, 2009, 04:01:19 pm
Post by: kamil9876 on July 02, 2009, 04:41:46 pm
E.g: say you have 2000 apples instead of 3000. We can split this into two lots of 1000. Say we take one of those lots to x. That means you drop off 1000-x apples at x km. Now take the other 1000 and go the whole way. Along the way pick up the apples at x. Hence:
Which implies that if you drop off 500 apples at x=500 and then pick them up then that is the minimum x value. Ie: if you drop off 400 at x=600 you have less since you have travelled a total of 1000+600 hence eaten that many apples. However if you drop off apples before x=500 then they will not fit into the truck.
My solution for 3000 does this as well but for two drop of points since we have to make at least 3 different journeys. 750 is most with two drop off points. (imagine that instead of dropping of 250 at x=750 u drop off 600 at x=400. Then those won't fit once your at 600 since at 600 you would have 900 apples in the truck by filling up at x=500), which brings me to my lemma that the best strategy involves you filling up the capacity each time you pick up.
I think I can prove that maxmimum delivery(assuming you can only deliver once(which is probably the case for apples at A below or equal to 3000)) occurs with only 2 drop off points if 2 drop of points is the minimum number of drop off points.
Post by: shinny on July 02, 2009, 07:03:56 pm
in the first table, From step 9 onwards all wrong
Ah sigh, thanks for picking that up. Was pretty sure I had a mistake somewhere (since it didn't make sense that I was only losing 2 apples for 3 distinct trips) but I couldn't find it.
Post by: kamil9876 on July 02, 2009, 11:56:41 pm
I did some research and apparently 533 is the best the source can come up with http://www.keymath.com/documents/daa1/CondensedLessonPlans/DAA_CLP_00.pdf
I did some research and apparently 533 is the best the source can come up with http://www.keymath.com/documents/daa1/CondensedLessonPlans/DAA_CLP_00.pdf
Ahh that problem assumes that the camel needs to eat on the way back, but we havn't assumed so hence our greater number. I googled it to check what it said on the sauce i first got the question from and it said "The car driver has developed an addiction to apples: when he has apples aboard he eats 1 apple with each mile made" So our efforts are not in vain :P
Post by: evaporade on July 04, 2009, 07:55:48 am
Post by: evaporade on July 04, 2009, 08:04:56 am
I did some research and apparently 533 is the best the source can come up with http://www.keymath.com/documents/daa1/CondensedLessonPlans/DAA_CLP_00.pdf
534 because the truckie did not eat an apple the last 2/3 km (mi).
Post by: evaporade on July 04, 2009, 08:34:45 am
3666 apples, first dropoff at 1000/6 km, next dropoff at 1000/3 km from the first.
Post by: dcc on July 04, 2009, 02:44:39 pm
at the end.
Therefore, I am going to say that if you allow me to have
For sensible answers however, notice that the function is decreasing, so the best solution over the natural numbers is when
p.s. I have discovered a truly marvellous proof of the above relation, however this post is too small to contain it.
Post by: dcc on July 04, 2009, 03:00:55 pm
Post by: evaporade on July 04, 2009, 03:25:37 pm
Answer: 833 apples
Post by: dcc on July 04, 2009, 05:15:00 pm
Post by: evaporade on July 04, 2009, 07:21:07 pm
Have to make 3 forward trips (1000 apples each trip) from A to the first dropoff. Total distance = 1000/3 x 3 = 1000 km. .: 1000 apples eaten and 2000 apples left at the first dropoff point.
Have to make 2 forward trips (1000 apples each trip) from the first dropoff to the next dropoff. Total distance = 500 x 2 = 1000 km. .: 1000 apples eaten and 1000 apples left at the second dropoff point.
The remaining distance = 1000 - 1000/3 - 500 = 166 2/3 km.
One final forward trip (1000 apples) of 166 2/3 km to B. .: 166 apples eaten, 834 delivered.
I let you think about why those two dropoff points were chosen.
Post by: kamil9876 on July 04, 2009, 07:50:25 pm
Note how this is equivalent to evaporade's method, just in a different order ie: instead of going back for each load after 1km, why not 0.5km? 0.1, or even the whole 1000/3 since it's all quite arbitrary. This is because you will lose those apples in the second load by one 333.3 km of trip as much as you will by 333.3 lots of those smaller 1km trips.
Post by: evaporade on July 04, 2009, 08:06:54 pm
2.) What's the minimum value of apples that he should start of with (rather than 3000) at A so that he can deliver 1000 apples to B?
and
Another question: If the capacity of the truck is 999, what is the max delivery to B?
Post by: kamil9876 on July 04, 2009, 08:08:31 pm
imagine if he only had to travel 1km. The obvious solution would be 3 lots of 1000, rather than 6 lots of 500 of anything like that. of course 1 lot of 3000 would be best but we cannot have this, hence minimum number of possible trips (
In comparison to my attempt, or any other one for that matter, is that we went over the same domain too many times. e.g: i went over the (0,500) domain 3 times, whereas evaporade only went over the (333.3,500) domain twice and so he saved 166.7 apples apples there. Going minimum lots by 1km is a safe way to guarantee unnecesary trips, and by looking ahead we can see it has the same outcome as 3 big journeys to 1000/3.
Post by: kamil9876 on July 04, 2009, 10:30:15 pm
i know i can get 1000 apples to B with 4000 at A by splitting it up into two lots of 2000. However if there exists a better method, it must be one where the apples at A are between 4000 and 3000 since 3000 gives a max that is less than 1000. Hence we can write the number of apples at A as 3000+a.
that means initially there are 4 apples being eaten per km if we drag across the 4 loads. This occurs for a distance
Now the next 1000 apples must be eaten such that we eat 3 apples per km until we get to position
hence:
The final 1000 apples must be eaten for a distance
Solving these equations backwards to find a gives
Your version can be done by applying this too.
Post by: evaporade on July 04, 2009, 10:57:12 pm
Post by: kamil9876 on July 05, 2009, 01:24:30 pm
3000=999*3+3 hence he has 4 loads at the start. loses 4apples/km ==>
3 apples per km:
2 apples per km:
2(x_3-x_2)=999
x_3=833.25
so far he has 999 apples left. and 166.75 km to go, hence apples delivered is: 832.25. so 832 delivered and 0.25 for his smoko.
Post by: evaporade on July 05, 2009, 02:55:52 pm
Now what about the camel and the bananas?