The Bogotá Marathon

Question

a) Runners at the coming Bogotá Half Marathon have been assigned consecutive numbers starting at 1.

Lorena, running for the first time, has noticed that the sum of the numbers of all the athletes with numbers less to hers is equal to the sum of the numbers of all the athletes with numbers larger than hers.

If more than 100 runners-but fewer than 1000- are taking part in the marathon, what number was Lorena assigned?

b) At another Marathon, with a much larger number of runners, two of them, Anne and Beth, claimed that they were assigned numbers such that the sum of the numbers of all those with numbers less than Anne's was precisely equal to the the sum of the numbers of all the athletes with numbers strictly between hers and Beth's, and, in fact, equal to the sum of the numbers assigned to all those with numbers greater than Beth's.

Could this really have happened? If so, at least how many runners at that marathon?

Answer 1

Part A & Partial answer to part B

Part A

Lorena is number 204 in a match with total 288 participants. The sum from 1 to 203 is the same as the sum from 205 to 288, which is 20706.

There isn't any fancy method I used to crack this, I simply wrote a program to test out possible scenarios one-by-one since there is not a lot(participant limited under 1000). Below is the code if anyone is interested.

let numberOfParticipants = 101

function sum(a, b) {
    let sum = 0
    for (let i = a; i <= b; i++) sum += i
    return sum
}

while (true) {
    console.log(Checking for ${numberOfParticipants} participants)
    for (let i = Math.floor(numberOfParticipants / 2); i < >!numberOfParticipants; i++) {
        if (sum(1, i - 1) == sum(i + 1, numberOfParticipants)) {
            console.log(Works when Lorena is number ${i})
            throw new Error() // Used to force exit the infinite loop
        }
    }

    numberOfParticipants++
}

Part B partial answer.

Recall that consecutive integers form an Arithmetic sequence with a common difference. To calculate the sum of an arithmetic sequence A to B, we can use the formula $$S = ((A+B)*N)/2$$, where N is the number of items in the sequence. Let's make A the number of Anne, B the number of Beth, and P the total number of participants, and we can have the following equation: $$1+2+3+...(A-1)=(A+1)+...+(B-1)=(B+1)+...+P$$ This is a three part equation since the three sums equal to each other. Using the formula above for the sum, we can rewrite the three sums in this format: $$\frac{(1+(A-1))((A-1)-1+1)}{2}=\frac{((A+1)+(B-1))((B-1)-(A+1)+1)}{2}=\frac{((B+1)+P)(P-(B+1)+1)}{2}$$ If we drop the middle part and only keep the other two, after some rearranging, we get a much cleaner equation: $$A(A-1)=P(P+1)-B(B+1)$$ With the middle part: $$A(A-1)=(A+B)(B-A-1)=P(P+1)-B(B+1)$$ Now I am stuck from here. If we can find a solution for this equation where A, B, P are integers then I think that's the answer. Otherwise if we can prove that no integer solutions exist that's also an answer. Maybe 3D graphing (substitute ABP with XYZ) could help.

Answer 2

Some comments on part (b)

(Warning: highbrow mathematics ahead, done by someone not actually particularly expert in the relevant field. Non-mathematicians will be intimidated, actual experts will likely be horrified.)

We are, after a bit of algebraic manipulation, looking for positive integers x < y < z satisfying the equations $2x^2=y(y-1)$ and $2y^2=x(x+1)+z(z+1)$. ($x$ is Anne's number, $y$ is Beth's, and $z$ is the number of runners in the race.)

I see two ways to continue from here. I'll begin with the lower-brow one because it's much easier (though still fairly mathsy) and seems to be substantially more efficient when all we're trying to do is to prove that there aren't solutions smaller than some limit. Then I'll describe the higher-brow one, which I think would be needed if we wanted to find all solutions or prove that there are none.

Lowerbrow approach: Pell's equation

Let's just look at the relationship between $x$ and $y$: Anne versus Beth. This is a standard Pell's equation plus a parity constraint, and the solution turns out to be: look at $(1+\sqrt2)^{2n}$ for integer $n$; this will have form $a_n+b_n\sqrt2$; then we have $a_n^2-2b_n^2=1$, $a_n$ odd, $b_n$ even; then write $x=b_n/2$ and $y=(a_n+1)/2$. There's an efficient way to compute these values, which I'll come to in a moment. And then we can use the second equation to find what $z(z+1)$ has to be, and hence what $4z(z+1)+1=(2z+1)^2$ has to be, and we can just check whether that last thing is a square.

