## FANDOM

10,828 Pages

Okay, the Second Googological Olympiad has officially ended.  Four people sent in solutions, and two sent in solutions to all six problems.  The winner is Wojowu, who scored a stellar 47 out of 50 points. On April 15, a person named January First-of-May sent in solutions; while technically his scores should not count, I don't see a problem with adding his scores to the list.

NameP 1P 2P 3P 4P 5BonusTotal
Wojowu55101010747
Wythagoras55596131
Cloudy17655    10
January First-of-May55    10

Thanks to everyone who participated! I had a lot of fun writing and overseeing the contest.

Solution to Problem #1:

The answer is $$\prod_{i=0}^{n-1} 10[3]i$$, where we take $$10[3]0$$ to be $$10$$. In fact $$10[3]n = 10^{\prod_{i=0}^{n-1} 10[3]i}$$, which we can prove this by induction.

Base case: $$10[3]1 = 10^{10} = 10^{10[3]0}$$.

Inductive step: Assume $$10[3]n = 10^{\prod_{i=0}^{n-1} 10[3]i}$$. Then

$$10[3](n+1) = (10[3]n)^{10[3]n} = (10^{\prod_{i=0}^{n-1} 10[3]i})^{10[3]n} = 10^{(\prod_{i=0}^{n-1} 10[3]i) 10[3]n} = 10^{\prod_{i=0}^n 10[3]i}$$.

Solution to Problem #2:

We use the following inequalities for the pth prime $$p_n$$:

$$n (\log n + \log (\log n) - 1) < p_n < n (\log n + \log (\log n))$$ for $$n \ge 6$$.

So if we let $$N$$ be the googolplexth prime,

$$N > 10^{10^{100}}(\log(10^{10^{100}}) + \log(\log(10^{10^{100}})) - 1) > 10^{10^{100}}(\log(10^{10^{100}}) + 100 - 1)\\ > 10^{10^{100}}10^{100}\log 10 > 10^{10^{100}}10^{100}(2.302585092994)$$

$$N < 10^{10^{100}}(\log(10^{10^{100}}) + \log(\log(10^{10^{100}}))) < 10^{10^{100}}(\log(10^{10^{100}}) + \log(10^{101}))\\ < 10^{10^{100}}(10^{100}\log(10) + 300) < 10^{10^{100}}10^{100}(2.302585092995 + .000000000001)$$

Since multiplying a number by $$10^{10^{100}}10^{100}$$ does not change its digits, the first 10 digits of $$N$$ are $$2302585092$$.

Solution to Problem #3:

Lower bound:

Since the function $$x \log x$$ is convex (one can check that the second derivative is $$\frac{1}{x}$$, which is positive for $$x > 0$$), the integral from $$1$$ to $$n$$ will be less than its approximation using the trapezoidal rule, so we have

$$\int_1^n x \log x \, dx < \sum_{i=1}^{n-1} \frac{i \log i + (i+1)\log(i+1)}{2}$$

Therefore

$$\log H(n) = \sum_{i=1}^n i \log i > \sum_{i=1}^n i \log i - \sum_{i=1}^{n-1} \frac{i \log i + (i+1)\log(i+1)}{2} + \int_1^n x \log x \, dx\\ = \sum_{i=1}^n i \log i - (\sum_{i=1}^{n-1} i \log i + \frac{n \log n}{2}) + (\frac{x^2 \log x}{2} - \frac{x^2}{4})_{x=1}^n\\ = \frac{n \log n}{2} + \frac{n^2 \log n}{2} - \frac{n^2}{4} + \frac{1}{4}$$

$$H(n) > e^{\frac{n^2 \log n + n \log n}{2} - \frac{n^2-1}{4}} = \frac{n^{\frac{n^2+n}{2}}}{e^{\frac{n^2-1}{4}}}$$.

Upper bound:

We can write

$$H(n) = (1 - \frac{1}{2})^1 (1 - \frac{1}{3})^3 \ldots (1 - \frac{1}{n})^{\frac{n(n-1)}{2}} n^{\frac{n(n+1)}{2}}$$

which we can verify by induction.

Base case: $$H(1) = 1$$

Inductive step: Assume $$H(n) = (\prod_{i=2}^n (1 - \frac{1}{i})^{\frac{i(i-1)}{2}}) n^{\frac{n(n+1)}{2}}$$.

$$H(n+1) = H(n)(n+1)^{n+1} = (\prod_{i=2}^n (1 - \frac{1}{i})^{\frac{i(i-1)}{2}}) n^{\frac{n(n+1)}{2}} (n+1)^{n+1}\\ = (\prod_{i=2}^n (1 - \frac{1}{i})^{\frac{i(i-1)}{2}}) (1 - \frac{1}{n+1})^{\frac{n(n+1)}{2}} (n+1)^{\frac{n(n+1)}{2}} (n+1)^{n+1}\\ = (\prod_{i=2}^{n+1} (1 - \frac{1}{i})^{\frac{i(i-1)}{2}}) (n+1)^{\frac{(n+1)(n+2)}{2}}$$.

We use the inequality $$(1 - \frac{1}{i})^i < \frac{1}{e}$$*. Then

$$H(n) = (\prod_{i=2}^n (1 - \frac{1}{i})^{\frac{i(i-1)}{2}}) n^{\frac{n(n+1)}{2}} \\ < (\prod_{i=2}^n e^{-\frac{i-1}{2}})n^{\frac{n(n+1)}{2}} = e^{-\frac{n^2-n}{2}}n^{\frac{n(n+1)}{2}} = \frac{n^{\frac{n(n+1)}{2}}}{e^{\frac{n^2-n}{2}}}$$

*to verify the inequality $$(1 - \frac{1}{i})^i < \frac{1}{e}$$, observe that $$\lim_{i \to \infty} (1 - \frac{1}{i})^i = \frac{1}{e}$$, and then observe that $$(1 - \frac{1}{i})^i$$ is increasing (the first derivative is positive).