British Algorithmic Olympiad 2023 Solutions
Question 1. High Rise
A
For this problem we are given a recursive relation \begin{equation} T(n) = \bigg\lceil \log_{10}(n^4)\bigg\rceil+T(n-1)+\bigg\lceil\frac{7}{20000}T(n-2)\bigg\rceil \end{equation} The evaluation of $T(ef)$ for buildings with an EDC of 23 could use simple recursion for small values of $f$. But we are asked to write downthe value at the theoretical 498th floors.Without memorization such a task is not possible for someone who is not working for Google!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | from math import ceil, log T_ = [2,2]+[None]*23*499 def T(n): if T_[n-1]==None: # remember T_ is zero offset temp = T(n-1) + ceil(7*T(n-2)/2000) + ceil(4*log(n,10)) T_[n-1] = temp return temp else: return T_[n-1] e = 23 TEDC=[] for f in range(1,499): TEDC.append(T(e*f)) print(f'For an EDC of 23, T(ef)={TEDC[32]} for floor 33') print(f'For an EDC of 23, T(ef)={TEDC[497]} for floor 498') |
None. The code only uses recursion if the value required has not been calculated yet (see if statement on line 6). Running time is 26.8 ms
± 5.86 ms per loop. The value for the 33rd floor is 35883 while the value for the 498th floor is 588343190381954253975.
B
C
D
TEDC. We also have the closed form for the total number of wires on the $f$th floor. We are asked to calculate
\begin{equation}
S_T(F) = \sum_{f=1}^F S(f) \label{TS}
\end{equation}
the total number of support beams for a building with $F$ floors and
\begin{equation}
W_T(F) = \sum_{f=1}^F [T(ef)+E(f)] \label{TW}
\end{equation}
We can speed up the calculation for $S_T(F)$ by writing down a closed form solution:
\begin{align*}
S_T(F) & =\sum_{f=1}^F S(f) \\
& = \sum_{f=1}^F \left(2^{f+1} - 3\right) \\
& = 2 \sum_{f=1}^F 2^f - 3F \\
& = 4 (2^F -1) -3 F & \text{use formula given for geometric progression}
\end{align*}
You can check that as in the Example Run if $F=6$, $S_T(6)=4(2^6-1)-18=4(64-1)-18=252-18=234$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | from math import log10 from bao_2023_1A import TEDC # import T(23f) array to avoid recalculation from tabulate import tabulate def ST(F): return 4*(2**F-1) - 3*F def E(f): return f*f + f*(f+1)*(2**f - 1.5) def first_four(n): digits = int(log10(n)) return int(n // (10**(digits-3))) WT_ = [None]*60 # initialize array for total number of wires def WT(F): if F==1: WT_[0] = TEDC[0] + E(1) # TEDC[0] is T(23) return WT_[0] else: if WT_[F-2]==None: # F-1 corresponds to F-2 for array indexation return WT(F-1) + TEDC[F-1] + E(F) else: return WT_[F-2] + TEDC[F-1] + E(F) table = [] for F in range(1,61): table.append([F,ST(F),first_four(WT(F))]) print(tabulate(table, headers=["Number of floors" , "Number of beams" , "Number of wires (4 s.d.)"],tablefmt="fancy_grid")) |
| Number of floors | Number of beams | Number of wires (4 s.d.) |
|---|---|---|
| 1 | 1 | 1239 |
| 2 | 6 | 4409 |
| 3 | 19 | 1046 |
| 4 | 48 | 2116 |
| 5 | 109 | 4101 |
| 6 | 234 | 8120 |
| 7 | 487 | 1694 |
| 8 | 996 | 3740 |
| 9 | 2017 | 8592 |
| 10 | 4062 | 2014 |
| 11 | 8155 | 4751 |
| 12 | 16344 | 1118 |
| 13 | 32725 | 2613 |
| 14 | 65490 | 6059 |
| 15 | 131023 | 1392 |
| 16 | 262092 | 3176 |
| 17 | 524233 | 7187 |
| 18 | 1048518 | 1615 |
| 19 | 2097091 | 3607 |
| 20 | 4194240 | 8011 |
| 21 | 8388541 | 1770 |
| 22 | 16777146 | 3892 |
| 23 | 33554359 | 8522 |
| 24 | 67108788 | 1858 |
| 25 | 134217649 | 4039 |
| 26 | 268435374 | 8751 |
| 27 | 536870827 | 1889 |
| 28 | 1073741736 | 4069 |
| 29 | 2147483557 | 8740 |
| 30 | 4294967202 | 1872 |
| Number of floors | Number of beams | Number of wires (4 s.d.) |
|---|---|---|
| 31 | 8589934495 | 4002 |
| 32 | 17179869084 | 8538 |
| 33 | 34359738265 | 1817 |
| 34 | 68719476630 | 3862 |
| 35 | 137438953363 | 8191 |
| 36 | 274877906832 | 1734 |
| 37 | 549755813773 | 3666 |
| 38 | 1099511627658 | 7740 |
| 39 | 2199023255431 | 1631 |
| 40 | 4398046510980 | 3434 |
| 41 | 8796093022081 | 7221 |
| 42 | 17592186044286 | 1516 |
| 43 | 35184372088699 | 3180 |
| 44 | 70368744177528 | 6663 |
| 45 | 140737488355189 | 1394 |
| 46 | 281474976710514 | 2916 |
| 47 | 562949953421167 | 6091 |
| 48 | 1125899906842476 | 1271 |
| 49 | 2251799813685097 | 2650 |
| 50 | 4503599627370342 | 5521 |
| 51 | 9007199254740835 | 1149 |
| 52 | 18014398509481824 | 2390 |
| 53 | 36028797018963805 | 4968 |
| 54 | 72057594037927770 | 1031 |
| 55 | 144115188075855703 | 2141 |
| 56 | 288230376151711572 | 4441 |
| 57 | 576460752303423313 | 9206 |
| 58 | 1152921504606846798 | 1906 |
| 59 | 2305843009213693771 | 3947 |
| 60 | 4611686018427387720 | 8167 |
E
F
During the exam we are under time pressure so our routine to determine whether a number $n$ is a prime might search if it is divisible by all integers $k=2,\ldots,n-1$. For future reference this is a bit inefficient; we know that any integer has the property $(m+1)^2 \geq n \geq m^2$ (for example $12^2 > 134 > 11^2$). If you find that n is the square of an integer then you don't need to search any further. But now lets assume this is not the case and you have to continue your search. If $n$ is not a prime we can write it as the product $pq$; if both $p$ and $q$ are greater than $m$ then their product must be at least equal to $(m+1)^2$. But this contradicts our assumption that $n < (m+1)^2$; so one of the factors of $n$ will be always less or equal to $m$ and thats how far we need to keep looking.
The code used to determine $r$ and to find the number of p-constructed floors for $f=2,\ldots,101$ is shown below:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | from math import sqrt import matplotlib.pyplot as plt def find_r(Nmax=1000): r = 7 while 2**r % 125 != 1 and r<Nmax: r = r + 1 if r >= Nmax: print("Failed") else: print(r) find_r() def is_prime(n): m = int(sqrt(n)) if n==m*m: return False k = 2 while k <= m: if n % k == 0: return False k = k + 1 return True n = 0 table = [] for f in range(2,101 + 1): x = (2**(f+1)-3) % 1000 # last three digits if is_prime(x): n = n + 1 table.append([n, x, 'red', f]) else: table.append([n, x, 'blue' , f]) print(f'There are {n} primes in each batch.') plt.bar([x[3] for x in table],[x[1] for x in table], color=[x[2] for x in table]) plt.ylabel(r'$S(f)$ last three digits') plt.xlabel(r'$f$') plt.show() |
The code takes 406 ms ± 382 ms.
Question 2. PET Scan
A(i)
To complete this question it helps to look at the following diagram:
When the tracer is acivated it is at a distance $d_{20}$ from camera 20 and a distance $d_4$ from camera $4$. From the geometry of the PET scanner it is clear that $d_4+d_{20}=D$ the inner diameter. We know that one of the detectors received one photon after $1\times 10^{-9} \; \mathrm{s}$; during this time the photon traveled a distance $3 \times 10^8 \; \mathrm{m/s} \times 1\times 10^{-9} \; \mathrm{s}$ or $0.3 \; \mathrm{m}$. The other detector received one photon after $2\times 10^{-9} \; \mathrm{s}$; during this time the photon traveled a distance $3 \times 10^8 \; \mathrm{m/s} \times 2\times 10^{-9} \; \mathrm{s}$ or $0.6 \; \mathrm{m}$. Therefore the inner diameter is equal to $D = 0.3 + 0.6 = 0.9 \; \mathrm{m} = 90 \; \mathrm{cm}$.
A(ii)
There are 32 cameras that cover a 360 degree angle ; each camera covers an angle of $11.25$ degrees. Each camera has three detectors A,B,C spaced at regular intervals. Therefore for camera 1 detector A is located at an angle $\frac{11.25}{4}^{\circ}$, detector B at an angle $\frac{11.25}{2}^{\circ}$ and detector C at an angle $\frac{3\cdot 11.25}{4}^{\circ}$. In general the angular coordinates of each detector for the $n$th camera are, \begin{align} \theta_A(n)& = 11.25 \left((n-1)+ \frac{1}{4}\right) \\ \theta_B(n)& = 11.25 \left((n-1)+ \frac{1}{2}\right) \\ \theta_C(n)& = 11.25 \left((n-1)+ \frac{3}{4}\right) \\ \end{align} When we are given an input in the form of (camera,detector), using the polar coordinate framework of the question we can draw the following schematic:
In this problem we have defined the angle as clockwise from the positive $y$-axis; one small complication introduced by this definition is that we cannot apply the standard polar coordinate conversion
$x=r\cos\theta, y = r \sin\theta$ (see diagram below). Both the $\cos$ and $\sin$ functions are defined for
Unfortunately by using clockwise angles we have reversed the sign of the standard angles. $\theta$ is really $-\theta$; so $\phi = 90^\circ - \theta$. We can now determine the $(x,y)$
coordinates of a detector using,
\begin{align}
x & = R \cos(90^\circ - \theta) = R \sin\theta & \cos(A-B)=\cos A \cos B + \sin A \sin B \label{xcoord} \\
y & = R \sin(90^\circ - \theta) = R \cos\theta & \sin(A-B)=\sin A \cos B - \cos A \sin B \label{ycoord}
\end{align}
where $R=D/2$. Note that the inverse (getting the detector's angle from its $x$ and $y$ coordinates) is not as straightforward; given $x,y$ we can always use the inverse of the tangent function $\atan (y/x)$. However $y=2,x=1$ give the same result as $y=-2,x=-1$ although the two points are in different quadrants.
The math library in Python has the atan2 function which takes two arguments $y,x$. Using standard convention for quadrant angles
it returns the angle in radians for values ranging from $-\pi$ to $\pi$. This requires a modification for $x < 0,y > 0$ (second quadrant); atan2 returns an angle greater than $90^\circ$. So if
we use the conversion $\theta=90^\circ - \phi$ we get a negative number. What we want (only for this case) is $360^\circ + 90^\circ - \phi$.
Given the angles $\theta_N, \theta_M$ for detectors $N,M$ we can use ($\ref{xcoord}$), ($\ref{ycoord}$) to calculate $(x_N,y_N)$, $(x_M,y_M)$. The length of the chord $NM$ is, \begin{equation} d_{NM}^2 = \sqrt{(x_N-x_M)^2+(y_N-y_M)^2} \end{equation} The following diagram can help provide clues as to how we can determine the coordinates of the tracer:
We want to determine the position of the tracer on the chord $NM$; we will use a variable $t$ to indicate its proximity to camera $N$. $t=1$ means that the tracer location is point $N$; $t=0$ means that the tracer location is point $M$; in all other cases $0 < t < 1$. It takes $t_N = \frac{d_{TN}}{c}$ seconds for one photon from the tracer to reach detector $N$ and $t_M = \frac{d_{TM}}{c}$ for another photon (moving in the opposite direction) to reach detector $M$. Therefore, \begin{equation} t_N - t_M = \frac{d_{TN} - d_{TM}}{c} \Rightarrow d_{TN} - d_{TM} = c(t_N - t_M) \end{equation} Since $d_{TN} + d_{TM}=d_{NM}$ we have a system of two equations from which we can derive, \begin{align} d_{TN} & = \frac{1}{2} \left(d_{NM} + c (t_N - t_M) \right) \\ d_{TM} & = \frac{1}{2} \left(d_{NM} - c (t_N - t_M) \right) \\ \end{align} As defined $t=1$ when $d_{TN}=0$; this means that we can write $t$ as, \begin{equation} t = \frac{d_{TM}}{d_{NM}} \end{equation} since when $d_{TN}=0$, $d_{TM}=d_{NM}$.
We can use $t$ to derive the $x$ and $y$ coordinates of $T$. To see how this works consider the similar triangles $MM'N$ and $TT'N$; we know that for two similar triangles, \begin{equation} \frac{\abs{TN}}{\abs{NM}} = \frac{\abs{T'N}}{\abs{M'N}} \label{int_one} \end{equation} where $\abs{TN}$ denotes the length of segment $TN$. Since $\abs{TN}=d_{TN}$ and $\abs{NM}=d_{NM}$ we have, \begin{equation} \frac{\abs{TN}}{\abs{NM}} = \frac{d_{TN}}{d_{NM}} = \frac{d_{NM} - d_{TM}}{d_{NM}} = 1-t \end{equation} Note that $\abs{T'N}=y_N-y_T$ and $\abs{M'N}=y_N - y_M$. So we can rewrite ($\ref{int_one}$) as, \begin{align} \frac{y_N-y_T}{y_N - y_M} & = 1-t \nonumber \\ y_N - y_T & = (1-t) (y_N - y_M) \nonumber \\ y_T & = y_N - (1-t) y_N + (1-t) y_M \nonumber \\ y_T & = t y_N + (1-t) y_M \end{align} The same procedure can be used for similar triangles $MT''T$ and $MM'N$ to show that, \begin{equation} x_T = t x_N + (1-t) x_M \end{equation} The radial coordinate of $T$ is, \begin{equation} r = \sqrt{x_T^2 + y_T^2} \end{equation}
The following code was used to derive the tracer coordinates:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | from math import sqrt, cos, sin, atan2, pi N = 32 # number of cameras ca = 360./N # angle covered by each camera def angle(dte): if dte[1]=='A': return ca*((dte[0]-1)+.25) elif dte[1]=='B': return ca*((dte[0]-1)+.5) elif dte[1]=='C': return ca*((dte[0]-1)+.75) else: return "Detector letter can only be A, B or C" def invert(x, y, tol = 1e-10): phi = 180.*atan2(y,x)/pi # 'normal' angle in the correct quadrant in degrees if x<0 and y>0: # in this quadrant 90 - phi does not work as phi is +ve and greater than 90 return 360 + 90 - phi else: return 90 - phi def coords( # each column contains info for the same camera t1 , t2 , # time lapse in nanoseconds dte1, dte2, # dte=[#camera , 'detector'] [integer , string] R = 45, # derived in 2(i) tol = 1e-10 # if abs(x) or abs(y) is below this level it is treated as zero ): theta1 = pi*angle(dte1)/180 theta2 = pi*angle(dte2)/180 y1, x1, y2, x2 = R * cos(theta1) , R * sin(theta1) , R * cos(theta2) , R * sin(theta2) d12 = sqrt((y2-y1)**2 + (x2-x1)**2) d2 = .5 * (d12 - 30 * (t1 - t2)) t = d2/d12 y, x = t * y1 + (1-t) * y2 , t * x1 + (1-t) * x2 r = sqrt(y*y + x*x) return round(invert(x,y),2) , round(r,2) |
B
The minimum distance travelled by any singular photon is half the length of the chord that joins two adjacent detectors. This is given by, \begin{equation} d_{min}= R \cos\left(\frac{1}{2}\left(180^\circ - \frac{11.25}{4}\right)\right) = 45 \; \mathrm{cm} \cos 88.59375^\circ = 1.1 \; \mathrm{cm} \end{equation} using 1 decimal place precision.
C
We start with the PET scanner with zero sources:
There is a single face and so $S(0)=1$; when we add a new line we are effectively cutting the single existing face in two parts. Since we are only adding a single new face we have, $$ S(1)=S(0)+1=2 $$ as shown below,
When we draw a second line we are now cutting each of the existing 2 faces in two parts (hence we only add 2 more faces). Therefore, $$ S(2)=S(1)+2=4 $$ and,
When we draw the third line we will cross 2 lines to create 3 new faces. We now have, $$ S(3)=S(2)+3=7 $$ and,
What is the maximum number of faces we can cross with the fourth line? At a minimum we can cross a single line,
We can also cross 2 lines,
or 3 lines,
Given that before we only had 3 lines we cannot do any better! Hence, $$ S(4)=S(3)+4=11 $$ We seem to be developing a pattern here; but it is still possible that in the next step the pattern disappears. We want the new line to cross the 4 existing lines. The new line will then cross 5 existing faces creating 5 new faces:
So the recursion still holds and, $$ S(5)=S(4)+5=16 $$ If we assume that $t$ lines have created $S(t)$ faces, then by adding an additional line we can cross a maximum of $t$ lines. By crossing $t$ lines we create $t+1$ new faces. Hence, $$ S(t+1)=S(t)+t+1 $$ For a closed form solution for $S(t)$ generate the following recursive expansion, \begin{align*} S(t) & = S(t-1) + t \\ & = S(t-2) + (t-1) + t \\ & = S(t-3) + (t-2) +(t-1) + t \\ & = S(t-4) + (t-3) + (t-2) +(t-1) + t \\ & = S(t-4) + (t-(4-1)) + (t-2) +(t-1) + t \end{align*} So if we wanted the first term to be $S(1)=S(t-(t-1))$ we would have to write, \begin{align*} S(t) & = S(t-(t-1)) + (t-((t-1)-1)) + \ldots + (t-1) + t \\ & = S(1) + 2 + \ldots + (t-1) + t \\ & = 2+ 2 + \ldots + (t-1) + t \\ & = 1 + 1 + 2 + \ldots + (t-1) + t \\ & = 1 + \frac{t(t+1)}{2} \end{align*} For example, $S(5)=1+(5\times 6)/2=16$.
Question 3. Fractals
A(i)
The standard version of this fractal assumes that once a white triangle has formed it stops subdividing. However in the question, the white triangle keeps subdividing; the difference now is that the new triangles formed are counted as white even if they point up. Therefore, if the number of black and white triangles at iteration $n-1$ is $T(n-1)$, the number of triangles at iteration $n$ is, \begin{equation} T(n)=4T(n-1) \end{equation} Since $T(1)=1$ it is easy to show that $T(n)=4^{n-1}$.
As instructed, we denote the number of black (resp. white) triangles at iteration $n-1$ as $B(n-1)$ (resp. $W(n-1)$). Each black triangle generates 3 new black triangles after each subdivision. Since the white triangles do not generate any new black triangles we can write the following recursive relation for $B(n)$: \begin{equation} B(n)=3B(n-1) \end{equation} Starting with $B(1)=1$ it is easy to show that $B(n)=3^{n-1}$.
A(ii)
Here we are instructed to write a recursive relation for $W(n)$. We know that after subdivision one black triangle generates a single white triangle, while one white triangle generates four white triangles. So, \begin{equation} W(n)=B(n-1)+4W(n-1)= 3^{n-2} + +4W(n-1) \label{version1} \end{equation} Another way of writing this is to note that, \begin{equation} T(n-1)=B(n-1)+W(n-1)= 4^{n-2} \label{fact} \end{equation} Therefore we can rewrite ($\ref{version1}$) as, \begin{align} W(n) & =B(n-1)+W(n-1)+3W(n-1) \nonumber \\ & = 4^{n-2} +3W(n-1) & \text{use ($\ref{fact}$)} \end{align}
A(iii)
In order to resolve a recursive equation to a closed form expression we must find a pattern that gives rise to a simple sequence like, for example, a geometric progression. In order to do this lets write down a few lines starting from ($\ref{version1}$): \begin{align} W(n) & =3^{n-2}+4W(n-1) \nonumber \\ & = 3^{n-2}+4 \left( 3^{n-3} + 4 W(n-2) \right) & \text{apply ($\ref{version1}$)}\nonumber \\ & = 3^{n-2} + 4 \cdot 3^{n-3} + 4^2 \left( 3^{n-4} + 4 W(n-3) \right) & \text{apply ($\ref{version1}$)}\nonumber \\ & = 3^{n-2} + 4 \cdot 3^{n-3} + 4^2 3^{n-4} + 4^3 W(n-3) \nonumber \\ & = 3^{n-2} \left( 1 + \frac{4}{3} + \left(\frac{4}{3}\right)^2\right) + 4^3 W(n-3) \end{align} At this stage we can come up with a recipe: first the expansion can go as far as the last term containing $W(1)=0$. If we want to be pedantic we can show that in the same way that $W(n-3)$ has a $4^3$ factor, $W(1)=W(n-(n-1))$ will have a $4^{n-1}$ factor. But since $W(1)=0$ this does not matter. Second, no matter how many additional lines we write there will always be a factor of $3^{n-2}$ applied to the expression in the brackets, which is a geometric progression. Finally, notice that we have $W(n-3)$ and a progression, $$ 1 + \frac{4}{3} + \left(\frac{4}{3}\right)^2 $$ i.e. the largest power is $3-1=2$; if the $W$ term is $W(1)=W(n-(n-1))$ then we must have, $$ 1 + \frac{4}{3} + \left(\frac{4}{3}\right)^2 + \ldots + \left(\frac{4}{3}\right)^{(n-1)-1} $$ The closed form solution is, \begin{equation} W(n)=3^{n-2} \sum_{k=0}^{n-2} \left(\frac{4}{3}\right)^k \label{closed1} \end{equation} The formula for a geometric progression is, $$ \sum_{k=0}^{n} r^k = \frac{1-r^{n+1}}{1-r} $$ and so we can rewrite ($\ref{closed1}$) as, \begin{align} W(n) & =3^{n-2} \frac{1-\left(\frac{4}{3}\right)^{n-2+1}}{1-\frac{4}{3}} \nonumber \\ & = 3^{n-2}\frac{\frac{3^{n-1}-4^{n-1}}{3^{n-1}}}{\frac{3-4}{3}} \nonumber \\ & = 3^{n-2} \frac{3(3^{n-1}-4^{n-1})}{3^{n-1}(3-4)} \nonumber \\ & = 3^{n-1} \frac{(3^{n-1}-4^{n-1})}{-3^{n-1}} \nonumber \\ & = 4^{n-1} - 3^{n-1} \label{W_n} \end{align}
A(iv)
($\ref{W_n}$) tells me that I wasted a lot of time deriving it! On the $n$th iteration the total number of triangles is $4^{n-1}$; there are also $3^{n-1}$ black triangles. Therefore there should be $4^{n-1}-3^{n-1}$ white triangles.
B
$\def\one{\mathtt{1}}$ $\def\zil{\mathtt{0}}$ The question makes clear that for the binary digit presentation “[w]e are only interested in upwards pointing triangles. ” If we denote a black triangle by $\one$ and a white triangle by $\zil$, the triangular patterns can be derived using the following rules: $\one \oplus \one = \zil$, $\one \oplus \zil = \zil \oplus \one = \one$, $\zil \oplus \zil = \zil$. This is the truth table from a XOR gate.
Since we are effectively constructing Pascal's triangle for the XOR gate it would be helpful if we can use the values from the original Pascal's triangle. These are given by the binomial coefficient $\binom{n}{k}=\frac{n!}{k!(n-k)!}$; for example if $n=3$ and $k=1$, $\binom{3}{1}=3$; but what does a coefficient of 3 mean in binary world?
Well, a coefficient of 3 means $\one \oplus \one \oplus \one$; if we calculate from right to left then we get, $$ \one \oplus \one \oplus \one \rightarrow \one \oplus \zil \rightarrow \one $$ In the instructions to this question we can check that $b(3,1)= \one$ ; in the same way, $b(3,2)=\one$ ($\binom{3}{2}=3$); the other entries ($b(3,0)$ and $b(3,3)$) default to $\one$. The pattern is actually much simpler: as we can see from the last equation XOR generates a periodic series $\one, \zil, \one, \zil, \ldots$. If the binomial coefficient is odd then we get $\one$; if it is even we get $\zil$.
The only issue is that we don't want to have to calculate large factorials and then do divisions just to find whether a binomial coefficient is even or odd! The parity (whether a number is even or odd) of binomial coefficients was first studied by James W. L. Glaisher. There is an ingenious algorithm for establishing the parity of $\binom{n}{k}$ by comparing the binary expression for $n$ with the binary expression for $k$. Under exam time pressure such luxuries are not available! So the code does not use binomial coefficients and instead builds each layer of Sierpinski's triangle using $b(k,i)=b(k-1,i-1) \oplus b(k-1,i)$. Note that the denary value $a(n,k)$ is not really a function of $n$; for $n \neq n'$ , $a(n,k)=a(n',k)$. The best we can do is require that the maximum number for $k$ is $2^{n-1}$. Having computed $b(k,i)$, \begin{equation} a(n,k) = \sum_{i=1}^k 2^{k-i} b(k,i) \end{equation} The function used to generate $a(n,k)$ is shown below:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | from itertools import accumulate from operator import mul def a(n,k): kmax = 2**(n-1) if k > kmax: return print(f'for iteration {n} the maximum number for k is {kmax}') else: p = [1] + list(accumulate([2]*(k-1),mul)) b_ = [1]*k # index from 0 , ... , k-1 b = [1]*k k_ = 1 while k_ < k - 1: k_ = k_ + 1 for i in range(1,k_): # only evaluate range for current step b[i] = abs(b_[i-1] - b_[i]) b_ = b[:] return sum([xi*pi for (xi,pi) in zip(b,p[::-1])]) |
For $a(10,432)$ the code takes 9.73 ms ± 1.28 ms.
C
After each successive iteration the triangles are scaled by a factor of $\frac{1}{2}$. The number of black triangles on the bottom row has the same property as the number of black triangles on any row. Recall that in our binary representation of Sierpinski's triangle we only include upwards pointing triangles (▲) . The original triangle is ▲; when it subdivides it generates 3 ▲. So the new row contains 2 ▲. There are no ▲ generated when a white triangle splits (we only get a single △). Each successive subdivision will generate 2 additional ▲ from each existing ▲ ; so we can safely infer that the number of ▲ on any row is a power of 2. Finally note that for any row of any iteration the last digit is always $\one$; a binary number that ends in $\one$ is odd.
D
Start by noting that, \begin{equation} a(n,k) = 2^{k-1} + 2^{k-2} b(n,k-2) + \ldots + 2 b(n,2) + 1 \end{equation} If we factor out $2^k$ we can rewrite this as, \begin{equation} a(n,k) = 2^k \left(2^{-1} + 2^{-2} b(n,k-2) + \ldots + 2^{-k+1} b(n,2) + 2^{-k} \right) \end{equation} From the property of the $\log$ function, $\log(a)/k=\log(a^{1/k})$. The $k$th root of the last expression is, \begin{equation} a(n,k)^{\frac{1}{k}} = 2 \left(2^{-1} + 2^{-2} b(n,k-2) + \ldots + 2^{-k+1} b(n,2) + 2^{-k}\right)^{\frac{1}{k}} \end{equation} Then since $\log(xy)=\log x + \log y$, \begin{equation} \log\qty(a(n,k)^{\frac{1}{k}}) = \log 2 + \log \left(\left(2^{-1} + 2^{-2} b(n,k-2) + \ldots + 2^{-k+1} b(n,2) + 2^{-k}\right)^{\frac{1}{k}}\right) \end{equation} The limit of $\log 2$ as $k \rightarrow \infty$ is easy. What do we do with the other term? We first rewrite it as, $$ \frac{\log \left(2^{-1} + 2^{-2} b(n,k-2) + \ldots + 2^{-k+1} b(n,2) + 2^{-k}\right)}{k} $$ The numerator does not grow as $k$ increases; in fact it has an upper bound since, $$ 2^{-1} + 2^{-2} b(n,k-2) + \ldots + 2^{-k+1} b(n,2) + 2^{-k} \leq 2^{-1} + 2^{-2} + \ldots + 2^{-k+1} + 2^{-k} $$ (we set all $b(n,k)=1$). The r.h.s. of the inequality when $k \rightarrow \infty$ is an infinite geometric progression, $$ \frac{1}{2} + \qty(\frac{1}{2})^2 + \qty(\frac{1}{2})^3 + \ldots = 1 $$ On the other hand, the denominator increases linearly with $k$; so we can conclude that the limit of the other term is zero.
E
To answer (i) the following diagram is useful:
For (ii) note that the area of a regular triangle with side $L$ is $\sqrt{3}L^2/4$; therefore the total surface area is $\sqrt{3}L^2$.
Question 4. Unplug
A
Before writing the code it helps to think about the problem we are trying to solve. First, lets look at the case of three dials; we denote the setting of each dial as $d_i$ with $i=1,2,3$. Lets say we wanted to set dial 1 to some value $d$; what is the
$\def\Mod{\mathrm{mod}}$ The formula that gives the same answer is $\Mod((3-4),5)$, since $-1=-1\cdot 5+4$.
If instead we move the dial in the
If we want to find the dial setting that requires the minimum number of turns for 3 dials then we can use the following algorithm:
- Select all values for the dial setting $d=0,1,2,3,4,5$.
- For each value of $d$ calculate $r^*(d_1,d)$, $r^*(d_2,d)$, $r^*(d_3,d)$.
- For each value of $d$ calculate $n(d)=r^*(d_1,d)+r^*(d_2,d)+r^*(d_3,d)$.
- The value of $d$ which produces the smallest value for $a(d)$ is the optimal solution.
As an illustration of the algorithm consider that we start with three dials set at $[1,2,0]$. We get the following set of values for each dial (step 2) and $n(d)$ (step 3): $$ \begin{matrix} d & 0 & 1 & 2 & 3 & 4 \\ r^*(1,d) & 1 & 0 & 1 & 2 & 2 \\ r^*(2,d) & 2 & 1 & 0 & 1 & 2 \\ r^*(0,d) & 0 & 1 & 2 & 2 & 1 \\ \hline n(d) & 3 & 2 & 3 & 5 & 5 \\ \end{matrix} $$ So the optimal dial setting is $d=1$ and it is achieved after 2 dial turns.
Having found a solution for the 3 dials problem we can now attempt to solve the more difficult problem for $n$ dials. We now start with an array $[d_1,d_2,\ldots,d_n]$ of initial dial settings. A reasonable strategy is to look at the optimal dial setting for each group $[d_1,d_2,d_3],[d_2,d_3,d_4], \ldots$ and then pick the group which requires the minimum number of dial turns. For example, if we find a group like $[3,3,3]$ it would be an obvious choice since we can immediately unplug them. But if we had to compare a group that requires 2 dial turns and a group that requires 3 dial turns the choice is not as straightforward. If we follow a local strategy (we are only interested in the group of 3 dials with the lowest number of turns), we might end up with a suboptimal global strategy: after taking out these 3 dials we end up with a new set of dials that takes more turns to complete.
For this reason, we need to consider two parameters for each group of three dials:
- The number of dial turns it takes to unplug them.
- The number of dial turns it takes to remove all remaining dials.
We have a solution for the first but not for the second parameter. Still lets pretend we actually have a solution, $V$; how would we use it to play the game for 9 dials?
We can choose one of the following groups: $$ [d_1,d_2,d_3],[d_2,d_3,d_4],[d_3,d_4,d_5],[d_4,d_5,d_6],[d_5,d_6,d_7],[d_6,d_7,d_8],[d_7,d_8,d_9] $$ For each of these groups we can calculate $n^*([d_i,d_{i+1},d_{i+2}])$, the minimum number of dial turns it takes to unplug them. To simplify the expressions lets call this $n^*(i)$. Then since we have a solution for $V$ we can calculate the corresponding values for the remaining dials: for example, if we choose $[d_1,d_2,d_3]$ (the group for $i=1$) we are left with $[d_4,d_5,d_6,d_7,d_8,d_9]$. For this set of dials we need $V(1)$ remaining dial turns. Therefore the optimal value for $i$ is given by the solution to the following equation: $$ \min_{i}\left[n^*(1)+V(1),n^*(2)+V(2),n^*(3)+V(3), n^*(4)+V(4),n^*(5)+V(5),n^*(6)+V(6),n^*(7)+V(7)\right] $$ which is usually abbreviated to $\min_{i}[n^*(i)+V(i)]$. This is translated as “minimize $n^*(i)+V(i)$ with respect to $i$” in the same way that we write $\min_{x}[x^2]$ instead of “minimize the function $x^2$ w.r.t. $x$”.
Although we do not have a closed form solution for $V(i)$ we have something equally good: recursion. Since we have solved the problem for three dials we can write a recursive algorithm. An example of the solution to this problem is shown in the code below; note that to save time for problems with a large number of dials we use memorization. This means that as soon as we find a solution for a dial setting we store it in a global array so that we do not have to redo the optimisation when we encounter it again.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | import random def remsub(dall,d3): N = len(dall)-2 i = 0 while d3!=dall[i:i+3] and i<N: i = i+1 if i==N: return "Failed" else: del dall[i:i+3] return dall def rstar(d,x): return min([(d-x)%5,(x-d)%5]) all_stars = [] # each element is an array [[state],[choice],[remainder],value] def nstar(d3): states = [all_stars[i][0] for i in range(len(all_stars))] # list of all optimized states if d3 in states: # state has already been optimised return all_stars[states.index(d3)] else: sc = [sum([rstar(d,i) for d in d3]) for i in range(5)] istar = sc.index(min(sc)) result = [d3, istar,None, sc[istar]] # state, choice (in this case just the number for all three dials), end state, number of turns all_stars.append(result) return result def opt(dials): if len(dials) % 3 == 0: states = [all_stars[i][0] for i in range(len(all_stars))] # list of all optimized states if dials in states: # state has already been optimised return all_stars[states.index(dials)] else: if len(dials)==3: # last stage return nstar(dials) else: N = len(dials)-2 series1 = [dials[i:i+3] for i in range(N)] series2 = [dials[:i]+dials[i+3:] for i in range(N)] obj = [] for i in range(N): loc = nstar(series1[i]) glo = opt(series2[i]) obj.append(loc[3]+glo[3]) istar = obj.index(min(obj)) result = [dials,series1[istar],series2[istar],obj[istar]] all_stars.append(result) return result else: return "Number of dials must be a multiple of 3" |
The solutions for a number of different problems are shown below:
B
$\mathtt{BAO}$ is made of three capital letters with ASCII values 66, 65 and 79. We convert these to decimal number 666579. Its quinary representation is, $$ \mathsf{666579}_{\mathsf{10}} = 1\cdot 5^8 + 3 \cdot 5^7 +2 \cdot 5^6 + 3 \cdot 5^5 + 1 \cdot 5^4 + 2 \cdot 5^3 + 3 \cdot 5^2 + 0 \cdot 5 + 4 = \mathsf{132312304}_{\mathsf{5}} $$ The solution to this dial set is shown below:
It takes four dial turns to solve this setting.
C
The setting presented here can be solved without using a computer. Notice that 2023 contains a single zero; this number is repeated 6 times, so we can make two $[0,0,0]$ groups if we unplug the intermediate dials. There are five $[2,3,2]$ groups which require a single dial turn. The last group of dials is $[2,2,3]$ which also requires a single dial turn. So this setting can be solved after 6 dial turns.
D
For a game with $n$ dials, since each dial can take one of five values $(0,1,2,3,4)$, there are $5^n$ possible permutations. Given an initial setting of these $n$ dials we want to generate the maximum number of dial turns before we reach the final setting $[0,1,0,\ldots,0]$ when the game stops. We can do this by going through all the remaining permutations while making sure that we keep the final setting for last. So the maximum number of dial turns is $5^n-1$ since we must exclude the initial setting. A diagram for the process of $n=3$ (each dial now takes values from $(0,1,2)$) is shown ; the diagram for $n=5$ requires 125 rows!
Comments
Post a Comment