Can you solve the computer virus riddle? - James Tanton
1,245,112 Views
1,363 Questions Answered
TEDEd Animation
Let’s Begin…
Your antivirus squad is up against a code that’s hijacked your mainframe. What you’ve learned from other infected systems, right before they went dark, is that it likes to toy with antivirus agents in a very peculiar way— and you’re the agent that’s been selected to go up against the malware. Can you figure out which disk that runs your mainframe has been corrupted? James Tanton shows how.
Additional Resources for you to Explore
A 16-disc version of this puzzle appears in Andy Liu’s 2009 article “Two Applications of a Hamming Code” (The College Mathematics Journal, Vol. 40, No. 1) and a 64-disc version of the puzzle has grown in popularity since then. (See for example, 3Blue1Brown’s video here.)
The solutions to these puzzles make use of the binary representation of numbers. For a fun, straightforward, and visual way to understand the binary number system have a look at the opening explorations of the Exploding Dots story from the Global Math Project . (Millions of students and teachers have!)
Solving the puzzle for a count of discs a large power of two relies on counting the 1s that appear in the binary representations of numbers and keeping track on whether these counts are even or odd. Mathematicians use the term parity to describe the idea that an object in a certain scenario might be in one of two states: up or down, black or white, or, in the case of the counting numbers, even or odd, for instance.
Let’s go through the full details of the 8-chip puzzle to see how parity is used in the solution to the general puzzle. And we’ll end this essay with some additional fun playing with parity!
The 8-disc puzzle
A malicious code has corrupted one of 8 discs that run your mainframe. The discs are represented by lights showing which are on and which are off. You will be told which disc is corrupted and then instructed to switch the state of one disc. Your challenge is to communicate to your team the number of the corrupted disc with just this single action. How?
Solution:Number the discs zero to seven via three-digit binary numbers: 000, 001, 010, …, 110, 111.
List the numbers of the discs currently switched on and use these codes to create a new three-digit binary code as follows.
1. The first digit of each disc number is either 0 or 1. Count how many 1s there are among those first digits. If the count of 1s is odd, write 1 as the first digit of our new binary number. Write 0 otherwise.
2. The second digit of each disc number is either 0 or 1. Count how many 1s there are among those second digits. If the count of 1s is odd, write 1 as the second digit of our new binary number. Write 0 otherwise.
3. The third digit of each disc number is either 0 or 1. Count how many 1s there are among those third digits. If the count of 1s is odd, write 1 as the third digit of our new binary number. Write 0 otherwise.
For example, suppose discs two (010), six (110), and seven (111) are on and all other discs are off.
Among the first digits of these codes there are two 1s, an even count.Among the second digits of these codes there are three 1s, an odd count.
Among the third digits of these codes there is just one 1, an odd count.
This gives us the binary number 011 (“even-odd-odd”).
(If no discs were switched on, we have the number 000.)
We must now change this three-digit number to the one we need to communicate, the number of the corrupted disc. We can either add another number to the list (turn a disc on) or remove a number from our list (turn a disc off).
Suppose, for example, the corrupted disc is number five, which has code 101. We created the number 011, which has incorrect first and second digits, but correct third digit.
Consider the number 110, which has a 1 in each digit position we would like to change—the first and second positions—and 0 in the digit position we wish to keep the same. The number 110 corresponds to disc six.
If we add this number to our list (by turning on disc six) or remove this number from the list (by turning off disc six), the count of 1s in each digit position we need to change does change by one, and the count of 1s in each digit position we don’t need to change doesn’t change. Either way, by switching disc six, the list of discs switched on now communicates the number of the corrupted disc!
In our example, we are turning disc six off (as we first saw it on).
Now just discs two (010) and seven (111) are on.
Among the first digits of these codes there is one 1, an odd count.Among the second digits of these codes there are two 1s, an even count.
Among the third digits of these codes there is just one 1, an odd count.
This gives us the binary number 101 (“odd-even-odd”), which is indeed disc five!
Practice: Describe the procedure for solving the 64-disc puzzle.
ParityA counting number is even of is divisible by two without remainder. Consequently, if one has that many pebbles, one can group those pebbles into pairs. A couniting number is odd if a remainder of one appears upon division by two, and so attempting to group that many pebbles into pairs always leaves one “odd pebble out.”
One can now see in one’s mind’s eye that· the sum of two even numbers must be even (adding a set of pebbles that can be paired to second set that can be paired, gives a larger set of pebbles that can still be paired), · the sum of an even number and an odd number, or vice versa, must be odd (adding a set of pebbles that can be paired to second set that can’t, gives a larger set of pebbles that still can’t be completely paired), and· the sum of two odd numbers must be even (the two individual “odd pebbles out” make a pair!).
Similar results hold for the differences of counting numbers.
Consequently, for example, the sum of any number of even numbers is even, the sum of an even number of odd numbers is even, and the sum of any set of numbers containing an odd number of odd numbers is odd!
As any fifty consecutive integers contain 25 even numbers and 25 odd numbers, the sum of fifty consecutive numbers is sure to be odd.
Practice: Is 25,489,465 the sum of five-hundred consecutive integers?
Practice: Agatha and Beau take turns inserting plus and minus signs between the numbers shown. If the resulting sum is even, Agatha wins. If it is odd, Beau wins.
90 3 17 8 1 7 13
Who wins?
Practice: Using pennies (1 cent coins), nickels (5 cent coins) and quarters (25 cent coins), how many ways are there to make change for a dollar (100 cents) using precisely fifteen coins?
Practice: In a certain county, each highway connects precisely two towns. Each town has an odd number of highways emanating from it. Records show that there are 13 towns in the county. Can this count be correct?
Practice: Can you solve the Prisoner Hat Riddle from TedEd?
The solutions to these puzzles make use of the binary representation of numbers. For a fun, straightforward, and visual way to understand the binary number system have a look at the opening explorations of the Exploding Dots story from the Global Math Project . (Millions of students and teachers have!)
Solving the puzzle for a count of discs a large power of two relies on counting the 1s that appear in the binary representations of numbers and keeping track on whether these counts are even or odd. Mathematicians use the term parity to describe the idea that an object in a certain scenario might be in one of two states: up or down, black or white, or, in the case of the counting numbers, even or odd, for instance.
Let’s go through the full details of the 8-chip puzzle to see how parity is used in the solution to the general puzzle. And we’ll end this essay with some additional fun playing with parity!
The 8-disc puzzle
A malicious code has corrupted one of 8 discs that run your mainframe. The discs are represented by lights showing which are on and which are off. You will be told which disc is corrupted and then instructed to switch the state of one disc. Your challenge is to communicate to your team the number of the corrupted disc with just this single action. How?
Solution:Number the discs zero to seven via three-digit binary numbers: 000, 001, 010, …, 110, 111.
List the numbers of the discs currently switched on and use these codes to create a new three-digit binary code as follows.
1. The first digit of each disc number is either 0 or 1. Count how many 1s there are among those first digits. If the count of 1s is odd, write 1 as the first digit of our new binary number. Write 0 otherwise.
2. The second digit of each disc number is either 0 or 1. Count how many 1s there are among those second digits. If the count of 1s is odd, write 1 as the second digit of our new binary number. Write 0 otherwise.
3. The third digit of each disc number is either 0 or 1. Count how many 1s there are among those third digits. If the count of 1s is odd, write 1 as the third digit of our new binary number. Write 0 otherwise.
For example, suppose discs two (010), six (110), and seven (111) are on and all other discs are off.
Among the first digits of these codes there are two 1s, an even count.Among the second digits of these codes there are three 1s, an odd count.
Among the third digits of these codes there is just one 1, an odd count.
This gives us the binary number 011 (“even-odd-odd”).
(If no discs were switched on, we have the number 000.)
We must now change this three-digit number to the one we need to communicate, the number of the corrupted disc. We can either add another number to the list (turn a disc on) or remove a number from our list (turn a disc off).
Suppose, for example, the corrupted disc is number five, which has code 101. We created the number 011, which has incorrect first and second digits, but correct third digit.
Consider the number 110, which has a 1 in each digit position we would like to change—the first and second positions—and 0 in the digit position we wish to keep the same. The number 110 corresponds to disc six.
If we add this number to our list (by turning on disc six) or remove this number from the list (by turning off disc six), the count of 1s in each digit position we need to change does change by one, and the count of 1s in each digit position we don’t need to change doesn’t change. Either way, by switching disc six, the list of discs switched on now communicates the number of the corrupted disc!
In our example, we are turning disc six off (as we first saw it on).
Now just discs two (010) and seven (111) are on.
Among the first digits of these codes there is one 1, an odd count.Among the second digits of these codes there are two 1s, an even count.
Among the third digits of these codes there is just one 1, an odd count.
This gives us the binary number 101 (“odd-even-odd”), which is indeed disc five!
Practice: Describe the procedure for solving the 64-disc puzzle.
ParityA counting number is even of is divisible by two without remainder. Consequently, if one has that many pebbles, one can group those pebbles into pairs. A couniting number is odd if a remainder of one appears upon division by two, and so attempting to group that many pebbles into pairs always leaves one “odd pebble out.”
One can now see in one’s mind’s eye that· the sum of two even numbers must be even (adding a set of pebbles that can be paired to second set that can be paired, gives a larger set of pebbles that can still be paired), · the sum of an even number and an odd number, or vice versa, must be odd (adding a set of pebbles that can be paired to second set that can’t, gives a larger set of pebbles that still can’t be completely paired), and· the sum of two odd numbers must be even (the two individual “odd pebbles out” make a pair!).
Similar results hold for the differences of counting numbers.
Consequently, for example, the sum of any number of even numbers is even, the sum of an even number of odd numbers is even, and the sum of any set of numbers containing an odd number of odd numbers is odd!
As any fifty consecutive integers contain 25 even numbers and 25 odd numbers, the sum of fifty consecutive numbers is sure to be odd.
Practice: Is 25,489,465 the sum of five-hundred consecutive integers?
Practice: Agatha and Beau take turns inserting plus and minus signs between the numbers shown. If the resulting sum is even, Agatha wins. If it is odd, Beau wins.
90 3 17 8 1 7 13
Who wins?
Practice: Using pennies (1 cent coins), nickels (5 cent coins) and quarters (25 cent coins), how many ways are there to make change for a dollar (100 cents) using precisely fifteen coins?
Practice: In a certain county, each highway connects precisely two towns. Each town has an odd number of highways emanating from it. Records show that there are 13 towns in the county. Can this count be correct?
Practice: Can you solve the Prisoner Hat Riddle from TedEd?
About TED-Ed Animations
TED-Ed Animations feature the words and ideas of educators brought to life by professional animators. Are you an educator or animator interested in creating a TED-Ed Animation? Nominate yourself here »
Meet The Creators
- Educator James Tanton
- Director Igor Coric, Artrake Studio
- Music Cem Misirlioglu
- Sound Designer Cem Misirlioglu
- Director of Production Gerta Xhelo
- Editorial Director Alex Rosenthal
- Producer Bethany Cutmore-Scott
- Narrator Addison Anderson
