## Problem 376

**Forum rules**

As your posts will be visible to the general public you

are requested to be thoughtful in not posting anything

that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

See also the topics:

Don't post any spoilers

Comments, questions and clarifications about PE problems.

### Problem 376

I think i've got how to do this, just I'm not quite sure of a few things

For N = 7, which of these sets would be allowed?

{1,2,3,4,5,6}

{1,2,3,4,5,7}

{1,1,1,7,7,7}

{2,2,3,3,4,4}

{2,3,3,3,3,3}

{1,1,1,1,1,1}

{1,2,7,7,7,7}

etc...

Basically, I just don't get the conditions of which sets would be allowed

Could someone please clarify the conditions.

Thanks

For N = 7, which of these sets would be allowed?

{1,2,3,4,5,6}

{1,2,3,4,5,7}

{1,1,1,7,7,7}

{2,2,3,3,4,4}

{2,3,3,3,3,3}

{1,1,1,1,1,1}

{1,2,7,7,7,7}

etc...

Basically, I just don't get the conditions of which sets would be allowed

Could someone please clarify the conditions.

Thanks

Last edited by kevinsogo on Thu Apr 25, 2013 12:40 pm, edited 1 time in total.

**Reason:***Title should be "Problem XXX"*### Re: problem 376 clarification

Warning: Pick with a grain of salt, I just looked over the problem.

My understanding is that all of these sets are valid. In fact if you consider a single die, any set with numbers in [1,7] is valid.

My understanding is that all of these sets are valid. In fact if you consider a single die, any set with numbers in [1,7] is valid.

### Re: problem 376 clarification

Hmm... When testing N = 7 I get much more than thisIdesnogu wrote:"In fact if you consider a single die, any set with numbers in [1,7] is valid"

It could just be my code. Don't know

Last edited by psujono on Sun Mar 18, 2012 10:47 am, edited 2 times in total.

### Re: problem 376 clarification

Note there are restriction between two dice, I only talked about *one* diepsujono wrote:Hmm... When testing N = 7 I get much more than thisIdesnog said:

"In fact if you consider a single die, any set with numbers in [1,7] is valid"

It could just be my code. Don't know

### Re: problem 376 clarification

So would you call this a valid set:

{3,3,6,6,6,6}

{3,4,4,5,7,7}

{4,5,5,5,5,6}

{3,3,6,6,6,6}

{3,4,4,5,7,7}

{4,5,5,5,5,6}

### Re: problem 376 clarification

What rule do you think your set would break?

The problem seems to just say these two sets are the same:

{{3,3,6,6,6,6},{3,4,4,5,7,7},{4,5,5,5,5,6}}

and

{{3,4,4,5,7,7},{3,3,6,6,6,6},{4,5,5,5,5,6}}

The problem seems to just say these two sets are the same:

{{3,3,6,6,6,6},{3,4,4,5,7,7},{4,5,5,5,5,6}}

and

{{3,4,4,5,7,7},{3,3,6,6,6,6},{4,5,5,5,5,6}}

### Re: problem 376 clarification

Just a few words from the moderator.

In the big box at the top of the page, in one of the linked topics Comments, questions and clarifications about PE problems it reads:

"If there is no previous topic for the specific problem you are trying to solve, you may start a new topic, giving as subject Problem xxx. Please do not use in the Subject-field expressions like "Clarification needed", "problem with the wording", "Correct answer not accepted" etc"

So I fail to see why it should have been called : "problem 376 clarification"

Secondly the subtitle of this forum reads:

"A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions."

In my opinion this also means: don't start a discussion about what can be meant.

Those that solved it or the PE team can answer questions judiciously if they think it wise to do so.

I would like to add:

This forum is not meant to openly discuss problems.

Please stop this dicussion until the problem is solved by at least 50, but preferably many more.

In the big box at the top of the page, in one of the linked topics Comments, questions and clarifications about PE problems it reads:

"If there is no previous topic for the specific problem you are trying to solve, you may start a new topic, giving as subject Problem xxx. Please do not use in the Subject-field expressions like "Clarification needed", "problem with the wording", "Correct answer not accepted" etc"

So I fail to see why it should have been called : "problem 376 clarification"

Secondly the subtitle of this forum reads:

"A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions."

In my opinion this also means: don't start a discussion about what can be meant.

Those that solved it or the PE team can answer questions judiciously if they think it wise to do so.

