Suppose you have files with size $1,2,3,4\dots$ (which can be arbitrarily large and which have and can have any value that you want) and a USB-stick whose memory size $s$ you don't know, where $s$ is a positive integer and can be arbitrarily large. If $s$ is not smaller than your current file you get a message that it would be possible to write the file on the USB-stick. If your current file is larger than $s$ then you get no message. In each time unit one file can be tested. My question is, is there an algorithm which finds $s$ in as few time units as possible and would this algorithm asymptotically optimal?

  • $\begingroup$ Welcome to Computer Science! Your question looks like interesting. However, $i_i$ looks like a typo. Do you mean the number of files is $i$? Suppose all we have are two files with 1MB and 5MB. Suppose the memory size is claimed to be 4MB. How can we verify that claim? If we want to talk about the asymptotic behavior, we have to specify infinitely many problems. I am not sure if I can spot them in the question. $\endgroup$
    – John L.
    Oct 30 '18 at 8:58
  • $\begingroup$ @Apass.Jack Yes the number of files is i and $i_n$ means the size of file number $n$. I see it was a bit unclear. I meant that you also have abritrarily many files with ever memory size you want. $\endgroup$
    – wertga
    Oct 30 '18 at 9:13
  • $\begingroup$ Instead of "a files with $i_1…i_n$ MB", it should simply be "files with $1, 2, 3, \cdots$ MB" (No article "a" before "files"). You can replace all references to $i_n$ by $n$. $\endgroup$
    – John L.
    Oct 30 '18 at 9:23
  • $\begingroup$ If there is no bound to the memory size of USB, this problem cannot have a well-defined answer. Imagine your USB has 1 billion MB or a quadrillion MB or even more. There is no converging answer. $\endgroup$
    – John L.
    Oct 30 '18 at 9:29
  • $\begingroup$ (I bet that you have not tried to solve your own question diligently. In fact, I have been in the same situation many times. When I had a new question, I was just thinking, this must be an interesting problem that is apparently beyond my reach. Let me just post my question to others to see if they can solve. Bang! I missed one condition. Bang! my question did not make sense.) $\endgroup$
    – John L.
    Oct 30 '18 at 9:36

The basic observation is:

Lemma. Suppose $a_s$ is a nondecreasing sequence of integers. There exists a strategy which uses $a_s$ queries when the answer is $s$ if and only if $$ \sum_{s=1}^\infty 2^{-a_s} \leq 1. $$

In one direction, consider any strategy. For each $s$, let $w_s$ be the sequence of answers to queries made by the strategy. No word in the collection $\{w_s\}$ is a prefix of another, and so the collection forms a prefix code. The lengths $a_s = |w_s|$ therefore satisfy Kraft's inequality, $\sum_{s=1}^\infty 2^{-a_s} \leq 1$.

In the other direction, let us suppose that $\sum_{s=1}^\infty 2^{-a_s} \leq 1$. Decrease the $a_s$ if need be (while keeping them nondecreasing) so that $\sum_{s=1}^\infty 2^{-a_s} = 1$ (this is always possible); we can restore the original values later by asking dummy questions. Since the $a_s$ are nondecreasing, there is an index $S$ such that $$ \sum_{s=1}^S 2^{-a_s} = \sum_{s=S+1}^\infty 2^{-a_s} = \frac{1}{2}. $$ The first question asked by the strategy is "$s \leq S$?". If the answer is affirmative, recurse on $a_1-1,\ldots,a_S-1$; otherwise, recurse on $a_{S+1}-1,\ldots$. The left recursion is different from the right recursion, since $a_1-1,\ldots,a_S-1$ is finite; but a similar argument works, with a base case of $a_1 = 0$, in which case no more questions need be asked. $\quad \square$

Given the lemma, we have reduced the question to the topic of the paper universal codes of the natural numbers, in which it is shown that no optimal strategy exists (in a certain reasonable sense formalized in the paper).


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.