The Mathematica Journal
Departments
Download This Issue
Home
Feature Articles
Graphics Gallery
Tricks of the Trade
In and Out
Columns
The Mathematica Programmer
New Products
New Publications
Classifieds
Calendar
News Bulletins
Editor's Pick
Mailbox
Letters
Write Us
About the Journal
Staff and Contributors
Submissions
Subscriptions
Advertising
Back Issues

Puzzle 2

The Problem

In February 1996, Robert Israel posed the following problem in the newsgroup sci.math.symbolic.

Given the following expression [Graphics:../Images/index_gr_43.gif],

[Graphics:../Images/index_gr_44.gif]

is [Graphics:../Images/index_gr_45.gif] always equal to 1 if one substitutes 0 or 1 for all variables?

The Solution

The question of is [Graphics:../Images/index_gr_46.gif] 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 [Graphics:../Images/index_gr_47.gif]. The problem turns out to be quite similar to Puzzle #1.

The variables of [Graphics:../Images/index_gr_48.gif] are

[Graphics:../Images/index_gr_49.gif]
[Graphics:../Images/index_gr_50.gif]

In this case there are about 67 million different substitutions.

[Graphics:../Images/index_gr_51.gif]
[Graphics:../Images/index_gr_52.gif]

Let's try a few randomly chosen substitutions.

[Graphics:../Images/index_gr_53.gif]
[Graphics:../Images/index_gr_54.gif]
[Graphics:../Images/index_gr_55.gif]
[Graphics:../Images/index_gr_56.gif]
[Graphics:../Images/index_gr_57.gif]

This looks like the conjecture is true, but of course it is no proof. The resulting numbers will be larger than machine integers.  So, we don't want to try all of the possibilities, since using integer bignum arithmetic will make the whole calculation time consuming.

[Graphics:../Images/index_gr_58.gif] has the structure product+1. For the whole expression to be [Graphics:../Images/index_gr_59.gif], product should be 1. This means we must look for realizations where the factors of the product are [Graphics:../Images/index_gr_60.gif].

[Graphics:../Images/index_gr_61.gif] is a list of the factors of [Graphics:../Images/index_gr_62.gif].

[Graphics:../Images/index_gr_63.gif]

The function make1 calculates the substitution rules for the variables of expr, so the resulting expression is [Graphics:../Images/index_gr_64.gif].

[Graphics:../Images/index_gr_65.gif]

Here is a test of make1.

[Graphics:../Images/index_gr_66.gif]
[Graphics:../Images/index_gr_67.gif]
[Graphics:../Images/index_gr_68.gif]
[Graphics:../Images/index_gr_69.gif]

The function combineRealizations combines two realizations into a new set of feasible ones.

[Graphics:../Images/index_gr_70.gif]
[Graphics:../Images/index_gr_71.gif]

Here is another example.

[Graphics:../Images/index_gr_72.gif]
[Graphics:../Images/index_gr_73.gif]
[Graphics:../Images/index_gr_74.gif]
[Graphics:../Images/index_gr_75.gif]
[Graphics:../Images/index_gr_76.gif]
[Graphics:../Images/index_gr_77.gif]
[Graphics:../Images/index_gr_78.gif]
[Graphics:../Images/index_gr_79.gif]

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 variables that yields the variables of a given realization.

[Graphics:../Images/index_gr_80.gif]

The list actualLength acts as a container for counting the number of realizations permitted in the intermediate steps.

[Graphics:../Images/index_gr_81.gif]
[Graphics:../Images/index_gr_82.gif]
[Graphics:../Images/index_gr_83.gif]
[Graphics:../Images/index_gr_84.gif]

We found only 715 possible solutions that obey our constraint. 715 solutions out of [Graphics:../Images/index_gr_85.gif] 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.

[Graphics:../Images/index_gr_86.gif]
[Graphics:../Images/index_gr_87.gif]

Here is a graphic showing the number of realizations we had in intermediate steps.

[Graphics:../Images/index_gr_88.gif]

[Graphics:../Images/index_gr_89.gif]

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 [Graphics:../Images/index_gr_90.gif]. For efficiency, we can use the numbers themselves, dropping the Rule and the variable name (which uniquely follows from its position).

[Graphics:../Images/index_gr_91.gif]
[Graphics:../Images/index_gr_92.gif]

First, we unite solutions which are adjacent after sorting.

[Graphics:../Images/index_gr_93.gif]
[Graphics:../Images/index_gr_94.gif]
[Graphics:../Images/index_gr_95.gif]

With this smaller list, we also can search for nonadjacent pairs.

[Graphics:../Images/index_gr_96.gif]
[Graphics:../Images/index_gr_97.gif]
[Graphics:../Images/index_gr_98.gif]

So, we have only 79 unique realizations. To check this, we can see that by replacing the constant [Graphics:../Images/index_gr_99.gif] with 0 and 1, we are back to our original 715 solutions.

[Graphics:../Images/index_gr_100.gif]
[Graphics:../Images/index_gr_101.gif]
[Graphics:../Images/index_gr_102.gif]

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.

[Graphics:../Images/index_gr_103.gif]

[Graphics:../Images/index_gr_104.gif]


Converted by Mathematica      October 5, 1999

[Prev Page][Next Page]