Let me first pose the problem:
The king of some faraway land is bored, so he decides to setup a little game for his own amusement. These are the rules of the game:
7 prisoners will be seated at a round table. Each prisoner will have a hat placed on their head. Each hat is one of seven possible colors. The prisoners can see everyone else's hat, but they cannot see their own. The prisoners will then write on a piece of paper what they think their hat color is, and hand the paper to the king. If any of the prisoners guesses their hat color correctly, they will all go free. Otherwise, they are all executed on the spot.
If the prisoners use the naive strategy of guessing randomly, then they have a survival chance of 66%. Can you think of a strategy such that the prisoners have a 100% chance of survival?
When given this problem, my brain subconsciously pointed towards modular arithmetic and I gave a satisfactory answer that solved the problem. My answer matched the answers given in this Math SE answer: Rainbow Hats Puzzle
A person I was explaining this problem to said that the answer worked in retrospect, but it required a logical leap to arrive at the answer. Introspection revealed that I too took a subconscious shortcut towards modular arithmetic without natural deduction.
My question is this: Is there a way to solve this systematically without a logic leap and with natural deduction or inferences. Understanding the modular arithmetic answer is easy in retrospect, but explaining how one might arrive at the solution is much harder.