To compute all the $a_n,b_n$ we can use the recurrence relation: $a_{n+1}=3a_n+4b_n$ and $b_{n+1}=2a_n+3b_n$. We start with $a_0=1,b_0=0$. This is all very easy to do with a computer, and I have run it as far as $n=826000$ at which point our candidate values of $x$ have a little over 2100000 binary digits; that is, our number of marathon numbers would need to have over 600000 decimal digits.

(If we take $n=-1$ then we get the "solution" $x=1,y=-1,z=0$; in general, negative $n$ means negative $y$. If we take $n=0$ we get the "solution" $x=0,y=1,z=1$. Neither of these describes a possible marathon. If we take $n=1$ we get $x=1,y=2,z=2$ which does describe a possible marathon but we were asked for "a much larger number of runners".)

OK, now for the heavy artillery. This doesn't actually turn out to get us anything beyond what I've done above -- quite the reverse -- but my guess is that the Pell's-equation approach above will not yield an actual solution in reasonable time, and that it can't prove that there aren't any, whereas someone who knows more than I do about elliptic curves might be able to get a solution or an impossibility proof out of them.

Higherbrow approach: elliptic curves

Three unknowns, two equations: this gives us a curve. Call it $C_1$. (There will be some more to come.) What sort of a curve? Well, it's the intersection of two "quadric surfaces" in three-dimensional space. If we projectivize them, so that our equations become $2x^2=y(y-w)$ and $2y^2=x(x+w)+z(z+w)$ -- call the resulting curve in projective 3-space $C_2$ -- then we can do the following standard calculation: make sure the $w^2$ terms are both zero, which they are, write these as $Aw+B=0$ and $Cw+D=0$ where $A,B$ are linear in $x,y,z$ and $C,D$ are quadratic in $x,y,z$, and eliminate $w$ getting $AD=BC$, a homogeneous cubic equation in $x,y,z$. In this case it turns out to be $2x^3-x^2y+2x^2z-xy^2+2y^3+y^2z-yz^2=0$. Call this $C_3$. (Given a point $(x:y:z)$ on $C_3$, we can then use $Aw+B=0$ to get $w=y-2x^2/y$ (or, if $y=0$, instead use $Cw+D=0$ to get $w=(2y^2-x^2-z^2)/(x+z)$) so that $(x:y:z:w)$ is a point on $C_2$; and then we can recover the original $x,y,z$ on $C_1$ by taking $(x/w,y/w,z/w)$.)

So we have a projective planar cubic curve, and the point $(0,0,0)$ on the original curve -- corresponding to a marathon with zero runners, of whom Anne and Beth are numbered 0 -- corresponds to the point we get by solving $A=B=0$, namely $(-1:0:1)$. This is a rational point on our cubic curve, and a cubic curve with a rational point is an elliptic curve. We can now use a fancy computer algebra system to put it into the standard Weierstrass form, getting $y^2 = x^3 + 7x^2 + 4x + 4$ or, projectively, $y^2z = x^3 + 7x^2z + 4xz^2 + 4z^3$ -- call this one $E$ -- and handy maps between the earlier form and this one: map $(x:y:z)$ on $C_3$ to $(4xy:-8x^2-2xy-2y^2+2yz:-xy+y^2-yz)$ on $E$, and map $(x:y:z)$ on $E$ to $(-\frac14x^3 - \frac{11}4x^2z + \frac14y^2z - 7xz^2 - z^3:-2xz^2 + 2yz^2 - 4z^3:x^2z + 8xz^2 + 2yz^2 + 20z^3)$. Obviously :-).

