Loading [MathJax]/extensions/tex2jax.js

Problem #86

The Augean Stables

The story

Hercules' task this time is to clean the Augean stables. They are in a right old mess. Hercules eventually hits upon the idea of diverting a nearby river into the stables in order to clean it. This gets rid of the muck but sadly a lot of vegetation has overgrown on the grounds that Hercules will have to weed out the hard way. In order to pass his time, he invites the local farmhand to play a game with him, using the weeds.

The game

Each weed is divided into a certain number of parts, and players take turns cutting off a part. Any section of the plant that is not connected to the ground after a cut is also removed. Play continues until the last person to make a cut wins.

Hercules always goes first.

Each weed is represented as a graph, with edges representing pieces of the plant that can be cut off in a turn. The node labelled 0 is the one that is connected to the ground.

Now, here are the adjacency matrices of 7 such weeds. Consider the 127 games that can be played with some combination of these weeds. For example, Hercules can always win the game played on just weed 1, but he will always lose the game played with both weeds 1 and 3. Find all the combinations of weeds such that Hercules will always lose the game played with them. Enter your input in the following fashion:

The combination (1,3) is considered as the binary number 1010000 (the first and third places are set to 1), and the combination (1,6,7) is 1000011. Convert your combinations into binary numbers and enter their sum in decimal.

Contributed by Project Gauss

Solved by 12 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.