## Puzzle 2## The ProblemIn February 1996, Robert Israel posed the following problem in the newsgroup sci.math.symbolic. Given the following expression ,
is always equal to 1 if one substitutes 0 or 1 for all variables? ## The SolutionThe question of is for all realizations can be answered using Groebner basis techniques in a straightforward fashion. To make this puzzle more interesting, let's not only answer the question stated here, but also the case of any realizations for which . The problem turns out to be quite similar to Puzzle #1. The variables of are
In this case there are about 67 million different substitutions.
Let's try a few randomly chosen substitutions.
This
has the structure is a list of the factors of .
The function , so the resulting expression is .
`expr`
Here is a test of
The function
Here is another example.
Having implemented all the necessary functions, we can perform the actual search. We step through all factors and keep only the compatible realizations. To do this efficiently, we need to address the situation where we have too many compatible realizations in the intermediate stages. To solve this problem we can use a simple rule. At a given stage, we choose the next set of factors so that the set has the most variables in common with the variables already determined.
We define a function
The list
We found only 715 possible solutions that obey our constraint. 715 solutions out of possibilities means that only about 0.002 percent of all possible realizations work. This explains why the above experiment, using just a dozen random realizations, failed to give a single 0. Let us verify the solutions found.
Here is a graphic showing the number of realizations we had in intermediate steps.
We actually can shorten the list of solutions. Looking at them, one sees pairs that are only different in the realization of one variable, which means this variable doesn't matter at all. We will unite them into one solution, replacing 0 or 1 in such pairs by . For efficiency, we can use the numbers themselves, dropping the
First, we unite solutions which are adjacent after sorting.
With this smaller list, we also can search for nonadjacent pairs.
So, we have only 79 unique realizations. To check this, we can see that by replacing the constant with 0 and 1, we are back to our original 715 solutions.
We can display the 79 compactified solutions in the form of a table where a dash "-" indicates that this variable can take either the value 0 or 1.
Converted by Mathematica
October 5, 1999
[Prev Page][Next Page] |