Toggling lights 3 at a time

Alice and Bob are playing a game. $n$ lights are put on a line with individual switches, initially all off. Then the two phases happen as follow:

1. Alice turns on some of these lights

2. Bob may do these actions: choose a contiguous block of 3 lights and toggle these 3 lights. He may repeat these actions as many times as he wants for different blocks.

And the scoring of the game is as follows:

In phase 1, Alice gets a -1 point for each light that she turns on. In phase 2, Alice gets a +1 point every time Bob performs an operation. Then at the end of the game, Alice gets $i$ points if light $i$ is on. Obviously Alice wants her score to be as high as possible, and Bob wants her score to be as low as possible. Determine the maximum points that Alice can get if both players are playing optimally.

Solution

Let $T_k$ denote the action by Bob of toggling a contiguous block of $k, k+1, k+2$, where $k \in [1, 98]$. If light $k+3$ is on and light $k$ is off, by performing $T_k + T_{k+1}$ he can turn off $k+3$ and turn on $k$. The net effect to the score is -1 so this move is beneficial to Bob. Therefore, he would keep doing it as long as there are lights on at $k > 3$. Furthermore, if there are 2 lights on $k > l$ such that $k \equiv l \mod 3$ then by repeating the operation above Bob can turn off both lights. The net effect to the score is $-k-l+2\frac{k-l}{3} < 0$. This means that it is not optimal for Alice to turn on two lights that have the same residue mod 3. So at most Alice should turn on 3 lights. But even then, if we ever arrive at the condition where lights $(1,2,3)$ are on, then Bob can perform $T_1$ to turn off all the lights. So Alice should turn on at most 2 lights.

The final condition that is most beneficial to Alice is either $(3)$ or $(1,2)$, both having the same value, and both are accessible from each other in phase 2. But obviously it's more beneficial for Alice to turn on only 1 light, and it should be the largest light divisible by 3, so that Bob has to spend a lot of moves moving it to the smaller number. So Alice should turn on $3\lfloor n/3 \rfloor$, and Bob will have to move it all the way to 3.

The total score is then $-1 + 2\lfloor n/3 \rfloor + 3 = 2\lfloor n/3 \rfloor +1$

Note: the number 3 can be replaced by a larger number $p$ but the principle is the same. Any light on above $p$ can be shifted down for a net gain for Bob. However, the final condition is tricky. Take $p=5$ for example. We don't want $(1,2,3,4,5)$ because then Bob can simply turn them all off in one fell swoop. We also don't want $(3,4,5)$ because Bob can still replace it by $(1,2)$ for a net gain. In fact, the optimal condition for Alice is $(3,5)$ because while Bob can replace it by $(1,2,4)$, it costs him 1 point to do so, so it's not a beneficial move for Bob. Likewise, for $p=6$, the best condition for Alice is $(5,6)$ because it's "just under" $(1+2+3+4+5+6)/2$. The number of lights that would be left on so that the sum is just under $n(n+1)/2$ is $\lfloor (n-1)/2 \rfloor$ which can be proved by induction. However, the exact configuration is harder to determine in closed form expression. This matters because in the course of shifting the lights down during phase 2, Bob may inadvertently have to perform the same $T_k$ twice in which case he would just not perform that action, so the calculation of final point count becomes more complicated.

Questions in an exam

A test is taken by 2019 students. The test consists of $n$ questions (where $n > 0$ is even), where each question is a true/false problem worth 1 point. It is known that:

1. Each student answered exactly half of the questions correctly.

2. Given two students, their answers agreed on exactly half of the questions.

Find the smallest $n$ such that this situation is possible.

Solution

If $n = 2^k m$ where $m$ is odd, then there are at most $2^k - 1$ students. Therefore, with 2019 students, we need $2048$ questions for this situation to be possible. Proof:

Suppose $m=1$, we will give a configuration of $2^k-1$ students that satisfy both conditions. First of all, given a number $b$, let $f(b)$ denote the number of 1s in its binary representation, modulo 2. That is $f(b)=0$ if $b$ contains an even number of 1s in its binary representation, and $f(b) = 1$ otherwise.