So, now we can use that fancy computer algebra system again to find the so-called Mordell-Weil group of $E$. That is: all rational points on $E$ (together with some extra structure: they form an "abelian group"). This turns out to be a free abelian group of rank 2, which means we can find points $p,q$ on $E$ such that the rational points on $E$ are exactly the points $mp+nq$ for integer $m,n$, where the meanings of $mp$, $nq$ and $+$ are defined (in a fairly intricate way) by that group structure. For instance, we can take $p=(-4:6:1)$, corresponding to point $(1:2:2)$ on $C_3$, corresponding to point $(1:2:2:1)$ on $C_2$, corresponding to point $(1:2:2)$ on $C_1$. (Does this make any sense? Well, we can check that a marathon with 2 runners, Anne being #1 and Beth being #2, satisfies our equations, and in fact is even a possible marathon.) And then we can take $q=(0:2:1)$, corresponding to point $(0:0:1)$ on $C_3$, corresponding to point $(0:0:-1:1)$ on $C_2$, corresponding to point $(0:0:-1)$ on $C_1$. This too passes the sanity check: a marathon with -1 runners, where Anne and Beth are both #0, may not make any sense as a race but the equations are satisfied.

So far, so good. We have a way to enumerate every possible rational point on $E$; because we have these rational maps between $C_1$, $C_2$, $C_3$, and $E$, rational points on $E$ are the same as rational points on $C_1$ aside from a few technicalities around 0-valued coordinates. But, alas, we want something more: integer points on $C_1$ satisfying certain inequalities.

There are standard ways to find all the integer points on $E$, but alas that isn't at all the same thing as finding integer points on $C_1$. What we can do is to enumerate rational points on $E$ in some sensible order, convert them into points on $C_1$, and see whether they work out. Or, more precisely, tell a computer to do that.

Well, with the two generators I picked above, I have verified that we get no solutions from $mp+nq$ for $-200\leq m,n\leq+200$. Just what does that let us exclude?

There is a thing you can calculate, given a rational point (typically, but not necessarily, on an elliptic curve), called its height; it's just a measure of how large the numbers defining it are. For instance, the height of the point $(-4:6:1)$ is just log(4). The height is "almost" well-behaved with respect to the "group law"; there is a related thing (when we are specifically talking about points on an elliptic curve) called the "canonical height" which has the property that $h(mp+nq)=Ap^2+Bpq+Cq^2$ for suitable $A,B,C$, and that's always within a bounded distance of the actual ("naive") height. This paper tells you a way to compute bounds on how far apart they are, and in this case if I've done the calculations right the difference is bounded on one side by about -1.457 and on the other by about 0.0625; it's certainly no bigger than 2 in absolute value. Given this, we can look at some actual height values and determine that we have $A\simeq0.726,B\simeq-0.373,C\simeq0.275$, and in particular that quadratic form is positive-definite, and (by looking at the "naive heights" for $\max(|m|,|n|)=200$) that any rational point on the curve that doesn't have $-200\leq m,n\leq+200$ has a height of at least about 9000.

And if we start with an integer point $(x,y,z)$ on $C_1$ then the corresponding point on $E$ is $(4xy:-8x^2-2xy-2y^2+2yz:-xy+y^2-yz)$ and the height of that can't be too much bigger than the height of $(x,y,z)$; in fact if $(x,y,z)$ has height $h$ then our point on $E$ has height no bigger than $2h+2$.

To recap a bit: any integer point on $C_1$ corresponds to a rational point on $E$, hence to a point of the form $mp+nq$ on $E$ where $m,n$ are integers. We found by exhaustive checking that any integer point with $0<x<y<z$ on $E$ has to have $\max(|m|,|n|)>200$, and that this implies that the height of our point on $E$ is at least (actually a bit more than) 9000. This implies that the height of the point $(x,y,z)$ on $C_1$ is at least 4500. And this implies that one of $x,y$ has to have at least about 1950 decimal digits.

(We could probably get to @hexomino's 7k digits this way, with a lot more computation. It seems less feasible to prove the "hundreds of thousands of digits" lower bound I gave above by this sort of calculation. But perhaps some deeper insight into rational points on elliptic curves would yield either an actual solution or a proof that none exists.)

Conclusions

So, anyway, I conclude

• No, there could not be such a marathon that fits into the observable universe. Any solution needs numbers that are at least hundreds of thousands of digits long.
• I do not know whether there could be one at all given the ability to have arbitrarily large numbers of runners.
• My guess is that there could, and the relevant number is absurdly large, and there is some clever way to find it.
• It seems unlikely that there is any complete solution that doesn't require some amount of expertise in elliptic curves.
• Congratulations, Bernardo Recamán Santos, you have shown that you know more about elliptic curves than we do. Perhaps you'd like to tell us the answer.

(As I mentioned in comments on the original question, this reminds me of https://www.reddit.com/r/puzzles/comments/azf0zo/im_stuck_on_this_one/ -- a puzzle presented in the same way as all those stupid "95% of people got this WRONG!!" things that do the rounds on social media, but where the difficulty isn't some order-of-operations thing or a matter of noticing that one shoe has an extra lace on it, but that the puzzle comes down to finding integer points on an elliptic curve, the smallest solution is extremely large, and there is no possible way to find it that would be accessible to anyone other than experts. It's trolling, basically. Which is roughly how I feel about this one.)

Answer 3

Part 1 solved.

I solved part 1 (the warm-up) with a brutal pair of loops.
Lorena is position 204 out of 288 runners.
Preparing for part 2, I first extended the constraint of number of runners, and found a series of solutions for part 1, which is A001108. The number of runners is

[0, 1,] 8, 49, 288, 1681, 9800, 57121, 332928, 1940449, 11309768, 65918161, 384199200, 2239277041, ...

Part 2 partial.

Clearly there will be a problem brutally using 3 nested loops.

So I turned the problem round, so that I could use a single loop (Anne / Lorena's position), and compute the number of runners needed to satisfy the problem. This was a simple quadratic to solve by the usual method.
With
$A$ = Anne's position
$R$ = number of runners
$suma$ = the the sum of the places before Anne (a function of $A$)

$R^2 + R - (A^2 + A + 2 \times suma) = 0 $

Solving for $R$ gave the same results in a fraction of the time, with a single loop for Anne's position. Having done that, for each solution, I set Beth's position

$B = R + 1$

and again solved a similar quadratic for the new number of runners now needed for part 2, and no more looping is required. However, in my working range I found no solutions, and the typical 64-bit double type used for the square root is inadequate to retain enough significance: I would need to make a bignum solution.

So that's where I left it.

Edit

On reviewing part 1 without constraining the number of runners, the position of Lorena (in valid solutions) also follows a series. I already mentioned that the number of runners follows series A001108. Now I see the Lorena's position (and by extension to Anna's in Part 2) follows another series A001109. Both of these series are easily computable following the Olivares formulas in both cases.

I am working with max 32-bit number of runners, and putting those series together, the series for which Part 2 is based can be generated in a fraction of a second.

Lorena=6 runners=8
Lorena=35 runners=49
Lorena=204 runners=288
Lorena=1189 runners=1681
Lorena=6930 runners=9800
Lorena=40391 runners=57121
Lorena=235416 runners=332928
Lorena=1372105 runners=1940449
Lorena=7997214 runners=11309768
Lorena=46611179 runners=65918161
Lorena=271669860 runners=384199200
Lorena=1583407981 runners=2239277041

I also used an exact 64-bit integer square root function, and determined empirically that there are no solutions for a 32-bit number of runners.

But because I have no solutions for Part 2 with which to see a trend, I can't go further. Perhps another contributer can project to a third OEIS sequence.

Answer 4

I will repeat what others have already said about part a:

Lorena is running with number 204 out of 288 participants

I went with the easy way and used computer for that. Code:

sums = {100: 5050}

for i in range(101, 1001):
    sums[i] = sums[i - 1] + i

# Print the sum for 1000
sums_1000 = sums.get(1000)

reverseSums = {v: k for k, v in sums.items()}

result = []
for i in range(101, 1001):
    totalNr = sums[i - 1] * 2 + i
    if totalNr in reverseSums:
        result.append((i, reverseSums[totalNr]))

sums_1000, result

For part b I also went with the computer approach, but so far no answer was found. Not sure if I made a mistake in the code or if I should just go higher than 5000000

Code that I used for part b:

maxValue = 5000000
sums = {100: 5050}

for i in range(101, maxValue + 1):
    sums[i] = sums[i - 1] + i

reverseSums = {v: k for k, v in sums.items()}

result = []
for i in range(204, maxValue):
    for j in range(i + 1, maxValue):
        totalNr = sums[i - 1] * 3 + i + j
        if totalNr in reverseSums:
            if sums[i - 1] == sums[j - 1] - sums[i]:
                if sums[j - 1] - sums[i] == totalNr - sums[j]:
                    print("found!")
                    print(i)
                    print(j)
                    print(reverseSums[totalNr])
                    result.append((sums[i - 1], sums[j - 1] - sums[i - 1], totalNr, reverseSums[totalNr], i, j, reverseSums[totalNr]))
                    break
    if result:
        break

result

Also not sure if the code can be optimized or not, I wrote that in Apex (Salesforce's dialect of Java), but the execution took too long and timed out, so asked ChatGPT to convert it into something more performant and it generated this Python code for me