Problem 157

[quilan]

So, I finally figured out the trick to make it easy and I've got a rock solid algorithm for it, but my answer's not going through. Since it would give far too much away to announce it here, is there an admin I could PM to check something with?

[daniel.is.fischer]

Sure

[David F]

I think this has been brought up before, but I don't think it is very obvious what actual answer is expected here. Is the wording intentionally vague, or am I missing something?

(I've got the correct answer so I don't need help, but in the end I only tried it out of desperation. I still don't think it makes sense, to be honest).

[rayfil]

Is the wording intentionally vague, or am I missing something?

Every effort is always made to provide problem descriptions which are as clear as possible to avoid any ambiguity.

For Problem #157, the number of solutions (and their details) are given when the exponent n = 1 (i.e. p/10¹ = p/10).

The description clearly asks to report the total number of solutions when the exponent n is varied between 1 and 9 inclusive. Could you expand a bit more on which part may not have been clear enough for you.

[David F]

OK, in hindsight, and with the benefit of a short break away from the problem, I can see why a strict reading of the question gives the answer that is expected.

However, I think it is very easy (and reading people's responses on the solution thread, I don't think I was alone) not to realise that, for example, 1/1+1/1 = 20/10 is to be treated as a different solution to 1+1+1/1=200/100.

I don't think it would be unreasonable to point that out in the question wording, or, alternatively to simply state that the solution is the number of distinct quadtuples (a,b,p,n).

Again, with hindsight, this is my misreading of the question. But out of the last 50 problems, this is the only one where my main difficulty was a misunderstanding of the wording, rather than the underlying mathematics. It seems to me that ProjectEuler generally tries to avoid such situations even where clarification may not be strictly necessary.

[GenePeer]

However, I think it is very easy (and reading people's responses on the solution thread, I don't think I was alone) not to realise that, for example, 1/1+1/1 = 20/10 is to be treated as a different solution to 1+1+1/1=200/100.

I don't think it would be unreasonable to point that out in the question wording, or, alternatively to simply state that the solution is the number of distinct quadtuples (a,b,p,n).

Agreed. It would only cost one extra sentence in the description and avoid any confusion whatsoever. Aren't the descriptions supposed to be as clear as possible?

[TripleM]

What other possible interpretation is there? You're not asked for the number of values the sum can take; you're asked for the number of solutions to an equation. If you are asked for the solutions to x^2 - 3x + 2 = 0 you don't need to clarify that two solutions are different if they have different values of x, or that you don't count the solutions as the same because they both give a result of 0. There isn't any difference with this problem - adding it here would just be a bad precedent to require unnecessary wording in lots of other problems.

(I can't see anyone in the problem thread who misunderstood the question in the way you mentioned; just some for whom the above solutions were counted as the same due to a bug in their code).

[GenePeer]

(I can't see anyone in the problem thread who misunderstood the question in the way you mentioned; just some for whom the above solutions were counted as the same due to a bug in their code).

neverforget. That makes it three of us, that have mentioned it. And like David, this is the only problem in the last 59 I've done that I've misunderstood. But if the admins see no reason to change the wording, it's fine.

And can the admins combine tapan's consecutive posts on the second page of the problem's forum?

[hk]

And can the admins combine tapan's consecutive posts on the second page of the problem's forum?

Done.

[jake223]

Can anybody validate these results and tell me which ones are wrong? thanks in advance.
for 10^n: (cumulative)

n solutions
1 20
2 *06
3 *86
4 **82
5 **62
6 **60
7 ***86
8 ***64
9 ***38

[rayfil]

10² is wrong already.

[jake223]

thanks. i'll look further at my code.
EDIT: I stilll can't find my error. can I PM somebody my method/results for 10^2?

[jake223]

I think I figured out my problem, however I am still getting an incorrect answer. Can anybody point out where I start to go wrong? thanks.
[these are cululative]

1. 20
2. *22
3. *78
4. **36
5. **28
6. **84
7. ***44
8. ***32
9. ***90
10. ***86

[thundre]

10. ***86

That's where you're going wrong. From the problem statement:

How many solutions has this equation for 1 ≤ n ≤ 9?

So you shouldn't have an entry for n=10.

[jake223]

Oops. Thanks.

[Oliver1978]

Hmm, back after some time off I seem to have picked a "nice" one...

I've tried to brute-force my way into this and get e.g. 102 fractions for n = 2 and *56 for n = 3. I'm somewhat doubtful that this is correct...

[MuthuVeerappanR]

Hmm, back after some time off I seem to have picked a "nice" one...

I've tried to brute-force my way into this and get e.g. 102 fractions for n = 2 and *56 for n = 3. I'm somewhat doubtful that this is correct...

It indeed is..

[scientes]

It is simple problem after PE 108.

[creature]

Registered because I also feel the problem statement is ambiguous and no one has clearly explained the source of the ambiguity.

An earlier comment by euler says we're counting distinct quadruples (a, b, p, n).

But this never specified and one can just as well interpret the wording to mean total number solution pairs (a, b) for which 1/a + 1/b can be written in the form p/10, p/100, p/1000, etc. Especially while comparing with problems 108 and 110 where solution counting is done with a fixed value on the right side of a similar equation. Thus it's not clear there are multiple solutions with the same values of a and b.

Not only does the example for n = 1 convey no information to address this question but the restriction to a value of n reinforces the apparent connection to problems 108 and 110, which suggests we shouldn't concern ourselves with how p and n could be varied for fixed a, b.

In diophantine-like equations there's often a bit ambiguity in what is meant by a solution when specific solutions give rise to trivially related ones. Something like x/(x+1) = (m/n)^2 is conventionally interpreted to mean "find values of x for which x/(x+1) is the square of a rational number", not an invitation to describe an infinite set of trivial solutions by multiplying m and n by arbitrary constants. In problem 157 moving factors between p and the 10^n seems similarly trivial.

[Oliver1978]

Brute-force aside, I'm positively sure I've found the pattern in this. Alas my numbers seem incorrect. Would anyone mind to hear me about this, and either support or decline my thoughts?