Label the students $1$ to $2^k-1$ and consider their binary representation (from $0...01$ to $1...1$, all having exactly $k$ digits). Also label the problems $0$ to $2^k-1$ and consider their binary representation (from $0...0$ to $1...1$, all having exactly $k$ digits). We set student $s$ answered problem $p$ correctly if $f(p \wedge s) = f(s)$, where $\wedge$ denotes bitwise AND operation between $p$'s binary representation and $s$' binary representation. In other words, if the number of digits where $p$ and $s$ are both 1 in their binary representation is the same parity as the number of 1s in $s$' representation, then student $s$ answered problem $p$ correctly.

For example, student $5=0...101$ answered question $2=0...010$ correctly because $f(5 \wedge 2) = f(0...000) = 0 = f(5)$. But student $7 = 0...111$ answered question $3 = 0...011$ incorrectly because $f(7 \wedge 3) = f(111 \wedge 011) = f(011) = 0 \neq 1 = f(7)$.

From there, it's easy to see that condition 1 is satisfied. A student's correct answers depends only on the digits of $s$ that are 1, and there are $2^{f(s)}$ possible combinations of those digits. Out of those, there will be half that has even number of 1s and half that has odd number of 1s, so that student answers half the questions correctly.

To prove condition 2, consider student $s$ and $t$. Consider $r = s \oplus t$ where $\oplus$ denotes the bitwise XOR operation. In other words, $r$ is a number whose binary representation is 1 at the digits where $s$ and $t$ are different, and 0 at the digits where $s$ and $t$ are the same. The problems where $s$ and $t$'s answers agree are exactly the problems where student $r$ answered correctly. To prove that assertion, note that $f$ is distributive with respect to $\oplus$. That is $f(a \oplus b) = f(a) \oplus f(b)$. This is because if $a$ has $d_a$ number of 1s and $b$ has $d_b$ number of 1s then $a \oplus b$ has $d_a + d_b \mod 2$ number of 1s, because the digits that were both 1s and turned into zero always come in pairs.

So suppose both $s$ and $t$ get problem $p$ right, then $p \wedge r = p \wedge (s \oplus t) = (p \wedge s) \oplus (p \wedge t)$ so $f(p \wedge r) = f(p \wedge s) \oplus f(p \wedge t) = f(s) \oplus f(t) = f(s \oplus t) = f(r)$ and similarly if they both get the problem wrong. We can show that if $s$ gets problem $p$ right and $t$ gets it wrong, then $r$ gets problem $p$ wrong as well. That way, we showed that student $s$ and $t$'s answers agree exactly on the problems that student $r$ gets right, and by condition 1, this is exactly half of all the problems. So condition 2 is proven.

Now for $m > 1$, let $l = 2^k$ so $n = lm$, we simply assign student $s$ answering problem $p$ correctly if and only if student $s$ answers problem $(p \mod l)$ correctly. In essence, we are duplicating problems $0,\dots, l-1$'s answers (which were constructed above) $m$ times. Condition 1 and 2 are still satisfied.

The second part of the proof is to show that this arrangement is optimal. That is, with $n = 2^km$ there is at most $2^k-1$ students.

For $n$ to be even then $k \geq 1$. For $k = 1$ we show that there is at most 1 student. That is, condition 1 can be fulfilled easily, but condition 2 cannot be fulfilled. Indeed, WLOG we may assume that student $A$ answered questions $1,\dots,m$ correctly and $m+1,\dots,2m=n$ incorrectly. If there is a second student $B$, then suppose above questions $1,\dots,m$ he answered $t$ questions correctly, then he must answer $m-t$ questions among the second half correctly. However, that means the number of questions that $A$ and $B$ agreed on is $t + (m- (m-t)) = 2t \neq m$, contradiction. So there is at most $2^1 - 1 = 1$ student for $k = 1$.

