2
$\begingroup$

Here is the problem I'm working on (Satan's apple with bounded memory decision problem): Suppose I offer you slices of an apple, first $1/2$, then $1/4$, ... then $1/2^k$, etc. You want to eat as much of the apple as possible without eating the whole thing. For simplicity, lets have the utility $U(A_n) = n$ where $A_n$ is eating n slices, and $U(A_\infty) = -1$. Now suppose you can't remember the decision you made $k$ decisions back. What is the optimal strategy (only deterministic strategies are allowed)?

For $k = 0$, either you always pick a slice, or you don't pick one, so there are two strategies. The first gives $-1$ utility, the second gives $0$, so don't take.

For $k > 0$, I formalize the problem as such. Let $S:\mathbb N \to \mathbf 2$ be your sequence of moves, with $S(n) = 0$ if you don't pick the nth slice and $1$ if you do, and $S_i:\mathbf k \to \mathbf 2$ be the $k$-length substring starting at $i$. For simplicity (and I don't think it turns out to matter), let $S(i) = 0$ for $i < k$, and $S(k) = 1$. This represents $k$ being the first time you take a slice and removes the difficulty of dealing with a third option of not having been offered a slice. The goal now becomes maximizing $U(S) = \sum_i S(i)$ while still having the sum converge.

For $k=1$, we have $1\bar 0$, $U(S) = 1$ being the optimal solution

$k = 2$,

$S_1 = 01$

$S_2 = 11$

$S_3 = 10$

$S_4 = 00$

S = $011\bar 0$, $U(S) = 2$. Notice how all strings of length 2 show up.


$S_1 = 001$

$S_2 = 011$

$S_3 = 111$

$S_4 = 110$

$S_1 = 101$

$S_2 = 010$

$S_3 = 100$

$S_4 = 000$

$k = 3$, $0011101\bar 0$, $U(S) = 4$. Again, every string of length 3 shows up.


$k = 4$, $00011101100101\bar 0$, $U(S) = 8$, and all strings of length 4 show up.

If a string of length $k$ comes up more than once, other than $00\dots$, then we will get a cycle of strings containing a $1$ and $U(S)$ will not converge, so I know the above solutions are optimal.

Questions:

  1. Do these sequences have a name?
  2. Do they exist for all $n$? Will they always contain $2^{n-1}$ $1$s?
  3. How do I specify them or give some closed form for them?
  4. Is my conjecture that it doesn't matter if we start with $000\dots 1$ instead of $---\dots 1$ (where $-$ is no slice is offered, or a blank tape entry) true? This would mean that you can distinguish the first $k$ offerings from the rest by by remembering you've only been offered a slice $i < k$ times. It's strictly more information, but I couldn't do anything with it for $k = 2, 3$.
$\endgroup$
1
$\begingroup$

Cyclic Gray codes will work, not the only solution, though.

0,1

0,1,1,0 [reverse] and augment by first zero and one on the left 00,01,11,10

write as sequence (I wrote 2 periods since you need to slide windows of length 2 along to see all tuples

0011,0011

000 001 010 011 111 110 101 100

write as sequence

0001010111010,0...

$\endgroup$
0
$\begingroup$
  1. The name is De Bruijn sequences.
  2. They exist for all $n$. For your alphabet $\{0,1\}$, they contain $2^n$ symbols with $2^{n-1}$ 0's and the same 1's.
  3. It's not easy to generate them. One way is with a shift register. See Knuth's Combinatorial Algorithms pre-fascicle 2A pp.22-23. (PDF)

I don't know the answer to 4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.