I would like to add:

This forum is not meant to openly discuss problems.

Please stop this dicussion until the problem is solved by at least 50, but preferably many more.

### Re: problem 376 clarification

I also misread the question initially so here is a clarification that would have helped me and I hope is not considered to spoil the question.

Suppose A has a probability of 20% of winning, and a probability of 10% of losing, and there is a 70% probability of a draw. In this case A does NOT have a >50% chance of winning.

Suppose A has a probability of 20% of winning, and a probability of 10% of losing, and there is a 70% probability of a draw. In this case A does NOT have a >50% chance of winning.

### Re: problem 376 clarification

Umm... So we can go here if we don't understand what the problem means but we can't discuss what the problem might mean?hk wrote: Secondly the subtitle of this forum reads:

"A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions."

In my opinion this also means: don't start a discussion about what can be meant.

### Re: problem 376 clarification

Does {A,C,B} = {A,B,C}? i.e. Are all permutations of a set considered the same or is it just rotations of a specific permutation?The sets of dice {A,B,C}, {B,C,A} and {C,A,B} are the same set.

- Marcus_Andrews
- Administrator
**Posts:**1530**Joined:**Wed Nov 09, 2011 5:23 pm

### Re: problem 376 clarification

A=[1,4,4,4,4,4], B=[2,2,2,5,5,5], C=[3,3,3,3,3,6] and

A=[2,2,2,5,5,5], B=[1,4,4,4,4,4], C=[3,3,3,3,3,6] and

A=[3,6,3,3,3,3], B=[4,4,4,1,4,4], C=[5,2,5,5,2,2] etc.

would all count as 1 set

A=[2,2,2,5,5,5], B=[1,4,4,4,4,4], C=[3,3,3,3,3,6] and

A=[3,6,3,3,3,3], B=[4,4,4,1,4,4], C=[5,2,5,5,2,2] etc.

would all count as 1 set

### Re: problem 376 clarification

It should be pretty obvious that the answer to that question is quite irrelevant.szymczak wrote:Does {A,C,B} = {A,B,C}? i.e. Are all permutations of a set considered the same or is it just rotations of a specific permutation?The sets of dice {A,B,C}, {B,C,A} and {C,A,B} are the same set.

### Re: problem 376 clarification

I thought the same at first but after re-reading the question now I am not so sure. The question states:TripleM wrote:It should be pretty obvious that the answer to that question is quite irrelevant.szymczak wrote:Does {A,C,B} = {A,B,C}? i.e. Are all permutations of a set considered the same or is it just rotations of a specific permutation?The sets of dice {A,B,C}, {B,C,A} and {C,A,B} are the same set.

Therefore, the triples {[1 4 4 4 4 4], [2 2 2 5 5 5], [3 3 3 3 3 6]} and {[2 2 2 5 5 5], [1 4 4 4 4 4], [3 3 3 3 3 6]} are both non-transitive (since whichever dice the first player picks the second player can pick a better one), and by rule 4 they are not necessarily the same. If we consider them as sets rather than triples then they are equal by the convention that sets are unordered, but in that case rule 4 is superfluous (and possibly misleading - why mention rotations but not transpositions?)So whatever die the first player picks, the second player can pick another die and have a larger than 50% chance of winning.

A set of dice having this property is called a nontransitive set of dice.

Rule 2 might cause confusion too. Strictly speaking it is dice with the same

*multiset*of pips that are equal rather than the same set.

