The First International Googological Olympiad has ended. Here will follow the results, remarks and solutions. In the First International Googological Olympiad (FIGO for short) have participated four contestants, of which three have sent all problems to me. I consider the olympiad as a succes, given the fact that all contestants responded very positive. I've learned a lot of this olympiad as well (see the acknowledgements section), and I've enjoyed organizing it.
Results[]
Congratulations to all contestants. Fish is the winner of the contest.
| Contestant | Attempt | P1 | P2 | P3 | P4 | Penalty | Total |
|---|---|---|---|---|---|---|---|
| Fish | #2 | 7.0 | 7.0 | 7.0 | 7.0 | -1.0 | 27.0 |
| #1 | 7.0 | 7.0 | 7.0 | 3.0 | 0.0 | ||
| LittlePeng9 | 7.0 | 7.0 | 4.0 | 7.0 | 0.0 | 25.0 | |
| Deedlit11 | #2 | 7.0 | 7.0 | 4.0 | 7.0 | -2.0 | 23.0 |
| #1 | 7.0 | 3.0 | 4.0 | 7.0 | 0.0 | ||
| Vel! | 7.0 | 0.0* | 0.0* | 0.0* | 0.0 | 7.0 |
*These scores are 0.0 because I haven't received these problems.
Acknowledgements[]
I also want to thank LittlePeng9 for correcting problems 2 and 4.
Further, I want to thank LittlePeng9 for correcting the solution of problem 2.
And I want to thank Fish for correcting the solution of problem 1.
Problems[]
Problem 1. Find a number \(n\) such that \(\frac{\sigma(n)}{n}\) is larger than 1,000. (\(\sigma(n)\) is the sum of the divisors of \(n\)).
Problem 2. Proof that \(SCG(2n)\) is even for every \(n \in \mathbb N\). (empty graph is counted)
Problem 3. Determine all quadruples of numbers (a,b,c,d) such that
\[a \rightarrow b \rightarrow c \rightarrow d > \{a,b,c,d\}\]
Problem 4. A function f is k-exponential iff f(n) = E(Θ(n))#k, using Hyper-E. For example, a function f is 3-exponential iff \(f(n) = 2^{2^{2^{\Theta(n)}}}\). Find, for every \(k \in \mathbb N\), a function f such that \(f^n(n)\) is a k-exponential function. Give the function in terms of: addition, multiplication, exponentation, factorial, logarithm, iterated logarithm, tetration, subtraction and division.
Solution to problem 1[]
Problem 1. Find a number \(n\) such that \(\frac{\sigma(n)}{n}\) is larger than 1,000. (\(\sigma(n)\) is the sum of the divisors of \(n\)).
Solution. We'll show that \(N = \text{ceil}(e^{1000})!\) statistifies. (! is the factorial function).
\(N\) is clearly divisible by all numbers up to \(\text{ceil}(e^{1000})\).Therefore \(N\) is divisible by all numbers in the form \(\frac{N}{k}\), with \(1 \leq k \leq \text{ceil}(e^{1000})\). Therefore:
\[\frac{\sigma(N)}{N} > \sum^{\text{ceil}(e^{1000})}_{k=1} \frac{1}{k} > ln(\text{ceil}(e^{1000})) > ln(e^{1000}) = 1000\]
Conclusion: \(N = \text{ceil}(e^{1000})!\) statistifies the given condition. q.e.d.
Remarks to problem 1[]
We find that \(N < 10^{10^{446.94}}\).
Using a result of Robin (1984) we can also find a lower bound:
\[\frac{\sigma(n)}{n} < e^{\gamma} \text{ln}(\text{ln}(n)) + \frac{0.6483}{\text{ln}(\text{ln}(n))}\]
Using this inequality and above result, we can prove that the smallest solution \(S\) statistifies:
\[10^{10^{243.47}} < S < 10^{10^{446.94}}\]
Solution to problem 2[]
Problem 2. Proof that \(SCG(2n)\) is even for every \(n \in \mathbb N\). (empty graph is counted)
Solution. We'll show that the sequence consists of two parts: one part with and one part without edges. Suppose \(S\) is the longest sequence of graphs and it has a graph with edges after a graph with no edges. Call \(G\) the first graph without edges, \(v\) the number of vertices of this graph and \(H\) the first graph with edges after it. \(G\) or earlier graphs are by definition not homeomorphically embeddable into \(H\) . However, any graph with edges is not homeomorphically embeddable into a graph without edges. Therefore we can have \(H\) at the place of \(G\) and then a graph with \(v+1\) vertices, then \(G\), and then the original sequence with \(H\) removed. This sequence is, however, longer. Contradiction.
Therefore the sequence consisting out of one part with and one part without edges is the longest. Let \(G_n\) be the last graph with an edge for \(SCG(2i)\). It is optimal when the first graph without edges has as many vertices as possible, in this case \(n+2i+1\). Further, it is optimal when each graph has only one vertex less than the graph before it. Therefore, this results in a sequence of \(n+2i+2\) graphs without edges, and therefore a total of \(2n+2i+2\) graphs. Because this is divisible by two, the proof is complete. q.e.d.
Solution to problem 3[]
Problem 3. Determine all quadruples of numbers (a,b,c,d) such that
\[a \rightarrow b \rightarrow c \rightarrow d > \{a,b,c,d\}\]
Solution. When a=b=2, we know that both the chained arrow expression and the BEAF expression are equal to 4. When a=1, both expressions are equal to 1. When b=1, both expressions are equal to a. When d=1, both expressions are equal to \(a \uparrow^c b\). Therefore, in these cases, there is no strict inequality.
Then, when a≥3, b≥2, c≥1 and d≥2. We'll use and prove a variant of Bird's Proof. We want to proof that :
\[\forall a\geq3, b\geq2, c\geq1, d\geq2: \{a,b,c,d\} \geq a \rightarrow b \rightarrow c \rightarrow d\]
First, some lemmas:
L1. a^b ≥ 3^b ≥ b+2. for a≥3,b≥2. Proof: By Bernoulli's inequality, (2+1)^b ≥ 2b+1 ≥ b+3 > b+2.
L2. \(a\geq3,b\geq2: a\uparrow^b a \geq a^b+1 > a^b\). Proof by induction. Base case: b=2: We know that \(a \uparrow^2 a > a^a > a^2\). Step: \(a \uparrow^b a > a \uparrow^{b-1} (a \uparrow^{b-1} a) > a \uparrow^{b-1} 2a\). Now, by the Knuth Arrow Theorem, \(a \uparrow^{b-1} 2a > (a \uparrow^{b-1} a) \uparrow^{b-1} a\). By the induction hypothesis is this larger than \((a^{b-1}) \uparrow^{b-1} a > (a^{b-1})^{(a^{b-1})} \geq (a^{b-1})^3 > a^{3b-3} \geq a^{b+1} > a^b\). Because we work with integers, this also shows that \(a\uparrow^b a \geq a^b+1\). This completes the proof.
Now, the main proof. We induction on \(c\).
Base. Now, we prove that the inequality holds for a≥3, b≥2, c=1 and d≥2 by induction. Chained arrow returns \(a^b\). When b=2, the inequality states \(\{a,2,1,d\} \geq \{a,2,1,2\} = \{a,a,a\} > a^2\), which is correct (because a≥3).
For the induction step: \(\{a,b+1,1,d\} \geq \{a,b+1,1,2\} = \{a,a,\{a,b,1,2\}\} >^{IH} \{a,a,a^b\} \geq \{a,a,b+3\} > a^{b+1} \). Second inequality follows form the IH, third fom L1, fourth form L2. This completes the induction.
Step. Now, we prove that if it is valid for all (a,b,c,d) if it is true for (a,b,c-1,d) which follows form the induction hypothesis.
\[a \rightarrow b \rightarrow c \rightarrow d = a \rightarrow b \rightarrow (a \rightarrow b \rightarrow (c-1) \rightarrow d) \rightarrow (d-1) \]
\[< \{a,b,\{a,b,c-1,d\},d-1\} < \{a,a^{b-1},\{a,a^{b-1},c-1,d\},d-1\} = \{a,a^{b-1},c-1,d\}\]
\[\leq \{a,\{a,b-1,c,d\},c-1,d\} = \{a,b,c,d\}\]
First inequality follows form the IH, second fom L1, third from the properties of BEAF. This completes the induction.
The only case that remains is a=2, b≥3, c≥1, d≥2. Here, BEAF returns 4 as a result of Cookiefonster, while the chained arrow notation returns a number larger than or equal to \(2^3=8\). Therefore all solutions have the form of:
\[(a,b,c,d) \text{ with } a=2, b\geq3, c\geq1, d\geq2\]
This solves the problem, q.e.d.
Solution to problem 4[]
Problem 4. A function f is k-exponential iff f(n) = E(Θ(n))#k, using Hyper-E. For example, a function f is 3-exponential iff \(f(n) = 2^{2^{2^{\Theta(n)}}}\). Find, for every \(k \in \mathbb N\), a function f such that \(f^n(n)\) (function iteration) is a k-exponential function. Give the function in terms of: addition, multiplication, exponentation, factorial, logarithm, iterated logarithm, tetration, subtraction and division.
Solution. The following set of functions statistifies the problem:
\[f(n) = \text{exp}^{k-2}(\text{ln}^{k-2}(n)^2)\]
Here the exponent is function iteration, and taking inverse ufncitons when it is negative.
When k=1, the function is equal to 2n. When iterated, this becomes \(2^nn\), which is one-exponential.
Further, when k≥2, we give a proof by induction to \(n\) that \(f^n(r)\) equals \[\text{exp}^{k-2}(\text{ln}^{k-2}(r)^{2^n})\]
For \(n=1\), the base case, it is trivial. The induction step goes as following:
\[f^{n+1}(r) = f(\text{exp}^{k-2}(\text{ln}^{k-2}(r)^{2^n})) = \text{exp}^{k-2}(\text{ln}^{k-2}(\text{exp}^{k-2}(\text{ln}^{k-2}(r)^{2^n}))^2)=\text{exp}^{k-2}((\text{ln}^{k-2}(r)^{2^n})^2)\]
\[= \text{exp}^{k-2}(\text{ln}^{k-2}(r)^{2^{n+1}})\]
We know that \[\text{exp}^{k-2}(\text{ln}^{k-2}(r)^{2^n})\] is k-exponential, because there are k+1 terms in total and the ln factor is to small to affect the topmost exponent. This solves the problem, q.e.d.
Remarks to problem 4[]
Fish originally misread the problem 4 as:
Problem 4.2. A function f is k-exponential iff f(n) = E(Θ(n))#k, using Hyper-E. For example, a function f is 3-exponential iff \(f(n) = 2^{2^{2^{\Theta(n)}}}\). Find, for every \(k \in \mathbb N\), a function f such that \(f^6(n)\) is a k-exponential function. Give the function in terms of: addition, multiplication, exponentation, factorial, logarithm, iterated logarithm, tetration, subtraction and division.
The difference is in \(f^6(n)\) and \(f^n(n)\). He gave a solution using the floor function, but because that one wasn't allowed, he used Fourier series to solve the problem. The following questions were then given:
- Question 1. Is it possible to define f without infinite sum and with only the specified functions?
- Question 2. Is it possible to define f which is a monotonically increasing function? If we can find such function, we can call it k/6-exponential function, and we could possibly define k-exponential function for all k∈Q.
- Question 3. If (2) is yes, is it possible to express such function in closed form?
He asked me to give these to you at the end of the olympiad.
What about next?[]
Anyone willing to organize the olympiad next year? Or next month?
It takes about eight or ten hours to prepare and finish, plus about one hour per contestant to check the solutions.