Problem 376

[psujono]

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

[ldesnogu]

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.

[psujono]

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

Hmm... When testing N = 7 I get much more than this
It could just be my code. Don't know

[ldesnogu]

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

Hmm... When testing N = 7 I get much more than this
It could just be my code. Don't know

Note there are restriction between two dice, I only talked about *one* die

[psujono]

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}

[ldesnogu]

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}}

[hk]

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.

[wrongrook]

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.

[mdean]

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.

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?

[szymczak]

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

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?

[Marcus_Andrews]

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

[TripleM]

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

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?

It should be pretty obvious that the answer to that question is quite irrelevant.

[stimmer]

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

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?

It should be pretty obvious that the answer to that question is quite irrelevant.

I thought the same at first but after re-reading the question now I am not so sure. The question states:

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.

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.

(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.)

[szymczak]

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.

That's what I was unsure about. While the problem says we are counting 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.

[jaap]

While the problem says we are counting 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.

I assume that there was a mix-up between two definitions when the problem was being worded.

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.

[TomWij]

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.

[mverschaeve]

I assume that there was a mix-up between two definitions when the problem was being worded.

I proposed this problem and suggested most of the final wording, I can assure you there was no mix-up.

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.

[jaap]

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.

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 from

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

to

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

[thundre]

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 from

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

to

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

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.

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.

[jaap]

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.

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.