Page 1 of 1

Crawl math problem

PostPosted: Wednesday, 15th June 2016, 07:21
by Yermak
Hello, kids, we're going to solve a simple math task today!
One has a full inventory and is standing on top of N (N<53) unknown books. What's the minimal number of turns one needs to read all the books and keep the initial inventory? As always, picking any number of items costs one turn and dropping costs one turn per item dropped. Version is 0.18, before this was implemented (hooray!).

Edit:
All books are different. Reading a book takes 0 turns.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 07:30
by duvessa
Are all of the books different from each other?

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 08:14
by Sprucery
3N+2

e: of course only if they are all different

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 08:18
by Yermak
duvessa wrote:Are all of the books different from each other?

Yes, good note. All books are different.
Sprucery wrote:3N+2

e: of course only if they are all different

Nope. Even the simple strategy "drop N items, pick up all books, drop the books, pick items back" gives us better 2N+2 solution.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 08:35
by Sprucery
I thought you had to read the books?

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 08:42
by duvessa
Reading a book doesn't take any time.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 09:23
by Sprucery
OK next guess:
for N=1: 4
for N>1, N even: 3N/2 + 3
for N>1, N odd: 3N/2 + 3 1/2

e: no it's not that simple either

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 11:51
by ZoFy
My money is on N + ceil(2 * sqrt(N)) + 1.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 12:08
by Hands
Here are my thoughts. Let r_1 + r_2 +...+ r_k = N, and suppose r_1 < r_2 <...< r_k. Then, subject to the assumption that you never want to drop an item that is not a book when you could drop a book instead, the minimal number of turns would be (r_1+1) +...+ (r_k+1) + r_k + 1, which is N + k + r_k + 1. So you want to minimize k + r_k. This looks like it should give ceil(2 * sqrt(N)).

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 12:50
by Sandman25
Yermak wrote:Even the simple strategy "drop N items, pick up all books, drop the books, pick items back" gives us better 2N+2 solution.


I believe the simple strategy is optimal. You need to drop every book (N) and of course you need to drop another item to be able to get every book in inventory (N). What am I missing?

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 13:06
by Hands
Sandman25 wrote:
Yermak wrote:Even the simple strategy "drop N items, pick up all books, drop the books, pick items back" gives us better 2N+2 solution.


I believe the simple strategy is optimal. You need to drop every book (N) and of course you need to drop another item to be able to get every book in inventory (N). What am I missing?


Try with 10 books where you pick them up in two sets of 5. The basic approach gives 2(10)+2 = 22 turns, but doing it with two groups like this gives (5+1) +(5+1) + 5 +1 = 18 turns.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 13:09
by Magipi
Hands wrote:
Sandman25 wrote:
Yermak wrote:Even the simple strategy "drop N items, pick up all books, drop the books, pick items back" gives us better 2N+2 solution.


I believe the simple strategy is optimal. You need to drop every book (N) and of course you need to drop another item to be able to get every book in inventory (N). What am I missing?


Try with 10 books where you pick them up in two sets of 5. The basic approach gives 2(10)+2 = 22 turns, but doing it with two groups like this gives (5+1) +(5+1) + 5 +1 = 18 turns.

Some explanation would be nice, these are just numbers and I cannot figure out which of them represents what.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 13:22
by Hands
Ok, in my original post you partition the set of books into k subsets, we use r_1,...,r_k to denote the size of the subsets. We assume that the r values are in ascending order of size. Then in the first turn you drop r_1 objects then pick up r_1 books, in the 2nd turn you drop r_2 objects (including all the books from turn 1) then pick up a new r_2 books. You keep doing this till you've picked up all the books. This takes (r_1+1)+...+(r_k+1) turns. But you still have to drop the last load of books and pick up your original stuff, so you add an extra r_k +1. Since r_1+...+r_k = N this simplifies to N + r_k + k + 1, and this will be minimized when r_k + k is minimal. I think but haven't proved that minimizing this will give 2*sqrt(N) rounded up.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 13:32
by Sandman25
I see, we are trying to combine dropping books and dropping items to make room for more books.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 14:34
by Lacuenta
Yermak wrote:Hello, kids, we're going to solve a simple math task today!
One has a full inventory and is standing on top of N (N<53) unknown books. What's the minimal number of turns one needs to read all the books and keep the initial inventory? As always, picking any number of items costs one turn and dropping costs one turn per item dropped. Version is 0.18, before this was implemented (hooray!).

Edit:
All books are different. Reading a book takes 0 turns.