(I hope I am not adding to the confusion. Marcus Andrews' post is the correct way to interpret this problem to get the given answer for N=7 and the green tick.)

### Re: problem 376 clarification

That's what I was unsure about. While the problem says we are countingstimmer wrote:

Therefore, the triples {[1 4 4 4 4 4], [2 2 2 5 5 5], [3 3 3 3 3 6]} and {[2 2 2 5 5 5], [1 4 4 4 4 4], [3 3 3 3 3 6]} are both non-transitive (since whichever dice the first player picks the second player can pick a better one), and by rule 4 they are not necessarily the same. If we consider them as sets rather than triples then they are equal by the convention that sets are unordered, but in that case rule 4 is superfluous (and possibly misleading - why mention rotations but not transpositions?)

Rule 2 might cause confusion too. Strictly speaking it is dice with the same multiset of pips that are equal rather than the same set.

*sets*, Rule 4 implies we are counting the number of equivalence classes of the set of 3-permutations (of dice) under rotation. Also, thanks for clarifying Rule 2.

### Re: problem 376 clarification

I assume that there was a mix-up between two definitions when the problem was being worded.szymczak wrote:While the problem says we are countingsets, Rule 4 implies we are counting the number of equivalence classes of the set of 3-permutations (of dice) under rotation. Also, thanks for clarifying Rule 2.

Sometimes a non-transitive set of dice is defined as a set of 3 dice where A beats B, B beats C, and C beats A. In that case rule 4 is all you need to say that re-orderings don't matter. The three other orders that were not mentioned do not satisfy the definition because they don't have the first beating the second etc.

The problem statement however defines a non-transitive set of dice as three dice where A is beaten by one of the other dice, B is also beaten by one of the other dice, as is C. So you could have A is beaten by B, B is beaten by C, C is beaten by by A. In this case rule 4 is misleading precisely because it does not fit with the definition and seems to imply more than was intended.

_{Jaap's Puzzle Page}

### Re: problem 376 clarification

I have came to the solution for N = 7, which is basically some code (that I'm not allowed and won't share).

How can I get to N = 30 in a reasonable computation time? I would thought to turn the code into a formula, but is there any generalized way of turning algorithms into formulas?

What am I missing, I can't seem to make any sense of it. But I guess I need a bit more common knowledge to be able to solve the N = 30 case.

How can I get to N = 30 in a reasonable computation time? I would thought to turn the code into a formula, but is there any generalized way of turning algorithms into formulas?

What am I missing, I can't seem to make any sense of it. But I guess I need a bit more common knowledge to be able to solve the N = 30 case.

- mverschaeve
**Posts:**676**Joined:**Mon Nov 24, 2008 10:26 am**Location:**Ghent, Belgium

### Re: problem 376 clarification

I proposed this problem and suggested most of the final wording, I can assure you there was no mix-up.jaap wrote: I assume that there was a mix-up between two definitions when the problem was being worded.

When interpreting the word 'set' as a

*mathematical*set, rule 4 might seem indeed superfluous, reordering elements in a set does not make it a different set.

However 'set' can also be interpreted non-mathematically as the collective noun for a collection of dice, in that case it seems necessary to stress that order is unimportant.

Also because we labeled elements in the set in order to explain the statistics, we thought it might be misinterpreted that order was important.

So that was our motivation for adding rule 4. I think at least an equal amount of people would have been confused if we had omitted it.

### Re: problem 376 clarification

That doesn't explain why rule 4 only mentions only half the possible permutations - exactly only the rotations - as if only those are significant. I would propose the wording be changed frommverschaeve wrote:When interpreting the word 'set' as amathematicalset, rule 4 might seem indeed superfluous, reordering elements in a set does not make it a different set.

However 'set' can also be interpreted non-mathematically as the collective noun for a collection of dice, in that case it seems necessary to stress that order is unimportant.

Also because we labeled elements in the set in order to explain the statistics, we thought it might be misinterpreted that order was important.

So that was our motivation for adding rule 4. I think at least an equal amount of people would have been confused if we had omitted it.

toThe sets of dice {A,B,C}, {B,C,A} and {C,A,B} are the same set.

The sets of dice {A,B,C}, {B,C,A}, {B,A,C}, etc. are the same set.

_{Jaap's Puzzle Page}

### Re: problem 376 clarification

Consider it a hint. If the ordered triple (A,B,C) fits the nontransitivity rule A < B < C < A (where "<" means "loses more than half the time"), the other permutations that fit the rule are exactly the rotations.jaap wrote:That doesn't explain why rule 4 only mentions only half the possible permutations - exactly only the rotations - as if only those are significant. I would propose the wording be changed fromtoThe sets of dice {A,B,C}, {B,C,A} and {C,A,B} are the same set.The sets of dice {A,B,C}, {B,C,A}, {B,A,C}, etc. are the same set.

Changing the problem statement now would muddy the waters, making the problem more difficult for future Eulerians than for those who saw the original problem statement.

### Re: problem 376 clarification

But the point is that A, B, and C are not defined in that way in the problem, but in a way that allows A>B>C>A as well.thundre wrote:If the ordered triple (A,B,C) fits the nontransitivity rule A < B < C < A (where "<" means "loses more than half the time"), the other permutations that fit the rule are exactly the rotations.

_{Jaap's Puzzle Page}