Now we use induction on $k$. Suppose that $k > 1$ and let $h = n/2 = 2^{k-1}m$. Take student $A$, and WLOG assume that he answered questions $1, \dots, h$ correctly (i.e. the first half). For any other student $B$, suppose he answers $t$ questions correctly on the first half, so $h-t$ questions correctly from the second half. The number of questions that $A$ and $B$ agreed on is $t + (h-(h-t)) = 2t = h$, so student $B$ answered $h/2$ questions correctly on the first half. This means all students other than $A$ must answer $h/2$ questions correctly on the first half.

Also note that if we replace $B$ with $B'$ whose answers are completely opposite of $B$, then condition 1 and 2 are both still preserved. $B'$ still answered half the questions, and the questions that $B$ agreed with other students are just "flipped." However, $B$ and $B'$ cannot both coexist because obviously condition 2 would be violated.

So now suppose that there are two students $B,C$ distinct from $A$. It's possible that $B$ and $C$ agree completely on the first half (and disagree completely on the second half). We see this a lot in the construction above. In that case, we call $B$ and $C$ "friends", and we put them under one "group." Also, if $B$ and $C'$ would have been friends, we still call $B$ and $C$ friends (as in, if $B$ and $C$ disagree completely on the first half but agree completely on the second half, we still call $B,C$ friends). Note that because $C$ and $C'$ cannot both coexist, we are not claiming that $B$ can be friends with two existing students. Indeed we shall show that $B$ is friends with at most one other person.

If $B$ and $C$ are friends, and $B$ and $D$ are friends. WLOG we may assume that $B,C,D$ agree completely on the first half (otherwise replace $C$ by $C'$ or $D$ by $D'$ or both). Suppose :
1. $X$ is the set of problems that $A$ got right, $B$ got right
2. $Y$ the set of problems $A$ got right, $B$ got wrong
3. $Z$ the set of problems $A$ got wrong, $B$ got right
4. $W$ the set of problems $A$ got wrong, $B$ got wrong

So $X \cup Y$ is the first half, and $Z \cup W$ is the second half. Because $C$ agree with $B$ on the first half, he must disagree completely on the second half. That means $C$ got $X \cup W$ completely right, and $Y \cup Z$ completely wrong. But we my apply the same argument to $D$, therefore $D$ got $X \cup W$ completely right and $Y \cup Z$ completely wrong. This violates condition 2 because now $C,D$ agree everywhere. Contradiction. Therefore, each group of friendship contains at most 2 students. (Some students may not have friends, so they are in a group each by himself).

Next, suppose $B$ and $C$ are not friends. Consider the answers of $C$ in $X,Y,Z,W$ that agree with $B$. Suppose there are $t_X, t_Y, t_Z, t_W$ answers that agree with $B$ respectively. Now by condition 2, the total number of agreement between $B$ and $C$ must be $h$, so: $$t_X + t_Y + t_Z + t_W = h$$ By condition 1, the total number of answers that $C$ got right must be $h$, so: $$t_X + (|Y| - t_Y) + t_Z + (|W| - t_W) = h$$ And note that $|Y| + |W|=h$ because those are the questions that $B$ got wrong. So the second equation can be written as: $$t_X + t_Z = t_Y + t_W$$ That means $t_X + t_Z = t_Y + t_W = h/2$. But also, $C$ must agree with $A$ for $h$ questions, so: $$t_X + |Y| - t_Y + |Z| - t_Z + t_W = h/2$$ But $|Y| + |Z| = h/2$ because those are the questions that $B$ disagreed with $A$, so $t_X + t_W = t_Y + t_Z = h/2$ Solving the two equations, we have $t_X = t_Y$. Next, because $C$ must answer $h/2$ questions correctly on the first half, then $t_X + |Y|-t_Y = h/2$, so $|Y| = h/2$, which means $|X| = |Y| = |Z| = |W| = h/2$. we get $t_X = t_W = t_Z = t_Y = h/4$. Because $k>1$ and $h = 2^{k-1}m$ then $h/4$ is still an integer. Therefore $t_X + t_Y = h/2$. So the conclusion here is that if $B$ and $C$ are not friends, then $C$ agreed with $B$ on exactly $h/2$ on the first half, and $h/4$ on the second half.