answer: 0
use ctrl+m

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 14:43
by ZoFy
Hands wrote:Ok, in my original post you partition the set of books into k subsets, we use r_1,...,r_k to denote the size of the subsets. We assume that the r values are in ascending order of size.
...
Since r_1+...+r_k = N this simplifies to N + r_k + k + 1, and this will be minimized when r_k + k is minimal. I think but haven't proved that minimizing this will give 2*sqrt(N) rounded up.

Since r_1 <= r_2 <= ... <= r_k and r_1 + r_2 + ... + r_k = N, r_k >= N/k.
r_k + k >= 2 * sqrt(r_k * k) >= 2 * sqrt(N) [AM—GM inequality], so the sum can't go lower than 2 * sqrt(N) rounded up.
Picking k = floor(sqrt(N)) and r_i between floor(N/k) and ceil(N/k) would give us that possible minimum:
  Code:
1) If N = k^2, r_k = k and k + r_k = 2 * k = 2 * sqrt(N) = ceil(2 * sqrt(N))
2) If k^2 + 1 <= N <= k^2 + k, r_k = k + 1 and sqrt(N) < k + 1/2, so ceil(2 * sqrt(N)) = 2 * k + 1 = k + r_k
3) If k^2 + k + 1 <= N <= k^2 + 2 * k, r_k = k + 2 and sqrt(N) > k + 1/2, so ceil(2 * sqrt(N)) = 2 * k + 2 = k + r_k


Spoiler: show
My apologies for a weird explanation, i've never taken math lessons in english.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 16:42
by 4Hooves2Appendages
Sandman25 wrote:I see, we are trying to combine dropping books and dropping items to make room for more books.

Two problems with that:
- There's no advantage to combining dropping items and books. Maybe you meant picking up?
- In the case of an even number of books it's also not necessary to combine them.

The reason why this problem was (at least to me) a bit counter-intuitive is this: At first it seemed that maximising the number of items picked up in one go is the right strategy, because you get to pick up stuff 'for free'. But on examination the 'rate determining' step is dropping items and the fastest solutions balance time spent dropping items with picking up stacks of items. The total time spent dropping books is fixed, but the time spent dropping non-book items can be varied.

Imagine you have 30 books and split them in two stacks. Now you drop 15 items, then process the books, in two stacks, then pick up the 15 items. You saved dropping 15 items (15 turns), at the cost of spending 2 turns picking up 15 books. Total overhead: 17 (drop 15 items + 2 turns picking up books)
Now imagine you split your books into 3 equal stacks of 10. Drop 10 items, process the books, pick up 10 items. You saved dropping 20 items (20 turns) at the cost of spending 3 turns picking up two stacks of 10 books. Total overhead: 13 (drop 10 items + 3 turns picking up books)
Split books into 5 stacks of 6 books. Drop 6 items, process books, pick up 6 items. Saved dropping 24 items (24 turns) at the cost of spending 5 turns picking up 5 stacks. Total overhead: 11 (drop 6 items + 5 turns picking up stacks of books)
The minimum is where the sum of turns spent dropping inventory items and turns spent picking up books is the smallest.

Maybe I'm talking nonsense.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 17:01
by Sandman25
4Hooves2Appendages wrote:- There's no advantage to combining dropping items and books. Maybe you meant picking up?


No, I meant dropping. My initial assumption was that we need to drop N books and N items to make room but in reality we can drop less than 2 N items because dropped book can be treated as item dropped to make room.

Edit. Maybe I used word "combine" in wrong meaning, I didn't mean that we should drop books and other items as one operation.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 18:24
by 4Hooves2Appendages
Well, overall you always have to drop N books. But you can choose anywhere between 1 and N non-book items to drop.

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 18:26
by ydeve
Can't you read books off the floor now?

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 20:09
by pubby
You are a kobold in a dungeon. The dungeon is in the shape of a ring and you do not know how many rooms there are in the dungeon.

Some of the rooms have their doors open, some have their doors closed. Your job is to close all of the doors. I remind you again that the dungeon is ring shaped, and you do not know how many rooms there are in the dungeon.

How would you close all of the doors, and in the end inform your superior (via your zot phone) that you have completed your job?

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 20:58
by CanOfWorms
drop your phone in the room you start in, walk in a given direction while opening all the doors, once you find your phone again you know every door is open so pick it up and close all the doors

if you're not allowed to drop your phone then do the following:
close a door at your starting point, this door is your "phone"
* now go in a fixed direction until you see a closed door and remember how far you are from the initial closed door (say by counting the number of doors)
open that door and go back to your starting point; if the door is not closed anymore then you've seen every door (and they're all open) so just close every door
otherwise start from * again

joke solution: read magic mapping

Re: Crawl math problem

