Math Talk: Liar Puzzles and Algebraic Equations
"Arin, how did you solve this puzzle earlier?"
I opened the puzzle book and pointed to the problem we had just solved.
Ancle: "Mare is a liar!"
Mare: "Hmph! Coron is the liar!"
Coron: "Heeing...! That's so mean! Both of them are liars!"
Arin read the problem and spoke.
"First, I split it into cases based on whether Ancle was telling the truth or lying."
"Right. Exactly. Then let's draw a table so we can see both cases at a glance."
I brought over the whiteboard, laid it on the living room floor, and drew a table.
Arin stared at the table and asked.
"Unni, what's the question mark for?"
"The question mark means a contradiction occurred."
I pointed to the corresponding cell as I explained.
"If Mare is lying, then Coron must be telling the truth. But if Coron is telling the truth, that means the other two must both be lying. However, if that happens, Ancle would have to be both telling the truth and lying at the same time. Since that makes no sense, the case with the question mark isn't the right answer."
Arin's eyes widened.
"Oh, then the case where Ancle is lying, Mare is telling the truth, and Coron is lying is the correct answer! That's so cool! Drawing it in a table makes it so easy to see at a glance!"
"Exactly. And there's an important point here."
I raised a finger.
"Usually, the premise of a liar puzzle is that a character either tells the truth or lies. Because of that, the logic of 'either true or false, and if not false then true' holds."
Logic.
The moment she heard that word, Arin's eyes sparkled.
Arin had watched Mom and me write complex research papers over our shoulders, but she had always stayed quiet because she didn't understand what any of it meant.
The joy of realizing that she, too, was dealing with "logic" was written all over her face.
I smiled brightly and continued.
"Now, let's play around with this a bit more. We established that the characters here are either true or false, right? Having both or having neither is against the rules. That's the law of this puzzle."
Arin nodded and said:
"Right. Just like in quantum mechanics, a superimposed state of being both true and false is against the rules."
To think she remembered the quantum mechanics stuff I mentioned in passing.
Her memory and ability to apply concepts are excellent. She really is my sister.
"In that case, let's go back to the state where we don't know the answer, and record whether each character told the truth or lied as a variable."
"A variable? Um... what was that again? A changing number?"
"Correct."
I wrote on the whiteboard.
Ancle: x
Mare: y
Coron: z
"Here, the value assigned to each character is either true or false. Do you understand so far?"
"Yep."
"But saying 'true' and 'false' over and over can get confusing, so let's convert them into numbers."
I wrote on the whiteboard.
True = 1
False = 0
"True is 1, and false is 0. That means x, y, and z will all have a value of either 1 or 0."
"Hmm... why are they suddenly turning into numbers..."
Arin had a puzzled look on her face.
"Because we can't do addition or subtraction with just 'true' and 'false', right? We want to express this liar puzzle mathematically."
Ancle is true → x = 1
Ancle is false → x = 0
Mare is true → y = 1
Mare is false → y = 0
Coron is true → z = 1
Coron is false → z = 0
"Ah... I see how it is... I get it for now."
Arin nodded.
"Now, let's express each statement as an equation."
Ancle: "Mare is a liar!"
"If we look closely at this statement, if Ancle is telling the truth, Mare must be lying. That means if x is 1, y is 0. Conversely, if Ancle is lying, Mare must be telling the truth. That means if x is 0, y is 1."
I wrote it down slowly.
If x = 1, then y = 0.
If x = 0, then y = 1.
"If we write this cleanly as a single equation..."
x = 1 - y
"It becomes this."
"Huh? It really does. If x is 1, y is 0, and if x is 0, y is 1."
"Exactly. This is Ancle's statement expressed as an equation."
Arin was convinced.
Mare: "Hmph! Coron is the liar!"
"Mare's statement is the same. If Mare is telling the truth, Coron is lying; if Mare is lying, Coron is telling the truth. So we can write it like this."
y = 1 - z
Coron: "Heeing...! That's so mean! Both of them are liars!"
"But Coron's statement is a bit different. Coron said both Ancle and Mare are liars. If Coron is telling the truth, then both x and y must be 0."
I paused for a moment.
"How can we express 'both are 0' mathematically?"
Arin pondered.
"Hmm... I don't know."
"Here's a hint: use multiplication. Because of the nature of 0, if any number in a multiplication is 0, the result is always 0. Since both x and y must be 0, we need to express the state where each of them is 0."
I gave her an additional hint.
"For reference, if x is 0, then (1 - x) is 1. If y is 0, then (1 - y) is 1."
Arin went "Hmm..." as she thought it over.
"...Then (1 - x) times (1 - y)? Because Coron is only telling the truth when both Ancle and Mare are lying!"
"Exactly."
I wrote it down just as she said.
z = (1 - x)(1 - y)
"And these three are the equations representing the statements of Ancle, Mare, and Coron."
x = 1 - y
y = 1 - z
z = (1 - x)(1 - y)
Arin muttered as she looked at the equations.
"Huh... the puzzle suddenly turned into math."
"Hehe. Cool, right? There's one more thing. What did we say the premise of the liar puzzle was earlier?"
"That they can only be true or false? ...Ah! The x, y, and z here can only be 0 or 1!"
"Right. And the equations representing that condition look like this."
x² - x = 0
y² - y = 0
z² - z = 0
These are the equations that say, "We are either 0 or 1."
It's a simple formula that anyone middle school age or older who has learned quadratic equations would know.
But explaining all of that to Arin would take too much time, so I skipped it.
"So, if we summarize everything we've done so far, we can represent it with the following equations."
Ancle: "Mare is a liar!"
Mare: "Hmph! Coron is the liar!"
Coron: "Heeing...! That's so mean! Both of them are liars!"
x = 1 - y
y = 1 - z
z = (1 - x)(1 - y)
x² - x = 0
y² - y = 0
z² - z = 0
"This puzzle and this system of equations are completely identical."
"Oh... that's kind of amazing..."
"Which means, finding the values of x, y, and z that satisfy all these equations at the same time is exactly the same as solving that puzzle."
Arin stared intently at the equations.
I suggested to Arin.
"Do you want to try plugging in the numbers yourself?"
Arin picked up a pencil.
Arin plugged in the numbers and found that x = 0, y = 1, and z = 0.
"But Unni... isn't this basically the same as what we did earlier? It feels exactly the same as when I split it into cases for when Ancle was telling the truth or lying, plugging 1 into x, seeing it didn't work, and then plugging in 0 and getting it right..."
"You noticed, Arin. You're right. Even if we beautifully convert it into equations, if we just plug in 0 and 1 case by case, it's no different from the standard way of solving a liar puzzle. That's why we're going to play around with it a bit more."
I took a sip of water and continued my explanation.
"From here on out, it's something even Dad doesn't know. Just listen. The tool used to calculate these complex, intertwined polynomials is called a Gröbner basis."
"Grebner?"
"Gröbner basis. It's a tool derived from the Hilbert Basis Theorem."
I had gotten the inspiration after hearing about the Hilbert Basis Theorem from that forum guy this morning.
Hilbert's Basis Theorem
→ A mathematical theorem stating that every ideal in a polynomial ring is finitely generated.
Gröbner Basis
→ An algorithmic tool derived from Hilbert's Basis Theorem used to actually compute, eliminate, and solve systems of polynomial equations.
Arin just listened blankly.
"The point is, no matter how complex the polynomials are, there is a way to solve them in one single shot! We're going to use a computer to calculate it."
Patter, patter.
I brought over my laptop and opened it on the living room floor.
"We obtained six equations that perfectly match the puzzle. Expressing this algebraically, we can say we have obtained the following ideal over the field of real numbers."
I = ⟨ x+y−1, y+z−1, z−(1−x)(1−y), x²−x, y²−y, z²−z⟩
What an ideal is is too complicated, so let's skip it.
Just know that such a thing exists in algebra.
I accessed WolframAlpha on my laptop.
"Unni, what is this place?"
"WolframAlpha. A true friend to science and engineering majors, solving all their complex equations."
I said as I typed in the command.
Clack, clack.
{x+y-1,
y+z-1,
z-(1-x)(1-y),
x^2-x,
y^2-y,
z^2-z},
{x,y,z}
]
"Unni, I don't know what you're doing."
Arin tilted her head.
"First of all, the part at the beginning is a command telling the computer to calculate the polynomials like this. You type 'GroebnerBasis', and then you put the polynomials inside brackets and braces, and it calculates them for you."
"Hmm... okay, but... we put in the equations we got earlier, so why are there no equal signs (=)?"
"When you enter this command, the rule is to move everything to the left side so the right side is 0, and then remove the equal sign. Our first equation was x = 1 - y, right? But we moved everything on the right to the left to change it to x + y - 1 = 0. And then we just took out the equal sign."
"Hmm... I see... I get it for now."
I wasn't sure if Arin actually understood, but she nodded along and kept following.
"Neeheehee! Anyway, once we enter this command, the computer will crunch the numbers in a flash!"
Press.
I pressed Enter.
And then...
The following result appeared.
"Unni, something came out. What does this mean?"
"It means it simplified the x, y, and z values that satisfy all six of those equations. Remember how we removed the '= 0' from the right side of the equations before putting them in? Now, put them back."
"Okay, then..."
Arin added '= 0' to the end and organized them just as I said.
x = 0
1 - y = 0
z = 0
"If it's like this... since x is 0, Ancle is lying. Since y is 1, Mare is telling the truth. Since z is 0, Coron is lying. It's exactly the same as the answer to the puzzle from earlier! Wow, that's so cool!"
"Hehe. Right? This is the kind of fun toy mathematicians play with!"
Arin stared at the laptop screen for a long time before speaking.
"But Unni."
"Yeah?"
"This is really cool, but..."
Arin tilted her head.
"In the end, the answer is exactly the same. Just like when I split it into cases."
I chuckled.
"You're right. You caught on."
"Then why do we do all this complicated stuff? It feels like you wasted so much time converting it into equations and typing it into the computer!"
I thought about it for a moment before replying.
"Arin, this puzzle only has three characters. But what if there were ten? Or what if there were a thousand?"
"Huh...? Um..."
Arin fell into thought.
"No matter how many characters there are, if you organize the equations and plug them in, the computer will solve it all in one go."
Arin's eyes went wide.
"Really? Then you can solve a puzzle with a thousand people in one shot, just like that?"
"Theoretically, yes."
"Ooh!"
Of course, no one would actually solve a liar puzzle with a thousand characters.
Instead, inside computers that deal with 0s and 1s, logical formulas far more complex than a liar puzzle with ten thousand characters are processed every single day.
The polynomial calculation technique I just showed her is actually used in the field.
The reason I went out of my way to convert a simple puzzle into complex equations was because I wanted to teach Arin that kind of mathematical intuition.
Arin looked back at the laptop screen, her eyes sparkling.
The magic of the liar puzzle she had just solved transforming into magnificent mathematics.
"Unni."
"Yeah?"
"Is math always this fun?"
I looked at Arin for a moment.
Then, I smiled brightly and said:
"Yep! It's always been fun!"
Pat, pat.
I stroked Arin's hair.