Puzzle Time - Read, Increment, Write
-
:::
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....
::: -
Don’t know much about Dyke languages but intuitively I see the analogy of the open and close parens.
-
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 -- } -
Not necessarily. The implication of that hint that I was trying to communicate is that if you find a really low number with, say, 2 scientists, you’d be able to preserve that low number at 100 (or potentially do better).
-
So if you can convince yourself that a solution you found for a smaller n must be a lower bound for any n, you are done.
-
:::
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.
:::
-
-
Your answer is what I got.
As for your question, seems like it’s the problem of how many ways there are to interleave two (or k) ordered lists.
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.
-
Repeating the answer w/o Klaus’s symbols:
2 scientists. Both go in and see zero. One does 99 of his 100 full cycles, taking the number high.
The 2nd comes in finally does his first write, replacing that high number with 37. 1st guy comes in for his last read and sees 37, leaves. 2nd guy does the remainder of his cycles, taking the number high again.
1st guy comes in, erases the high number, and writes 74 as his final write.
As we discussed earlier, when you expand to 100 scientists just have them do all their 100 cycles after the final guy’s last read but before his final write.
