Binary Variable Equations

Lars Rasmusson

Lars.Rasmusson@hp.com

Consider the following problem: Johnny's ideal woman is red-haired, green-eyed, slender, and tall. He knows four women.

Here are the requirements that they meet:

1. Only three of the women are both green-eyed and slender.

2. Only two of the women are both red-haired and tall.

3. Only two of the women are both slender and tall.

4. Only one of the women is both green-eyed and red-haired.

5. Adele and Betty have the same color eyes.

6. Betty and Carol have the same color hair.

7. Carol and Doris have different builds.

8. Doris and Adele are the same height.

9. Only one of the four women has all four characteristics.

To determine which one of the four women satisfies all of Johnny's requirements, one can set up and solve a system of equations involving binary variables: if Betty is red-haired, and so forth.

Define the binary variables as elements of lists corresponding to each attribute.

There are 20 variables.

Use to constrain the variables to be .

Set up the equations by translating each of the requirements.

We solve the system of equations using NSolve (this is much faster than using Solve), obtaining two solutions.

However, there is only one perfect girl.

There are two solutions because the heights of Betty and Carol are not determined.