But i feel like that I can use this method only for establishing the lower and upper bounds on the number of attempts needed. I don't see yet how this method helps in achieving one construction which solves the problem.

I see using the 'cube' that one non-key number, say xyz, helps eliminate 22 numbers (which are xy*, x*z, *yz).

Thus, we can arrive at a lower bound which is 512/22 = 23.27 or 24.

Further, it also helps in calculation of upper bound (the brute force 64) in a different way. (I feel I may have done something fishy below. Please verify)

Every node which is a non-key, (say xyz again), helps eliminating 3 lines passing through that node.

There is a total of 16 xy lines on each z-slice. Thus 8 z-slices contribute 16*8 xy-lines. Next, all the 64 points on the xy-plane have a z-line passing through them.

Thus, total number of lines in the figure is 16*8 64 = 192.
Since every choice helps in reasoning about 3 lines, we can remove all the lines in 192/3 = 64 moves.

But I am not entirely convinced by my reasoning. Eliminating the lines passing through one node and eliminating the 22 values on those lines looks much the same. Then why is one calculation giving lower bound and the other one the upper bound?

Am i missing something? (Must be)

As I see it, if there are 16 xy-lines in every z-section, you do not need z-lines to cover all the points. This is wasteful.

Consider only the planes z = 2, 3, ..., 8. This gives you 7×8 = 56 distinct z-lines. These lines meet the z = 1 section in 56 points. Choose the lines so as to leave a line (x-line or y-line) in z = 1 section. Which is pretty easy. This shows that you can do with 57 lines. But you can do better.

Nice to see 'the cube way' getting done in only 57.

If time permits, can you please try posting the solution 'the cube way'. If not, please post a hint.

BR
-Akash

Think of the cube as being cut into 8 smaller cubes.

There are 16 guess with combinations of numbers 1, 2, 3, 4 whose sum is a multiple of 4. The number of such combinations is 16 because choosing two number into a key fixes the third number.

Now translate these combinations by the vector (4, 4, 4). All in all, you have 32 combinations that cover the cube. The proof depends on the observation that the solution contains either 2 or more numbers from the set {1, 2, 3, 4} or 2 or more numbers from the set {5, 6, 7, 8}.

The part that 32 is the absolute minimum is more involved.

I see how it works.

The proof of minimality is not in my reach yet. Am trying it. Will get back if I need more help.

BTW I tried generalising the problem a little bit in (now I think vain) hope that the general version might be actually easier than the version stated in the problem.

I was trying the case when the Key length is L and the demon's memory is so bad that he says yes even if d (1 <= d < L) digits are spoken wrongly in a turn.

My approach was again to invoke recursion (a la dynamic programming) argument to handle the problem as I thought the cube argument would be tough to use in the general case. But hell, no recursive solution came up. Maybe it is a fool's errand to try using recursion here...

BTW I still keep thinking that a recurrence relation for this problem should exist. The reason is I have seen similar problems (I believe) where recursion works.

For example, the orb puzzle - wherein you have 2 orbs which break only when dropped from a threshold height and won't break unless that height is reached. You need to use these 2 orbs and determine in fewest drops the threshold height from which they start breaking.

The trick is to setup a recurrence to solve the 'reverse problem' of determining maximum height which you can scale using 2 orbs and 'd drops'. The case where 'd drops' lead to scaling a height more than 100 the first time leads to the answer.

I tried a similar approach as outlined in my first post but eventually gave up as a bad idea.

But to end it, I would definitely say that your cube approach was too cute...

Good day
-Akash

Unfotunately the solution is not mine. I have Winkler's book. But you can think of how one can (combinatorially) reorganize a given configuration while still maintaining its properties, like being a cover.

Thanks again for your help throughout with this puzzle and thanks for that tip - I believe I may put it to use in solving puzzles/problems in future. Its good to have it in your toolbox.

BTW I had an email exchange with Peter Winkler regarding the same puzzle. There also, I asked about the utility of a recursive method (in both the original and the generalized version above) if at all one was applicable.

He answered in negative, I am quoting him below in order that one is not misled by attempting a problem not likely to yield to a particular methodology.

"I'm afraid that a recursion is unlikely for this problem; it's essentially
a problem in coding theory, which is quite a difficult subject. Coding
problems often have clever solutions in some cases and nothing but
crude bounds in many other cases."

Good day
-Akash