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.
:::
@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.
:::
-
Here's a counter puzzle for @jon-nyc :
How many different scenarios/orders are there for n scientists and r rounds?
I have worked out the solution for n=2. It's interesting.
-
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.
@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.
