Each question carries 10 marks, but the questions are roughly ordered from easy to hard.
1. Find the exact value of \(\frac{(10^{100}-1)!2\cdot H(10^{100})}{(10^{100}!)^{10^{100}}}\). n!2 is from the Torian, so n!2 = \(\prod^{n}_{i=1} i!\)
2. We define the following variant on the block subsequence theorem.
Suppose we have a string x1, x2, ... made of an alphabet of k letters, such that no block of letters xi, ..., xdi is a substring of any later block xj, ..., xdj for some given d. Call n(k,d) the length of the longest sequence.
Prove n(2,d) > d3, assuming its existence.
3. Find the highest power of 9 that divides \(10^{9^{1000000}}-1\)
4. Find which number is the largest: \(\text{expostfacto}(9)\downarrow^{4}3\) or \(\text{expostfacto}(9\downarrow^{4}3)\).
Answer:
\(\text{expostfacto}(9\downarrow^{4}3)\) is the largest.
Solution:
Lemma 1. \(2\uparrow\uparrow n < \text{expostfacto}(n) < 2[3](2n-4)\) for \(n≥4\)
First inequality by induction:
Base case: \(\text{expostfacto}(4) = 4^{362880} > 2\uparrow\uparrow 4\)
\(\text{expostfacto}(n) = n^{\text{expostfacto}(n-1)!} > n^{\text{expostfacto}(n-1)} > 2^{\text{expostfacto}(n-1)} > 2^{2\uparrow\uparrow (n-1)} = 2\uparrow\uparrow n\)
Second inequality by induction:
Base case: \(\text{expostfacto}(3) = 9 < 256 = 2[3][3] = 2[3]2\)
\(\text{expostfacto}(n) > n\) for \(n≥4\) by the first inequality.
\(\text{expostfacto}(n)^{\text{expostfacto}(n)} > \text{expostfacto}(n)!\)
\((\text{expostfacto}(n)^{\text{expostfacto}(n)})^{(\text{expostfacto}(n)^{\text{expostfacto}(n)})} > n^{\text{expostfacto}(n)!} = \text{expostfacto}(n+1)\)
Lemma 2. \(a \uparrow\uparrow b < a \downarrow^{3} b < a[3]2b\) for \(a,b≥2\)
First inequality by induction:
\(a \downarrow^{3} 2 = a \downarrow^{2} a = a^{a^{a-1}} > a \uparrow\uparrow 2\)
\(a \downarrow^{3} b = (a \downarrow^{3} (b-1)) \downarrow^{2} a > (a \uparrow\uparrow (b-1))^{a \uparrow\uparrow (b-1)^{a}} > (a \uparrow\uparrow (b-1))^{a \uparrow\uparrow (b-1)} > a^{a \uparrow\uparrow (b-1)} = a \uparrow\uparrow b\)
Second inequality by induction:
\(a \downarrow^{3} 2 = a \downarrow^{2} a = a^{a^{a-1}} < a^{a^{a+1}} = a[3]2 < a[3]4\)
\(a \downarrow^{3} b < (a \downarrow^{3} (b-1))\uparrow\uparrow3 < (a \downarrow^{3} (b-1))^{(a \downarrow^{3} (b-1))^{(a \downarrow^{3} (b-1)+1)}}\)
\(< (a[3]2(b-2))^{(a[3]2(b-2))^{(a[3]2(b-2)+1)}} = a[3]2(b-1) < a[3]2b\)
Proof.
\(\text{expostfacto}(9\downarrow^{4}3) = \text{expostfacto}((9\downarrow^{4}2)\downarrow^{3}9) = \text{expostfacto}((9\downarrow^{3}9)\downarrow^{3}9)\) \(> \text{expostfacto}((9 \uparrow\uparrow 9) \uparrow\uparrow 9) < \text{expostfacto}(9 \uparrow\uparrow 17) > 2\uparrow\uparrow9\uparrow\uparrow17\)
\(\text{expostfacto}(9) \downarrow^{4}3 < (2[3]14)\downarrow^{4}3 = ((2[3]14)\downarrow^{4}2)\downarrow^{3}(2[3]14) =\) \(((2[3]14)\downarrow^{3}(2[3]14))\downarrow^{3}(2[3]14) <\) \(((2[3]14)[3](2*2[3]14))\downarrow^{3}(2[3]14) <\) \((2[3]14)[3](2*2[3]14)[3](2*2[3]14) = 2[3](4*2[3]14+14) = 2[3]2[3]15 < 2 \uparrow\uparrow 2 \uparrow\uparrow 17\) \(< 2\uparrow\uparrow9\uparrow\uparrow17 < \text{expostfacto}(9\downarrow^{4}3)\)