PostPosted: Wednesday, 15th June 2016, 23:58
by duvessa
CanOfWorms wrote:if you're not allowed to drop your phone then do the following:
close a door at your starting point, this door is your "phone"
* now go in a fixed direction until you see a closed door and remember how far you are from the initial closed door (say by counting the number of doors)
open that door and go back to your starting point; if the door is not closed anymore then you've seen every door (and they're all open) so just close every door
otherwise start from * again
I would just piss on the floor

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 00:06
by pubby
A nondescript kobold choo-choo is travelling along the snakepit railrway at 55 MPH towards zot station. Onboard, the kobold has three devices:

1. a turing machine with infinite linear-access tape memory
2. a bag full of 5 uniquely colored marbles
3. an omniscient advisor that will answer any yes/no question truthfully

At zot station, a red-green flare has been fired off and is travelling towards the kobold in a parabolic arc with a horizontal speed of 105 mph, signalling that the ecumencial bridge is out.

What one weird trick can be applied to force the kobold to stop the choo choo and save the life of the marbles?

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 00:18
by duvessa
A boulder beetle is rolling towards 5 goblins. There are three levers, one of which will divert the boulder beetle's course so that it only hits 1 hobgoblin. The other two levers are fake and have no effect. You may pull only one lever. After choosing your lever, one of the other levers is revealed as fake. Do you switch your choice?

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 00:19
by Hellmonk
pubby wrote:A nondescript kobold choo-choo is travelling along the snakepit railrway at 55 MPH towards zot station. Onboard, the kobold has three devices:

1. a turing machine with infinite linear-access tape memory
2. a bag full of 5 uniquely colored marbles
3. an omniscient advisor that will answer any yes/no question truthfully

At zot station, a red-green flare has been fired off and is travelling towards the kobold in a parabolic arc with a horizontal speed of 105 mph, signalling that the ecumencial bridge is out.

What one weird trick can be applied to force the kobold to stop the choo choo and save the life of the marbles?

Wand of enslavement?

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 00:19
by Hellmonk
duvessa wrote:A boulder beetle is rolling towards 5 goblins. There are three levers, one of which will divert the boulder beetle's course so that it only hits 1 hobgoblin. The other two levers are fake and have no effect. You may pull only one lever. After choosing your lever, one of the other levers is revealed as fake. Do you switch your choice?

No, because goblins deserve death.

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 01:11
by crate
Hellmonk wrote:
duvessa wrote:A boulder beetle is rolling towards 5 goblins. There are three levers, one of which will divert the boulder beetle's course so that it only hits 1 hobgoblin. The other two levers are fake and have no effect. You may pull only one lever. After choosing your lever, one of the other levers is revealed as fake. Do you switch your choice?

No, because goblins deserve death.

In this case you should clearly switch because then you have a 100% chance of picking a fake lever!

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 01:14
by Arrhythmia
A trolley cart is heading down a path, on which there are Aleph 1 people. You may pull a lever to direct it onto another path, on which there are Aleph 0 people. Should you pull the lever? You may assume the Axiom of Choice and the Generalized Continuum Hypothesis for simplicity.

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 01:47
by Rast
duvessa wrote:A boulder beetle is rolling towards 5 goblins. There are three levers, one of which will divert the boulder beetle's course so that it only hits 1 hobgoblin. The other two levers are fake and have no effect. You may pull only one lever. After choosing your lever, one of the other levers is revealed as fake. Do you switch your choice?


Would I get xp for the 5 goblins?

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 03:09
by PleasingFungus
duvessa wrote:A boulder beetle is rolling towards 5 goblins. There are three levers, one of which will divert the boulder beetle's course so that it only hits 1 hobgoblin. The other two levers are fake and have no effect. You may pull only one lever. After choosing your lever, one of the other levers is revealed as fake. Do you switch your choice?


http://existentialcomics.com/comic/106

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 03:11
by PleasingFungus
is it possible to activate +fly while on a treadmill

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 03:14
by Arrhythmia
PleasingFungus wrote:
duvessa wrote:A boulder beetle is rolling towards 5 goblins. There are three levers, one of which will divert the boulder beetle's course so that it only hits 1 hobgoblin. The other two levers are fake and have no effect. You may pull only one lever. After choosing your lever, one of the other levers is revealed as fake. Do you switch your choice?


http://existentialcomics.com/comic/106


