I’m a computer science undergrad student learning basic programming, with a bit of basic probability background from high school, but I have a task that requires me to write a code to solve a Blind Bartender problem for non-power 2 cases(with relevant test cases which I would not reveal here). I figured that what I’m lacking is probably mathematics concept instead of programming concepts.
Here is a general description of the blind bartender problem for $n=4$ case and its solution: http://brainden.com/forum/topic/16626-blind-bartender/
This written solution for one of the posts made on this site can be translated into a sequence of moves in programming. (the maximum number of moves to solve any $n=4$ case is 7)
1) Turn over two diagonal glasses $(1010)$
2) Turn over two adjacent glasses $(1100)$
3) Turn over two diagonal glasses $(1010)$
4) Turn over one glass $(1000)$
5) Turn over two diagonal glasses $(1010)$
6) Turn over two adjacent glasses $(1100)$
7) Turn over two diagonal glasses $(1010)$
Resulting sequence of moves: $(1010),(1100),(1010),(1000),(1010),(1100),(1010)$
where 1 denotes flip the glass at the particular position/0 to denote unchanged
For a $n= 2_i^x$, I am hinted that the sequence of moves required is similar to the towers of Hanoi backup rotation scheme (backup rotation scheme in link). Observe that 3 tape Hanoi schedule is similar to $n=4$ Blind Bartender where $A=(1010),B=(1100),C=(1000).$
https://en.wikipedia.org/wiki/Backup_rotation_scheme#Grandfather-father-sonTable
Extrapolating from the given backup rotation schemes, a 7 tape Hanoi will be similar to $n=8$ Blind Bartender with the following sequence of moves
$$A=(10101010)$$
$$B=(11001100)$$
$$C=(10001000)$$
$$D=(11110000)$$
$$E=(10100000)$$
$$F=(11000000)$$
$$G=(10000000)$$
Now for my main questions
1)How does one derive visually the essential type of moves required for $n=4$ case? The sequence of moves(consisting of 1 and 0) for $n=4$ only made some sense to me when I saw the connection provided with a visual solution(diagonals, adjacent). Still, it’s a circular problem, so how do u “linearise” it(Like $1100$ can essentially be $1001$ in a circle, how do u tell whether something is a repetition or not? Why would something like odd number of 1s like $$(11100000)$$ in $n=8$ be considered trivial and not be used for the problem?). This question pertains to the above n=4 case and other $n=2_i^x$ cases or even $n= \text{non}-2_i^x$ cases I’m currently trying to figure out. I learnt some basic probability, but don’t know what concepts apply here.
2)I also saw an interesting segment from the following online article. The non-$2_i^x$ cases I’m trying to figure out are 7,10,13. Does this have to do with this paragraph in the article?
https://www.sciencedirect.com/science/article/pii/0097316595900926
Pg 3 of pdf:
The point is to successively eliminate possibilities. The middle flip, where only one glass is flipped, is the transition from eliminating possibilities that started with an even number of glasses up to those that start with an odd number of glasses up. At the start we assume that an even number of glasses are up, which can only be $2$. If it were $0$ or $4$ we would already have won. If there are $2$ they can be diagonal or neighboring. If they are diagonal, the first move will win. If they are neighboring, the first move will leave them neighboring, the second will either win or leave them diagonal, and the third (if required) will win. If we haven't won by the third move we know that there were an odd number up to start with and there still are. Flipping one glass then makes the number up even. If it doesn't win we do the same process as we did before.