Suppose there are $2^k$ students, and because $A$ is one of them, then there are $2^k-1$ "non-A" students. Because each group contains at most 2 students, then there are at least $\lceil (2^k-1)/2 \rceil = 2^{k-1}$ groups. Take any student from each group to be the "representative" of that group. Now, consider their answers only on the first half of the exam. These answers satisfy the condition for the exams with $n/2 = h$ questions. Indeed, condition 1 is satisfied because all students other than $A$ must answer $h/2$ questions correctly. Condition 2 is also satisfied because every two students who are not friends must agree exactly $h/2$ on the first half. Therefore, now we have at least $2^{k-1}$ students (excluding student $A$) with $h = 2^{k-1}m$ problems that satisfy conditions 1 and 2, violating our induction hypothesis. Contradiction. So there must be at most $2^k-1$ students in an exam with $2^km$ problems.

Finally, because $2^{10} < 2019 < 2^{11}$, then in order for this situation to happen with 2019 students, $k \geq 11$. That means the least number of problems is $2^{11}.1 = 2048$.

Lights forming a hexagon

Six lights are placed such that they form a regular hexagon. At each turn, we're allowed to do one of the following:

1. Toggle three consecutive lights

2. Toggle three lights that form an equilateral triangle

3. Toggle two diametrically opposite lights

Prove or disprove, for any given starting configuration, we can turn off all the lights through a series of turns as described above.

Solution

Answer: we cannot.

Label the lights as 1,2,3,4,5,6, and denote each move as follows:

$A_i$: toggling lights $i, i+1, i+2$. There are 6 such moves: $A_1, \dots, A_6$.

$B_i$: toggling an equilateral with $i$ as one of its vertices. Obviously we only need to consider $B_1, B_2$.

$C_i$: toggling $i$ and its opposite. Again, we only need to consider $C_1, C_2, C_3$.

$D$: toggling all the lights. Although this is not one of the moves allowed explicitly in the problem statement, it can be achieved by the combination of $A_1+A_4$ (as well as many others), so it is effectively a legal move.

From a set of moves, we're allowed to remove it if it can be achieved by a combination of all the other moves remaining in the set. So from the set of all the moves described above, we can remove $A_4, A_5, A_6$ because they can be achieved by $D + A_1, D+A_2, D+A_3$ respectively.

Likewise, we can remove $B_2 = B_1 + D$ and $C_3 = C_1+C_2+D$. So now we're down to $\{A_1,A_2,A_3,B_1,C_1,C_2,D\}$. Now notice that: $A_2 = C_1 + A_1$, $A_3 = C_1 + C_2 + A_1$ so we remove them as well, leaving us with $\{A_1,B_1,C_1,C_2,D\}$.

Now although the number of possible move sequences is infinite, the number of reachable configurations from an all-off configuration is limited. There are five moves left in our set. We have not yet proved that they're all truly independent (i.e. we can no longer remove any more), but we don't need to. For each move in that set, it only matters whether that move is performed an even or odd number of time. In algebraic lingo, these moves are commutative and self-inverse. So that means there are at most $2^5$ configurations reachable from an all-off configuration, but we have $2^6$ total configurations. Each sequence of moves are its own inverse, so that means there are 32 configurations such that we cant turn off all the lights.

If we're asked to identify such configuration, we note the following: the configuration where only 1 light is on is not reachable from an all-off configuration. If this were possible, then we could apply that same sequence of moves (rotated appropriately) to achieve any desired configuration.

Prisoners With Hats Again

This is a generalization of the latest logic problem in MIT's Technology Review, November/December 2014 There are $n$ prisoners, $a_1, a_2, \dots, a_n$ where each prisoner is a perfect logician. Also, $a_n$ is blind but the other ones can see.

Initially they're all blindfolded. There are $n$ white hats and $n-1$ black hats, and out of those $2n-1$ hats, $n$ hats are randomly selected, and the rest hidden. Each prisoner is then given one of those $n$ hats to wear. At the same time, all the blindfolds are taken off.

