'Invisible' Logic In Combinatorics

(This is Lucas.) Hi! In this post, I'm going to try and highlight a small but important part of my thought process when attempting Olympiad problems. 

Let's begin with a question:

Question 1

Each cell of a 9 by 9 square is initially filled with ‘+1’ or ‘−1’. We define a move as follows: We choose some of the 81 cells. For each chosen cell, we calculate the product of its neighbours (neighbours are cells which share a side). Then, the products calculated simultaneously replace the original values in the chosen cells. Is it always possible to make all values in the 9 by 9 square equal to ‘+1’ through finitely many moves?

Initial Thoughts

It should hopefully be intuitive to try and find an invariant state, that is, a state where each cell is already equal to the product of its neighbours. (Of course, we want one that isn't the trivial state where the entire board is "+1".) Clearly if such a state exists, no moves will be able to affect it, so it can never become identically "+1". However, that still leaves us with $2^{81}$ or so possibilities. So what can we do to narrow down the possibility space?

Well, it would be nice if the state we were looking for was symmetric, for instance, along the horizontal axis. But sadly, we can't be sure if this is the case... or can we?

Application of The Thing

Assume we have a nontrivial invariant state $S$ that isn't symmetrical. Let $S'$ be $S$ mirrored about the horizontal axis. Then, consider multiplying the corresponding elements of $S$ and $S'$ to form a new 9 by 9 grid. The new grid is clearly symmetrical as desired, and is also invariant. Additionally, since the old grid was not symmetrical, $S$ and $S'$ differ, meaning our new grid is also nontrivial! As such, the existence of a non-symmetric grid implies the existence of a symmetric one, so we are 'safe' in assuming the grid is symmetrical. We can apply the same logic to deduce vertical and even diagonal symmetry, making a daunting search into a relatively trivial one.

This is what I'm hoping to highlight today: logic that's applied to help you narrow down what you're looking for, which may or may not even go in the proof. Of course, if this logic does lead you to find an invariant state, you won't actually have to describe any of this process in the proof — simply presenting the invariant state and describing why it solves the question will suffice. And if it turns out there's no invariant state, you would presumably just move on to another approach, and this reasoning would likewise go unwritten.

The form and execution of this kind of reasoning varies wildly depending on the question. However, I think there is still value in drawing attention to it — I find that especially in tougher questions, where it's less clear what approach is correct, there is value in the assurance that a chosen approach (which may otherwise just be a sensible guess) is actually the correct path to go down. Other than the mental assurance provided, it may mitigate effort that might otherwise be wasted searching for other approaches.

That example may be too simple to be illustrative, so let's take a look at another question (this may be familiar to some):

Question 2

(239 2022) 239 wise men stand in a circle. The king places a hat of one of 16 colours on each man’s head. Each wise man does not know the colour of his hat, but can see the colours of the 2 hats of his neighbours. They then independently each write down one of the 16 colours. The wise men gain one point for each man whose guess does not match their hat (i.e. they are trying to wrongly guess their own hat color). The wise men were allowed to discuss a strategy in advance. What is the maximum score they can guarantee?

Initial Thoughts

Let's go through the problem solving process. Trying small cases (as one should), we can glean some insight from the case where there are only 2 wise men. There, one man can copy the other man's hat color as his guess, while the other man can guess a color not matching the first man's hat. This guarantees that at least one of the guesses will be wrong. In fact, in general we can guarantee at least $\lfloor {\frac n2} \rfloor$ incorrect guesses by pairing up neighbours and applying this strategy, giving us a lower bound of 119 for the original question.

What about the other end? Well, we can isolate 119 men such that no two of them are neighbours. As a result, they collectively do not receive any information about any of their hats, and as such cannot guarantee a single incorrect guess. This gives us an upper bound of 120.
So, the question has boiled down to whether the answer is 119 or 120, that is, whether our strategy can be refined or not. As such, we scrutinise the type of strategy that we could potentially be looking for.

Application of The Thing

Try to imagine what a strategy guaranteeing 120 wrong guesses would look like. Well, if we were somehow able to make a strategy where every pair of neighbours are able to guarantee that at least one of them can guess incorrectly, then that would guarantee 120 wrong guesses. But is this necessarily what the strategy has to look like?

Consider a strategy that does not guarantee this. That is, there exists a game state and 2 neighbouring men such that under that game state, the 2 men can potentially both guess correctly. Call this state $S$. Label the men 1 to 239 going around the circle such that these neighbours are numbers 1 and 239. Consider the guesses made by men 3, 5, 7, ..., 237 from state $S$. We now construct a state $S'$ such that the hats on men 3, 5, 7, ..., 237 match those guesses while the other guesses are unchanged. Now note that the odd numbered men cannot distinguish between states $S$ and $S'$, so they their strategy must allow all 120 of them to guess correctly in state $S'$, and hence can only guarantee at most 119 incorrect guesses. Hence, the strategy we're looking for must be one that ensures any 2 neighbours cannot simultaneously guess correctly.

I think this example highlights the strengths of this kind of thinking more strongly — since strategy is a potentially a lot more varied than, say, '+1's and '-1's on a board, it's a lot more unclear whether any given idea for a strategy is the correct one to be looking for.
As for whether the actual answer is 119 or 120, I'll leave that to you to figure out.

Conclusion

In conclusion, this line of thinking is seldom something that comes up, and even if it does it may not even find its way into the proof. However, it's for those reasons that I feel it's worth highlighting. At the very least, I hope the ideas presented in the questions were cool.