How I failed to solve Math Olympiad Problem 3. And you thought I'd only post if I succeeded! Well you didn't think anything, but if you had thought about it maybe
Anyway, the exercise is thusly
One first shows that any prime number can only have two
smaller neighbors in any circle. So let p be a prime number and A,B be its two neighbors in the first circle. There are x,y such that
(1) x + x^2 + k = pA
(2) y + y^2 + k = pB
Wlog x > y. Subtracting (2) from (1) yields
p(A-B) = x + x^2 + k - y - y^2 - k = (x^2-y^2) + (x-y) = (x-y)(x+y) + (x-y) = (x-y)(x+y+1)
Since p is a prime number, it follows that p | x-y or p | x+y+1. (The | means "divides"). Suppose p|x-y. Then p <= x-y so p <= x or p <= y. Wlog p <= x. Then we find a contradiction via
pA = x + x^2 + k > x^2 >= p^2 > pA
So we must have p | x + y + 1, which means Np = x + y + 1 for some natural number N. Suppose N >= 2. Then x+y+1 >= 2p which again means x >= p or y>=p, so we get the same contradiction as above. Therefore, p = x+y+1.
Now let C be an arbitrary other prime that's a smaller neighbor of p in some circle. Using the circle property, we find a number z such that
(3) z + z^2 + k = pC
subtracting (3) from (1) and doing the same steps as before yields
(x-z)(x+z+1) = p(A-C)
If p(A-C) = 0, then C=A. Otherwise, the same argument as above shows that p = x+z+1. But then x+y+1=x+z+1 and hence y=z. Then pB = y+y^2+k = z+z^2+k = pC and hence C=B. So either C=A or C=B.
I figured this all out, too! So in particular, the largest prime number of the set has fixed neighbors (since it can only have smaller neighbors). Sounds very promising. Moreover, by comparing edges, you really restrict what prime numbers come next. Like if the circle starts A -- p -- B with x the integer sitting on the edge between A and p, then the next integer is either x - NA or (N+1)A-x-1, where N is the largest integer such that x-NA is still above 0. Also, the function f(x) = x^2 + x + k actually comes out the same for x-(N+1)A and (N+1)A-x-1; I really thought that would be significant. Anyway, there are only two choices how to continue the circle, and we can compute them exactly! Feels like that's really close!
And I could not conclude the proof from there. I could not. For the life of me. Figure out. How. To. Get. This. Stupid. Fucking. Lemma. Proven. From. Here. I. Couldn't. Do it.
Moreover, I found this:
This abomination that you currently see on your screen
photographed with a Q3 Leica Monocrhome Hyperflux Edition is an example of 4 prime numbers and two paths between them (k=31). Essentially, you can go (A,B,C,D) and also (A,C,B,D).
"Why is this significant?" you ask, clueless about the problem. Thanks for asking! It's significant because if we find any path between A and D, here 3 and 53 -- ANY PATH, whether it includes 0 or 2 or 47 or 2873766663299276 extra prime numbers -- then we will have found two circles with this property. So you now need to show that there is no way to do this. Or in other words, you cannot solve this problem by looking at a local segment of this graph. I found this monstrosity in trying to prove that it could not exist. This is probably a metaphor for something. Also what the fuck how is this provable now?
Anyway, here's how you actually prove the lemma. Remember the formula (x-y)(x+y+1) = p(A-B)? No? Ok. Well it was there. Also x^2 + x + k = pA. Anyway, no I'm not typing this all why would you ask that. Here's the photographed version:
The point is that epsilon chosen as here connects A and B, which are the two neighbors of p. So not only are the two neighbors of the largest prime fixed, but they connect as well. And that proves the lemma because you can now proceed by induction -- not over nodes in the given set of circles, which is what I tried, but over all possible sets by size -- if the lemma is true for sets of primes of size 4, well take a set of 5 primes, delete the largest node, connect its two neighbors, and you get a set of size 4 with otherwise identical connections. Base case is n=3 where there is only one possible circle. QED. My arm hurts.
I came close to this, too; I tried something with epsilon before, but I defined it as A-B rather than x-A, and then nothing works, and then I never went there again bc it didn't seem useful.
Author
Topic: The Necro Wars (Read 410460 times)