-
Notifications
You must be signed in to change notification settings - Fork 0
/
J.tex
144 lines (136 loc) · 4.32 KB
/
J.tex
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
\section{J}%
\setcounter{MaxMatrixCols}{20}
\label{sec:j}
\begin{frame}
\frametitle{Problem J: Just Jingling}
\begin{itemize}
\item Given a lyric, how many times do we have to write it in a spiral to arrive back at the original lyric?
\item \textbf{Insight:} we can reduce the problem to writing the integers $1\dots n$ in a spiral
\begin{itemize}
\item The fact that the input is simply the \textit{length} of the lyric should point to this observation
\end{itemize}
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Problem J: Just Jingling (cont.)}
\begin{itemize}
\item \textbf{Insight:} we can reduce the problem to writing the integers $1\dots n$ in a spiral
\item Let's try $n=13$ (sample case 3)
\[
\begin{array}{cccc}
& & & 13\\
5 & 4 & 3 & 12\\
6 & 1 & 2 & 11\\
7 & 8 & 9 & 10
\end{array}
\mapsto
\begin{array}{cccc}
& & & 10\\
12 & 3 & 4 & 9\\
6 & 13 & 5 & 8\\
1 & 2 & 11 & 7
\end{array}
\mapsto
\begin{array}{cccc}
& & & 7\\
9 & 4 & 3 & 11\\
6 & 10 & 12 & 2\\
13 & 5 & 8 & 1
\end{array}
\]
\[
\mapsto
\begin{array}{cccc}
& & & 1\\
11 & 3 & 4 & 8\\
6 & 7 & 9 & 5\\
10 & 12 & 2 & 13
\end{array}
\mapsto \cdots \mapsto
\begin{array}{cccc}
& & & 13\\
5 & 4 & 3 & 12\\
6 & 1 & 2 & 11\\
7 & 8 & 9 & 10
\end{array}
\]
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Problem J: Just Jingling (Cont.)}
\begin{itemize}
\item Let's relabel so that our original spiral looks like
\[
\begin{array}{cccc}
& & & 1\\
2 & 3 & 4 & 5\\
6 & 7 & 8 & 9\\
10 & 11 & 12 & 13
\end{array}\mapsto
\begin{array}{cccc}
& & & 13\\
5 & 4 & 3 & 12\\
6 & 1 & 2 & 11\\
7 & 8 & 9 & 10
\end{array}
\]
Then the spiral induces a permutation on these elements, and we continue applying the permutation over
and over again until it comes back to the original order.
\item We can think of the permutation as a function $f$ from the integers $1\dots n$ to the
integers $1\dots n$ that is one-to-one. It looks like
\[
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\
13 & 5 & 4 & 3 & 12 & 6 & 1 & 2 & 11 & 7 & 8 & 9 & 10 \end{pmatrix}
\]
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Problem J: Just Jingling (Cont.)}
\begin{itemize}
\item Then iterating the spiral process is equivalent to composing this function with itself multiple times.
For example, the second spiral we write will be
\[ f\circ f = \]
\[
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\
13 & 5 & 4 & 3 & 12 & 6 & 1 & 2 & 11 & 7 & 8 & 9 & 10 \end{pmatrix}
\]
\[
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\
13 & 5 & 4 & 3 & 12 & 6 & 1 & 2 & 11 & 7 & 8 & 9 & 10 \end{pmatrix}
\]
\[
=
\]
\[
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\
10 & 12 & 3 & 4 & 9 & 6 & 13 & 5 & 8 & 1 & 2 & 11 & 7 \end{pmatrix}
\]
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Problem J: Just Jingling (Cont.)}
\begin{itemize}
\item But notice that, in composing this permutation with itself many times, we will end up with
some elements cycling to each other. It will look like this:
\begin{align*}
f &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13\\
13 & 5 & 4 & 3 & 12 & 6 & 1 & 2 & 11 & 7 & 8 & 9 & 10 \end{pmatrix}\\
&= (1,13,10,7)(2,5,12,9,11,8)(3,4)(6)
\end{align*}
\item These numbers will cycle, and we want to know when they are all \textit{simultaneously}
at the beginning of the cycle, so we should just take the least common multiple of the cycle lengths!
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Problem J: Solution}
\pyf{J}
\end{frame}
\begin{frame}
\pyf{J2}
\end{frame}
\begin{frame}
\pyf{J3}
\end{frame}
\begin{frame}
\pyf{J4}
\end{frame}