Elimination Grids

An elimination grid is a tool to solve complex logic problems. It is useful when there is lots of information and works by converting data into a visual grid.

In basic logic puzzles, the sort found on many math and reasoning tests, a grid like the one to the right can be useful to eliminate possibilities, based on provided information.

Some well-known examples of these sorts of puzzles are Sudoku, Einstein's logic puzzle, and Cheryl's birthday. For instance, in Sudoku puzzles, an elimination grid can be used to determine what the right entry is: eliminating numbers 1-9 that have already been used across, down, and in the same box.

Setting Up the Grid

As the name suggests, when solving these types of problems, it is advisable (though not a necessity) to set up a grid. Typically, these puzzles have a description or a list of facts that describes a group of people or other objects. The puzzle then asks for the solver to uniquely match the people or objects to properties described in the list of facts.

Alice, Bethany, Carly, and Denise each have their own favorite flavor of ice cream (vanilla, chocolate, strawberry, or caramel) and their own favorite topping (sprinkles, nuts, M&Ms, or gummi bears). Right away, a grid can be set up wherein each characteristic (name, flavor, and topping) owns a set of rows that overlap each other characteristic as columns.

We are then given information about which person likes which flavor and topping. For instance, we might be told that Bethany likes chocolate ice cream, but doesn't like nuts. With this in mind, we can check Bethany off as the chocolate lover, while crossing off every other flavor for Bethany and every other name for chocolate. Furthermore, we can mark Bethany and the chocolate-lover off as candidates for liking nuts.

Next, we might be told that Carly doesn't like strawberry or vanilla ice cream, allowing us to eliminate her as candidates for those flavors, revealing that she must be the caramel lover.

With the remaining information, see if you can finish off the puzzle:

Denise likes gummi bears as her favorite topping.

The person who likes vanilla ice cream likes sprinkles as her topping.

Alice doesn't like nuts or M&Ms.

In making a grid we use the columns and rows effectively so that every possibility in the puzzle is identified. Start with one of the easiest clues that gives you a simple fact matching two pieces of information together. For instance, you have the information "Sam has a red ball." Then find the row or column of your grid labeled "Sam," and follow it until you get to a square underneath the column or row labeled "red." Highlight that point to show that Sam and the red ball are connected. Let us try another example now.

Question: There are three people--X, Y, and Z--and they are a doctor, an engineer, and a teacher, not in the same order. They also have A, B, and C as their children, also not in the same order. Consider the following statements:

X is the father A, but is not a doctor.

Y can either be a doctor or a teacher.

Z is an engineer, and is the father of B.

C is the son of a doctor.

What is the profession of A's father?

Answer: This is how the grid will look:

Then step by step cross out squares that are ruled out from the hints provided. Harder problems have numerous properties, in which you have to fill out a much more complicated matrix.

Direct Elimination

Uniqueness Strategies

In this section we will be solving puzzles by applying the same concepts from K-level thinking. If you are not familiar with that concept, please see the main article first, K-level thinking.

When solving K-level puzzles, it is also possible to create gridlike tables and work our way through to obtain the answer. Because it is difficult to explain this without any question in mind, let us jump into a sample question:

Ed thinks of two positive integers, he then secrely told Fred one number and Greg another number separately. Ed then told both Fred and Greg that the sum of their numbers is 2 or 4. If Fred told Greg that he (Fred) didn't know Greg's number, can you deduce what Fred's number is?

For starters, we need to know what the possible values are for Fred's and Greg's numbers. Let \(F\) and \(G\) denote the possible values for Fred's number and Greg's number, respectively. Because we are told that the sum of their numbers is 2 or 4, it follows that \(F+G = 2\) or \(F+G=4\) must be fulfilled. So \(F\) can take values 1, 2, and 3, and similarly, \(G\) can take values 1, 2, and 3 as well. Let us construct the outline of the grid first:

	1	2	3
Fred
Greg

Now if Fred's number is 3, then the sum of their numbers must exceed 2, so the only possible number for Greg to have is 1. However, this is impossible because Fred already knows his number and if his number is indeed 3, then he can automatically deduce the fact that Greg's number is 1, which contradicts the fact that Fred says he doesn't know about Greg's number. Hence Fred can't have the value of 3. So, let's mark an X in the table as follows:

	1	2	3
Fred			\(\times\)
Greg

Similarly if Fred's number is 2, then the sum of their numbers must exceed 2, so the only possible number for Greg to have is 2. However, this is impossible because Fred already knows his number and if his number is indeed 2, then he can automatically deduce the fact that Greg's number is 2, which contradicts the fact that Fred says he doesn't know about Greg's number. Hence Fred can't have the value of 2. So, let's add another X to the table:

	1	2	3
Fred		\(\times \)	\(\times\)
Greg

From here, the only possible solution for Fred's number is \(F=1\). Hence the following table:

	1	2	3
Fred	\(\checkmark \)	\(\times \)	\(\times\)
Greg

Now is it possible for Fred to figure out what Greg's number actually is if Greg makes the additional claim that his number is not the same as Fred's? Yes it is! For starters, Greg's number can't be 1 because his number is different from Fred's. Hence the following table:

	1	2	3