Then the prisoners said the following things, in this order:
$a_1$ said: "I don't know my hat color."
$a_2$ said: "I don't know my hat color."
$a_3$ said: "I don't know my hat color."
...
$a_{n-1}$ said: "I don't know my hat color."
$a_n$ said: "I know my hat color."

What is $a_n$'s hat color?

Solution

If $a_1$ saw all black hats, then he would know that his hat is white, because there are at most $n-1$ black hats in the room. Because he doesn't know his hat color, then at least one of $a_2,\dots,a_n$ is white.

Likewise, if $a_2$ saw all black hats among $a_3, \dots, a_n$, given the information that at least one of $a_2, \dots, a_n$ is white, he would know that his hat is white. Because $a_2$ doesn't know his hat color, then at least one of $a_3, \dots, a_n$ is white.

We can continue this line of reasoning via induction. The hypothesis is that at least one of $a_k, \dots, a_n$ is white. If $a_{n-1}$ saw that $a_n$ has black, he would know that he has white. Because $a_{n-1}$ doesn't know his hat color, that means $a_n$ has white.

liars and honest villagers

In a village, there are $n$ people who each has an ID number from 1 to $n$. Each person is either completely honest or a total liar. One day, a detective came to visit and interviewed them. This is what they told him:

If a person had an ID number $x$ where $x$ is even, he said:
"The person whose ID number is $x/2$ is honest"

If a person had an ID number $x$ where $x$ is odd and greater than one, he said:
"The person whose ID number is $(x-1)/2$ is a liar"

Person with ID number of 1 did not say anything.

If $L$ is the number of liars and $H$ is the number of honest villagers, find all possible values of $L-H$

Matching Binary String

We are given two binary strings $A$ and $B$ each of length $2n$. Both strings contain equal number of ones and zeros to each other. We write $A$ on top of $B$, so that each element of $A$ is paired with each element of $B$ at the corresponding position.

We call the two strings a "match" if there are at least $n$ common elements where the element of $A$ at a certain position matches that of $B$ at that position.

Prove that, we can cyclically shift $B$ a number of times (and wrap around at the end/beginning) so that $A$ and $B$ form a match.

Room and Lights Game

This problem is identical to this one but reworded for better clarity.

Alice is playing a game against Bob and Charlie. In a room, there are 27 lights with individual switches, some of them could be turned on or off. Bob enters the room while Charlie waits outside. Alice will tell Bob a number from 1 to 27. Bob then is allowed to flip at most 3 switches if he wishes. Then Bob exits and Charlie enters the room. He has to, upon examining the lights, guess the number that Alice told Bob. Neither Bob nor Charlie knows the configuration of the lights before Bob entered the room.

How can Bob and Charlie agree on a strategy to win this game?

Harder version: 15 lights, but Alice tells Bob a number from 1 to 16, and Bob can only flip at most one switch.

Prisoners and hats

2047 prisoners are kept in a dungeon. One day, the King decided to do an experiment. They will each be given either a blue hat or a red hat and then collected in a room. Each prisoner can see the color of everyone else's hats but not his own. No form of communication is allowed. After a few minutes, the warden will come and ask each of them individually what he thinks the color of his hat is. They can answer "red" or "blue." Each prisoner must answer by whispering to the warden's ear, so that the other prisoners can't hear his answer. Those who can answer correctly will be freed, but those who answer incorrectly will be executed on the spot. The prisoners found out about this experiment the night before, so they had some time to devise a scheme to ensure they can save as many people as possible.

Question 1: What is the scheme that allows everyone to live in this case?

Suppose now the King decided to alter the experiment a little bit. The warden will come to the room immediately after everyone get their hats. Each prisoner is allowed to answer "red", "blue", or "I don't know." If everyone answers "I don't know", they will all be executed. If someone answers "red" or "blue" and he is wrong, they will all be executed. Otherwise, everyone is freed at the same time. In other words, in order for them to live, at least one person must answer "red" or "blue" and he must be right. As before, the prisoners can't hear everyone's answers, and the release or execution is delayed until everyone had given their answers.

Question 2: What is the scheme that allows everyone to live with the highest probability? What is that probability?