i really wish this guy was a better artist :(

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 06:51
by 4Hooves2Appendages
crate wrote:
Hellmonk wrote:
duvessa wrote:A boulder beetle is rolling towards 5 goblins. There are three levers, one of which will divert the boulder beetle's course so that it only hits 1 hobgoblin. The other two levers are fake and have no effect. You may pull only one lever. After choosing your lever, one of the other levers is revealed as fake. Do you switch your choice?

No, because goblins deserve death.

In this case you should clearly switch because then you have a 100% 66% chance of picking a fake lever!

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 07:32
by ydeve
If you switch and pick the non-revealed one you have a 50% chance of picking a fake lever.
If you switch and pick the revealed-as-fake one then you have a 100% chance.

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 07:40
by duvessa
ydeve wrote:If you switch and pick the non-revealed one you have a 50% chance of picking a fake lever.
this thread is a trolley wreck

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 07:47
by ydeve
Oops, 33%. I should go to bed now.

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 07:54
by Hands
ZoFy wrote:
Hands wrote:Ok, in my original post you partition the set of books into k subsets, we use r_1,...,r_k to denote the size of the subsets. We assume that the r values are in ascending order of size.
...
Since r_1+...+r_k = N this simplifies to N + r_k + k + 1, and this will be minimized when r_k + k is minimal. I think but haven't proved that minimizing this will give 2*sqrt(N) rounded up.

Since r_1 <= r_2 <= ... <= r_k and r_1 + r_2 + ... + r_k = N, r_k >= N/k.
r_k + k >= 2 * sqrt(r_k * k) >= 2 * sqrt(N) [AM—GM inequality], so the sum can't go lower than 2 * sqrt(N) rounded up.
Picking k = floor(sqrt(N)) and r_i between floor(N/k) and ceil(N/k) would give us that possible minimum:
  Code:
1) If N = k^2, r_k = k and k + r_k = 2 * k = 2 * sqrt(N) = ceil(2 * sqrt(N))
2) If k^2 + 1 <= N <= k^2 + k, r_k = k + 1 and sqrt(N) < k + 1/2, so ceil(2 * sqrt(N)) = 2 * k + 1 = k + r_k
3) If k^2 + k + 1 <= N <= k^2 + 2 * k, r_k = k + 2 and sqrt(N) > k + 1/2, so ceil(2 * sqrt(N)) = 2 * k + 2 = k + r_k


Spoiler: show
My apologies for a weird explanation, i've never taken math lessons in english.


That makes sense.

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 07:57
by Sprucery
duvessa wrote:A boulder beetle is rolling towards 5 goblins. There are three levers, one of which will divert the boulder beetle's course so that it only hits 1 hobgoblin. The other two levers are fake and have no effect. You may pull only one lever. After choosing your lever, one of the other levers is revealed as fake. Do you switch your choice?

At first you have a 1/3 chance of picking the real lever and a 2/3 chance of picking a fake one. You should not use the original lever is it was a fake one. The chance for this is 2/3 so you should pull the other one. Unless you just want to see the goblins die, in which case you should not use any lever.

Re: Crawl math problem

PostPosted: Thursday, 16th June 2016, 08:00
by ydeve
But if you pull a fake lever out of the ground you can use it to bludgeon the corpses. Or go after that hobgoblin that the cart didn't kill.

Re: Crawl math problem

PostPosted: Tuesday, 21st June 2016, 07:44
by rexdaemonia
Just do project euler it's like the same thing as this thread https://projecteuler.net/

Re: Crawl math problem

PostPosted: Tuesday, 21st June 2016, 22:35
by Arrhythmia
did you know that 99% of groups with order less than 2000 have order 1024? fucked up IMO

Re: Crawl math problem

PostPosted: Tuesday, 21st June 2016, 23:38
by archaeo
mathcrawl...

Re: Crawl math problem

PostPosted: Wednesday, 22nd June 2016, 00:10
by Arrhythmia
archaeo wrote:mathcrawl...


i think you mean bestcrawl

Re: Crawl math problem

PostPosted: Thursday, 23rd June 2016, 04:09
by xentronium
If you have X cmut potions, and you don't need to save any of them, how many purple chunks should you eat?

Re: Crawl math problem

PostPosted: Thursday, 23rd June 2016, 04:48
by PleasingFungus
arrhy and arch should stop having basically the same av, imo. their name situation is bad enough

Re: Crawl math problem

PostPosted: Thursday, 23rd June 2016, 04:58
by Rast
PleasingFungus wrote:arrhy and arch should stop having basically the same av, imo. their name situation is bad enough


Your name is too similar to ProzacElf. I get confused sometimes in IRC.

Re: Crawl math problem

PostPosted: Thursday, 23rd June 2016, 05:37
by Arrhythmia
PleasingFungus wrote:arrhy and arch should stop having basically the same av, imo. their name situation is bad enough



be thankful we aren't both mods