Fred	\(\checkmark \)	\(\times \)	\(\times\)
Greg	\(\times\)

Because the sum of Fred's and Greg's numbers is either 2 or 4 only, Greg's number must be either \(2-1 = 1\) or \(4-1= 3\) only. Thus Greg's number can't be 2, which gives us 4 as Greg's number, and we have the following table:

	1	2	3
Fred	\(\checkmark \)	\(\times \)	\(\times\)
Greg	\(\times\)	\(\times \)	\(\checkmark\)

So we have finally deduced what their numbers are!

Now, doing the same kind of reasoning as above, can you solve the following example?

Difficulty increases with the number of rows and columns. It could also be unclear how one should choose to present the data and follow the argument. An excellent example is Josh Silverman's solution to the viral problem Cheryl's Birthday.

Example Problems

Four friends have been identified as suspects in a car theft. One of them really stole the car, and the following are the statements they made to the investigating authorities:

Thomas said, “Simon did it.”
Kim said, “I did not do it.”
Simon said, “Harper did it.”
Harper said, “Simon lied when he said that I did it.”

If the authorities also know that exactly one of the four suspects is telling the truth, who did it?

Set up a truth table for all the possibilities as follows:

Kimtruthtelling

Then the first four columns show the suspects and the scenarios of who possibly lied and who possibly told the truth. The second four columns show what can be understood by assuming that the respective suspect is the only one who told the truth.

Thomas is telling the truth: This results in both Simon and Kim being guilty, which can't be.

Kim is telling the truth: Since Simon and Harper contradict each other, one of them must be telling the truth. But since we are assuming only Kim is telling the truth in this scenario, this cannot be the case.

Simon is telling the truth: This results in both Harper and Kim being guilty, which can't be.

Harper is telling the truth: This means that Kim is the criminal, which is the correct answer. \(_\square\)

Let's try a harder problem.

Saeed and Grover are two mathematicians, and \(f_1\) and \(f_2\) are two integers such that each is greater than \(1\) and their sum is not greater than \(100.\) Saeed is told the total \(f_1+f_2\), and Grover is told the product \(f_1\times f_2\).

Both Saeed and Grover have the above information and they are both perfect in their logic. Then the following conversation occurs:

Grover says, "I do not know \(f_1\) and \(f_2\)."
Saeed says, "I know that you don't know."
Grover says, "Now I also know \(f_1\) and \(f_2\)!"
Saeed says, "So do I."

What are the values \(f_1\) and \(f_2\)?

After Grover’s first statement, we know that there is not a unique decomposition of the product \(f_1 \times f_2\) in \(f_{1}, f_{2} > 1\) with \(f_{1} + f_{2} ≤ 100\). From this we conclude:

\(f_{1}\times f_{2}\) cannot be the product of two distinct primes, for then Grover could deduce the numbers.

\(f_{1}\times f_{2}\) cannot be the cube of a prime, such as \(3^{3} = 27\), for then \(3×9 =27\) would be a unique factorization; or the fourth power of a prime.

\(f_{1}\times f_{2}\) does not contain a prime factor greater than \(50\).

From Saeed's first statement, we learn that all splittings of the sum in \(f_{1}\) and \(f_{2}\) satisfy the above conditions. This implies that the sum is odd (for Goldbach’s conjecture that all even numbers except \(2\) and \(4\) are the sum of two primes, holds below \(100\)). Finally the sum is not of the form \(f_{1}+f_{2}=q+2,\) where \(q\) is a prime number and the sum is less than \(50\) (since \(53\) is the smallest prime greater than \(50\)).

Therefore the list of plausible sums are:

\[f_{1}+f_{2}\in S=\{11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53\}.\]

Grovers statement "Now I also know \(f_1\) and \(f_2\)!" implies he now knows that sum is one of the values listed above. If this enables him to deduce \(f_{1}\) and \(f_{2}\), then, of the eligible factorizations of \(f_{1}\) times \(f_{2}\), there must be precisely one for which the sum of the factors is in the list. Now, we make the following observation:

Are the numbers \({ f }_{ 1 }\times { f }_{ 2 }={ 2 }^{ k }\cdot q\) with \(q\) prime, \(k>1\) and \(2^{k}+q\in f_{1}+f_{2}\) eligible (because all decompositions of \(f_{1}\times f_{2}\) have an odd sum)?

Saeed's final statement "So do I" implies that the sum \(f_{1}+f_{2}\) must admit exactly one eligible product. We can observe that \(11, 23, 27, 29, 35, 37, 41, 47, 51, 53\) all admit at least two eligible products. \(17\) is the only number that admits only one eligible product, where \(k=2\) and \(q=13\). Thus the values of \(f_{1}\) and \(f_{2}\) are \(4\) and \(13\). \(_\square\)

Sample problems

\[\] Problems from Brilliant:

\[\] Reference from other sites:

May 15	May 16	May 19
June 17	June 18
July 14	July 16
August 14	August 15	August 17

Contents

No copyright infringement intended.

Image credit: Wikipedia Tatiana Sapateiro