Problem 756

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.
Post Reply
abenoit
Posts: 1
Joined: Tue May 04, 2021 2:54 am

Problem 756

Post by abenoit »

I've been trying to begin the most recent problem (756) but I'm struggling to understand exactly what it's asking, and mostly where the numbers from the first example come from.

From what I understand E is like the expected value of Delta with n and m. But if delta is S - S*, where does the fraction answer of E(delta|k,100,50) = 2525/1326 come from? It looks like it would be something along the lines of S/S*, since the numerator is 5050/2 (and 5050 is S in this case), but how would that make sense if delta uses subtraction and not division? Subtraction by itself also seems like a strange measure of error, since it'll greatly be affected by the magnitudes of S and S*.

I'm surely missing something very obvious here, but I would love a clarification of what the problem is asking, and where the given fraction answer comes from in simple terms. I would love to understand it even if it does turn out that I'm in over my head in solving it
pjt33
Posts: 70
Joined: Mon Oct 06, 2008 6:14 pm

Re: 756

Post by pjt33 »

abenoit wrote: Tue May 04, 2021 2:57 am From what I understand E is like the expected value of Delta with n and m. But if delta is S - S*, where does the fraction answer of E(delta|k,100,50) = 2525/1326 come from?
The fraction comes from expected. For any given tuple $(X_1, X_2, \ldots, X_m)$ the value of $S^*$ will be an integer, but you need to average over all possible such tuples.
pen_hh
Posts: 1
Joined: Tue May 04, 2021 4:28 pm

Re: Problem 756

Post by pen_hh »

Not being a native English speaker, I am struggling to understand the phrase "random, uniformly distributed, m-tuple" in the problem description. From my understanding the 'uniformly distributed' would mean that Xi-Xi-1 would be a constant value c, hence (1, 2, 3,..., m) and (2, 4, 6, ..., 2m ) would be valid tuples, but (1, 3, 4, ...) would not. Is my interpretation correct?
User avatar
jaap
Posts: 559
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 756

Post by jaap »

Uniformly distributed refers to the probability distribution, and means that when the m-tuple is chosen at random, every possible outcome is equally probable.
See Uniform Distribution.

Of course, you randomly choose only from the set of valid m-tuples (i.e. it must have m integers that are strictly increasing and have values between 1 and n inclusive).
Mike
Posts: 10
Joined: Wed Mar 29, 2006 8:03 am
Location: London, England

Re: Problem 756

Post by Mike »

Am I misunderstanding the delta Function?
In a set of 20 random values for S* - S, with m = 50, n = 100, and f(k) = k, I got:
-11,222,114,174,99,12,16,14,12,14,321,-10,5,16,107,118,8,183,314,107
with a mean value of 91.75 .

Typically, I find 10000 random samples of (Delta|k, 100, 50) have a mean around 100,
so I fail to see how the Expectation is going to be ~1.9 .

Is there a missing denominator in the definition of delta? (S* - S)/S , say?

Thanks
brob26
Posts: 8
Joined: Thu Nov 22, 2018 3:48 am

Re: Problem 756

Post by brob26 »

Mike wrote: Wed May 05, 2021 11:39 pm Am I misunderstanding the delta Function?
In a set of 20 random values for S* - S, with m = 50, n = 100, and f(k) = k, I got:
-11,222,114,174,99,12,16,14,12,14,321,-10,5,16,107,118,8,183,314,107
with a mean value of 91.75 .

Typically, I find 10000 random samples of (Delta|k, 100, 50) have a mean around 100,
so I fail to see how the Expectation is going to be ~1.9 .

Is there a missing denominator in the definition of delta? (S* - S)/S , say?

Thanks
There's nothing missing in the problem statement. I can only guess there's something wrong with your algorithm for sampling values of $S^*$
Image
Mike
Posts: 10
Joined: Wed Mar 29, 2006 8:03 am
Location: London, England

Re: Problem 756

Post by Mike »

As was to be expected, asking the question and obtaining reassurance that the problem statement was correct chased my difficulty away. Classic debugging solution! Thanks.
Post Reply