Project Euler Forum

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

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.

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 X_i-X_i-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?

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

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

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^*$

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.

I have trouble with the first example
E(Δ|k,100,50) = 2525/1326 ≈ 1.904223
Since Δ = S - S* f(k)=k is a monotonically-increasing function , then Δ < 0 , why won't the expected value be negative?
Will it be Δ = | S - S* |?

rsjw wrote: Thu Aug 26, 2021 2:54 pm I have trouble with the first example
E(Δ|k,100,50) = 2525/1326 ≈ 1.904223
Since Δ = S - S* f(k)=k is a monotonically-increasing function , then Δ < 0 , why won't the expected value be negative?
Will it be Δ = | S - S* |?

Take a closer look at what values X_m could take.

Thanks !