How to remember without writing, a subset of 1000 numbers [closed]

Question

P has a secret number which is between 1 and 1000 (both inclusive).

Q tries to guess the number by speaking out random numbers one by one.

R has to keep track of all the numbers that Q has spoken. An easy way to do this would be to write down all the numbers that have been spoken. But he does not have a pen and a paper.

So, he has to memorise the numbers. It is quite difficult to memorise 999 numbers.

What is an easier way for R to remember all the numbers that have been spoken if

• a) R also needs to remember the order in which the numbers have been spoken.

• b) R does not need to remember the order in which the numbers have been spoken.

Q and R are not allowed to collaborate.

Source: I came up with this puzzle myself.

Answer 1

This appears to be a question of data representation, optimizing both for efficiency (in the classical computer science sense) and human-friendliness. I'm not sure there are objective ways of measuring the latter, so I'll mostly be answering the former, instead.

For part (2) (the order of numbers does not matter), there are $2^{1000}$ states that one may be in, consisting of every possible binary option ("said already" or "not said already") among the 1000 numbers. The most computationally natural way to encode these states is in a 1000-digit long binary number, where 1 stands for "said already" and 0 stands for "not said already." This is the "only" optimal solution to this problem, in the sense that any other memory scheme for representing which state we are in could be repurposed to memorize an arbitrary 1000-digit long binary number. This is because we have constructed a bijection from the state space (the thing to be remembered, from a class of many such possible things) to the code space; the two are interchangeable. To formalize the notion of information as a measurable and conserved quantity, one may read up on Shannon entropy and information theory more generally. What we have done here is a lossless compression of the source data.

For part (1) (the order of numbers does matter), we are asked to represent one among $$K := \sum_{k=0}^{1000} k! {1000 \choose k} \approx 1.1 \times 10^{2568}$$ possible states, that is, all possible sequences of length 0 ("P hasn't said anything"), of length 1 ("P has said one number, namely X"), of length 2 ("P has said two numbers, namely X, then Y"), all the way up to length 1000, while keeping the order in mind. The informational content of this is $\log_2 (K) \approx 8530.8$, which indicates that we cannot expect to do better than memorizing a 8531-digit long binary number, given a lossless and entirely nonredundant encoding. I'm not a specialist, but some research indicates the related problem of permutation representation (this is what you're doing as a subcase, for each length-$k$ sequence) to be a nontrivial and still-studied problem concerning the tradeoffs between memory efficiency, encoding/decoding speed, etc. The Lehmer encoding is one popular way of doing this.

How would an optimal encoding compare to a more naive approach, like just writing the numbers down in a comma-separated list and taking no advantage of non-repetition? This code space consists of

$$\sum_{k=0}^{1000} 1000^k \approx 10^{3000}$$

possible codes, with an informational content of about 9965.8 bits of Shannon entropy. In other words, a perfect encoding would net us less than 15% in memory savings over this naive approach, and this is not to account for any added overhead of the encoding/decoding process. A method of loci applied to the naive method is approaching the best that humans could hope for. Arguably, employing the method of loci while conscious of the non-repetition of entries in the list is already implicitly utilizing the ideal nonredundant code space we want.

For an idea of how easily a human might actually replicate these feats, one can consider the speed world record for digit memorization. In the given link, an individual memorized 616 digits in five minutes using human-friendly methods of loci. This corresponds to memorizing $\log_2 (10^{616}) \approx 2046.3$ bits of Shannon entropy.

Answer 2

Case A:

Likely, the best way to remember Q's numbers is by using The Method of Loci. In this method, R can imagine a familiar place or route and associate each number spoken by Q with a specific location along that path. As Q speaks numbers, R mentally places them in these locations. Later, when R needs to recall the numbers and their order, they can mentally walk through the path, retrieving the numbers from each location.

Alternatively, R could use parts of their body like so: as Q says the numbers, R would associate them with body parts, typically from the bottom up (e.g., feet, ankles, shins, etc.). This might not be quite as effective as the first method described because of the length of the numbers.

Case B:

R could still use the first method, but here's a more efficient method:

If R doesn't need to remember the order in which the numbers were spoken, they can use a mnemonic technique called The Chunking Method. R can group the numbers spoken by Q into manageable chunks, such as groups of 10 or 100, and then remember these chunks instead of individual numbers. For example, if Q speaks numbers from 1 to 1000, R can remember them as ten groups of 100 numbers each. This simplifies the memorization process.

I've used the first method to memorize long strings of numbers (like Pi), and out of all the methods I've tried, I find this to be the most effective.