Problem 376

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
psujono
Posts: 7
Joined: Sun Mar 18, 2012 8:09 am

Problem 376

Post by 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 :)
Last edited by kevinsogo on Thu Apr 25, 2013 12:40 pm, edited 1 time in total.
Reason: Title should be "Problem XXX"
ldesnogu
Posts: 17
Joined: Wed Jan 11, 2012 10:04 am

Re: problem 376 clarification

Post by 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.
Image
psujono
Posts: 7
Joined: Sun Mar 18, 2012 8:09 am

Re: problem 376 clarification

Post by psujono »

Idesnogu wrote:"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
Last edited by psujono on Sun Mar 18, 2012 10:47 am, edited 2 times in total.
ldesnogu
Posts: 17
Joined: Wed Jan 11, 2012 10:04 am

Re: problem 376 clarification

Post by ldesnogu »

psujono wrote:
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 :wink:
Image
psujono
Posts: 7
Joined: Sun Mar 18, 2012 8:09 am

Re: problem 376 clarification

Post by 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
Posts: 17
Joined: Wed Jan 11, 2012 10:04 am

Re: problem 376 clarification

Post by 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}}
Image
User avatar
hk
Administrator
Posts: 11195
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: problem 376 clarification

Post by 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.
Image
wrongrook
Posts: 481
Joined: Sat Oct 17, 2009 10:39 pm

Re: problem 376 clarification

Post by 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
Posts: 170
Joined: Tue Aug 02, 2011 2:05 am

Re: problem 376 clarification

Post by mdean »

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.
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?
Image
szymczak
Posts: 15
Joined: Wed Nov 23, 2011 8:43 am

Re: problem 376 clarification

Post by 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?
Image
User avatar
Marcus_Andrews
Administrator
Posts: 1530
Joined: Wed Nov 09, 2011 5:23 pm

Re: problem 376 clarification

Post by 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
Image
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: problem 376 clarification

Post by TripleM »

szymczak wrote:
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
Posts: 10
Joined: Mon Jul 25, 2011 5:56 pm

Re: problem 376 clarification

Post by stimmer »

TripleM wrote:
szymczak wrote:
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
Posts: 15
Joined: Wed Nov 23, 2011 8:43 am

Re: problem 376 clarification

Post by szymczak »

stimmer 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.
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.
Image
User avatar
jaap
Posts: 555
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: problem 376 clarification

Post by jaap »

szymczak wrote: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
Posts: 1
Joined: Tue Mar 20, 2012 2:35 pm

Re: problem 376 clarification

Post by 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.
User avatar
mverschaeve
Posts: 676
Joined: Mon Nov 24, 2008 10:26 am
Location: Ghent, Belgium

Re: problem 376 clarification

Post by mverschaeve »

jaap wrote: 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.
User avatar
jaap
Posts: 555
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: problem 376 clarification

Post by jaap »

mverschaeve wrote: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
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: problem 376 clarification

Post by thundre »

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 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.
Image
User avatar
jaap
Posts: 555
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: problem 376 clarification

Post by jaap »

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.
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.
Post Reply