Puzzle Time - Read, Increment, Write
-
One hundred scientists are working at a high-tech project. Proud of their ability to do mental arithmetic, they institute a challenge. In a small and noisy engine room, there is a blackboard with the number zero written on it. Each scientist performs the following routine one hundred times:
1. Enter the engine room, read the number on the blackboard, and leave the engine room.
2. Increment the memorized number by 37 (mentally).
3. Enter the engine room, erase the number on the blackboard, write the incremented value on the blackboard, and leave the engine room.The scientists work at their own pace, independent of each other; that is, their steps can be interleaved. The engine room is so small that at each moment, only one scientist can be in there. So, occasionally, they will have to wait for each other.
When they are all done, the largest number that could be on the blackboard is 370,000.
What is the smallest possible final value?
-
I'm getting Dijkstra-semaphore-vibes from this task!
:::
Probably I'm not getting something, but isn't it obviously just 37? For instance, if the first guy who enters-to-read is the last guy who enters-to-write.
Or is the point that the scientists have to queue up immediately after step 1? But even then, if all 100 scientists queue up immediately, they'll all read 0 and write 37.
:::
-
DON’T let them eat cake.
- RFK Jr -
:::
Thinking about it a little, I think the problem can be expressed in terms of a formal languages of balanced parantheses. Something like a Dyck language. I vaguely remember that there's a generalization of Dyck languages to different kinds of parentheses. I believe there is something like the language D_n, which is the balanced parenthesis expressions with n different kinds of parentheses. So for this scenario, we would need to consider the language D_100, featuring 100 different kinds of parentheses. There's a 1:1 correspondence between the scenarios that can unfold in Jon's story and the words of D_100 where each parenthesis shows up 100 times..
Hmmm....
::: -
-
Here’s a hint.
:::
Let M(n,r) be the minimum final number with n scientists doing r rounds of read, increment, write. Observe that M(n+1, r) <= M(n,r) since given a minimal sequence with r rounds and n scientists, you can add another scientist with no impact by having all his activity occur after the read associated with final write but before that final write.
:::
-
@jon-nyc said in Puzzle Time - Read, Increment, Write:
When they are all done, the largest number that could be on the blackboard is 370,000.
Hmmm, I will think some more (and probably not still be able to solve it),
:::
but I am not sure how it could be smaller than 370,000.
100 * 100 * 37
:::
-
Recall the read/increment, and write are separate. And whatever happens to the number between your read and your write is essentially lost when you write.
To put it another way, imagine you are one of the hundred. You go in first, see it at zero. Walk out. Then (say) all the other 99 do all 100 of their cycles. IOW, they’re done now. Then you finally walk back in, erase whatever number they got to, and write 37. So you basically reversed all of their work. Made it as if they had never even participated. And you’ve got 99 cycles left which will bring the grand total to 3700. That was basically Ax’s proposal.
But it can go even smaller than that.
-
@jon-nyc said in Puzzle Time - Read, Increment, Write:
Here’s a hint.
:::
Let M(n,r) be the minimum final number with n scientists doing r rounds of read, increment, write. Observe that M(n+1, r) <= M(n,r) since given a minimal sequence with r rounds and n scientists, you can add another scientist with no impact by having all his activity occur after the read associated with final write but before that final write.
:::
So you want us to express M(n,r) as a recurrence relation and then solve it?
I assume it's something like this:
M(n+1,r) = minimum{ M(n,r) , -- the trick -- }
M(n,r+1) = minimum { M(n,a) + M(n,b) | a+b=r+1} union { -- the-other-trick -- } -
:::
I made a little progress.
In the scenario with 2 scientists and 3 rounds, Ax's method would yield a bound of 3*37.
If we denote by R<n> the event of scientist n entering the room to read and W<n> the event of scientist n entering the room two write, then this sequence of events yields a final number of just 2*27.
R0,R1,W0,R0,W0,W1,R0,R1,W1,R1,W1,W0
Here's a sequence that yields just 2*37 for 4 rounds of 2 scientists:
R0,R1,W0,R0,W0,R0,W0,W1,R0,R1,W1,R1,W1,R1,W1,W0
Even for five rounds, 2*37 is sufficient.
R0,R1,W0,R0,W0,R0,W0,R0,W0,W1,R0,R1,W1,R1,W1,R1,W1,R1,W1,W0
And finally, one for six rounds with 2*37.
R0,R1,W0,R0,W0,R0,W0,R0,W0,R0,W0,W1,R0,R1,W1,R1,W1,R1,W1,R1,W1,R1,W1,W0
Based on this pattern, I assume that 2*37 is also sufficient for 100 rounds of 2 scientists and, since more scientists can be added without increasing the number, also in the original case with 100 rounds and 100 scientists.
:::
-
I think I got it.
:::
With my nomenclature from above, here's how to get by with 2*37 for 100 rounds with 2 scientists:
R0
99 times R1,W1
W0
R1
99 times R0,W0
W1For the remaining 98 scientists, insert them somewhere before a "W"rite in that sequence.
:::
-
-
DON’T let them eat cake.
- RFK Jr -
@jon-nyc said in Puzzle Time - Read, Increment, Write:
As for your question, seems like it’s the problem of how many ways there are to interleave two (or k) ordered lists.
Yes. Both lists have length 2r. Once the positions of the first list in the interleaved list are fixed, the positions of the elements of the second list are fixed, too. Hence the number we are looking for is binomial(4r,2r). Which turns out to be (r+1) * C(r), where C(r) is the r-th Catalan number. Which in turn brings us back to my reference to Dyck languages, since the number of distinct Dyck words with exactly n pairs of parentheses is the n-th Catalan number.
