12
$\begingroup$

I've been invited (by my kid) to give a one hour talk to her highschool math club. Last year (right before the pandemic hit) I did two such talks on probability, and they loved it. I'm looking for topic suggestions.

Logistics: There will be about $10-15$ kids total, from grades $9-12$. These kids are mostly "A" students, and some of them have skipped a math grade, but they're nowhere near Olympiad standard. The talk will be on March $1$st, $2021$, and will be on zoom. I will be making slides this weekend.

I don't want this to become an "educational" lecture, so I'm looking for fun examples to motivate certain math areas. E.g. last year my talks on probability culminated with Polya Urn and Buffon's Noodle. Also, I'd like everything (well, $95\%$) to be fully explainable within the one hour, i.e. I don't want to just spew facts and then tell them "just trust me".

My own math skill tends toward discrete: comp-sci, combinatorics, etc. However I'm open to any idea - esp. if it has worked for you before! - as long as I can learn it during one weekend. :)

Some ideas:

  • modulo arithmetic esp. finite fields: Perfect shuffle is fun. Would cryptography (e.g. RSA) be too difficult? What about codes e.g. Hamming? Any other fun examples of modulo arithmetic?

  • non-Euclidean geometry: especially how a POINT in elliptic geometry is actually $2$ "ordinary points". Can the alternates to the parallel postulate (and some consequence e.g. angle sum in a triangle) be explained sufficiently at highschool level in an hour?

  • finite geometry: Personally I find Finite projective planes very beautiful. Do they (or finite affine planes) have any application? (Besides the kiddie game Spot It?)

  • algorithm: This is actually my work area, but I don't know what I can cover in an hour. Maybe the $O(N \log N)$ lower bound for sorting? Some of these kids don't even have coding experience... :(

  • graph theory: Edge coloring of a complete graph is one of my favorite pictorial proofs. Eulerian tour. Euler characteristic (of a planar graph) is related. What else? Shortest path would require discussion of algorithm. Hall's marriage theorem is surprising and neat but I don't think I can prove it from scratch in an hour.

  • combinatorics: Start with ${N \choose m}$ and then stars-and-bars for sure. What are your favorite (elementary) examples? Can Burnside's lemma be proved from scratch (at highschool level, without group theory) in an hour?

Comments on above and/or any other suggestion most welcome!

(Apologies if I'm tagging too widely...)

$\endgroup$
18
  • 1
    $\begingroup$ My answer to this question uses finite projective planes. $\endgroup$
    – saulspatz
    Feb 23 at 2:16
  • 1
    $\begingroup$ I like Pell's equation, use of continued fractions (but visually, no subscripts) to find the very small values of $x^2 - n y^2.$ Just a simple calculator thing. Something they can do on their own...Also the Gauss Lagrange method for indefinite binary quadratic forms. $\endgroup$
    – Will Jagy
    Feb 23 at 2:37
  • 1
    $\begingroup$ I put an example and some background. The "digits" $4,1,1,2,1,1,8$ for $ \sqrt{21}$ come from calculator, for each irrational number $w, $ the next irrational is $1/(w - \lflloor w \rfloor$) so $\sqrt {21 } = 4.58; 1.716, 1.3956, 2.52, 1.89, 1.116,8.5825$ which is all that needs be calculated: $8 = 2 \cdot 4$ See my answer, how to create the next rational convergent $\frac{p}{q}$ from a new digit, also value $p^2 - 21 q^2$ $\endgroup$
    – Will Jagy
    Feb 23 at 3:01
  • 1
    $\begingroup$ As a high schooler, I think I can give the best advice :). I think non-Euclidean geometry would be cool, and it's possible to explain the basics and explore some neat questions in an hour. Another completely different idea is inclusion-exclusion principle (although I can't think of any fun questions with this off the top of my head, I do think it's a feasible option). And I second @Aaratrick's suggestion of Gray codes. $\endgroup$ Feb 23 at 6:15
  • 1
    $\begingroup$ Finite fields and coding theory? You could try and reuse my old MSE blog post. Except that, in the interest of trying to be current, don't use CDs as the application. Make it QRCodes! The algebra (= the codes) is the same. The app is different, as is the technology of retrieving the codewords. $\endgroup$ Feb 24 at 5:55
6
$\begingroup$

Have you considered game theory (e.g. Nim or Nim-like games)? Will students have the chance to interact and play a few games against each other?

Since you say it's a "math club", are these kids AMC 10/12 level?

Among your suggestions, I find combinatorics the most promising. There are lots of angles of attack: 1. story-problem/story-proof, 2. algebraic proof, 3. generating functions.

Aw man you're making me miss my high-school times. Can you record this and put it on the internet?

$\endgroup$
5
  • 1
    $\begingroup$ I came here to post something similar. Alternatively, some kind of fixed point theorem might be fun. Brouwer in 1D or 2D Sperner's lemma. $\endgroup$ Feb 23 at 2:01
  • $\begingroup$ Last year Nim would have worked better, since it was in person. This year it'll be a zoom call... :( Game theory is a great idea though. I used to know nimbers; just need to relearn them. :) I dont have access to books though, e.g. the classic Winning Ways. any good website you can recommend? It'd be awesome if I can show how universal Nim is! $\endgroup$
    – antkam
    Feb 23 at 2:12
  • $\begingroup$ Yeah these kids are AMC 10/12 level, the best math kids from our highschool, but no one from our highschool is Olympiad level. Re: combinatorics: do you have concrete examples? Or, website suggestions? A 1-hr-explainable use of generating functions would probably blow their mind...! $\endgroup$
    – antkam
    Feb 23 at 2:16
  • $\begingroup$ @PeteCaradonna - sorry I don't know anything about fixed point theorems (except their statements). Too far outside my area... $\endgroup$
    – antkam
    Feb 23 at 2:18
  • 1
    $\begingroup$ Dots and Boxes? upcommons.upc.edu/bitstream/handle/2117/78323/memoria.pdf $\endgroup$
    – Trurl
    Feb 26 at 13:40
5
$\begingroup$

Again, thanks all of you for answering and commenting. I thought some of you might be interested in what actually happened.

I decided to go with a theme of "finite mathematics" and talk mostly about modulo arithmetic, using it to illustrate $3$ different topics:

(A) I started by performing a crowd-pleasing "magic trick" related to the perfect shuffle. I actually cannot do a perfect shuffle at all, so instead I did a sort of reverse: I dealt a deck of cards into 4 piles, re-assembled them into a deck, and repeated the process $3$ more times. As expected, the kids were very surprised to see that the original deck order was restored! Which I then explained via $4^4 = 256 = 1 \pmod{51}$ as in the wikipedia article. (BTW if some of you are not aware of this trick, it's actually quite neat and also easy to do in practice.) This took about $15$ minutes.

(B) Then I talked about error correction codes, starting with the background: why you need it, message, encoding, codeword, error, decoding, etc. For motivation, I found out that the ASCII for lower-case "l" and lower-case "d" differ by just $1$ bit, so I made up a story how, with a $1$-bit error, "Trump lied" would become "Trump died". :D

Anyway, I discussed the Hamming $(7,4)$ code in detail, with actual examples of encoding and decoding, doing parity checks (which I called mod $2$ addition) by hand, and introducing the concept of Hamming distance. I did not use linear algebra, as most kids haven't learned that.

Then I discussed the crucial fact that, when $N$ is prime, mod $N$ arithmetic supports division (I did not use the term finite field), which in turn means you can solve systems of equations. This segued into polynomials and Reed Solomon codes, which I covered briefly using the approach of this excellent blogpost by @JyrkiLahtonen - thanks!

The whole error correction code segment took about $30$ minutes.

(C) Lastly, I talked about the kiddie game Spot-It - I have asked my kid to poll her friends before hand and many are familiar with it. While the game itself is uninteresting, the math behind the card design is fascinating: it's based on the finite projective plane of order $7$. I spent many slides using modulo $5$ arithmetic to construct the finite affine plane of order $5$, then showing how it satisfies some of Euclid's axioms and therefore deserves the fancy name of "finite plane". Then, I showed how it can almost be turned into the cards of Spot-It, discussing point-line duality briefly. Finally I added the points and line at infinity to turn it into a finite projective plane for the full solution. This segment took about $25$ minutes.

The whole thing took about $70-75$ minutes and was quite well received, both during the event, and when my kid told me the others' reactions afterwards. She said the older kids mostly got it, while the younger kids had some trouble but still got the flavor.

I spent way, waaaaay too much time over the weekend making the slides, as I was having such a great time! I just couldn't bear to leave out any of the $3$ topics since they're all fun (and even "educational" in the case of error correction codes) and also show a great variety between them. I ended up with about $60$ slides! Had to talk really fast to go through them in $70$ minutes. :)

$\endgroup$
3
$\begingroup$

Conway's rational tangles, continued fractions, and the "greedy" Euclidean algorithm!

Here are some Math Circles notes by Tom Davis on the topic. You're going to want to have two pieces of thick rope, at least 10 feet in length, and hopefully have at least 4 volunteers to hold the ends for a very fun interactive activity.

Figure from p. 43 in The Knot Book by Colin C. Adams

Pictured: construction of the tangle $$ -4 + \frac{1}{2+\frac{1}{3}} = -\frac{25}{7} $$

$\endgroup$
2
  • $\begingroup$ Wow, I never knew this before! Thanks! Will read it in detail later. Sadly my talk will be a video call due to covid, so the demo would be difficult. $\endgroup$
    – antkam
    Feb 23 at 2:20
  • $\begingroup$ Yeah, that really puts a damper on the activity. It's very much an interactive thing, kind of like when a magician says, "I need volunteers from the audience." :-) $\endgroup$ Feb 23 at 2:28
2
$\begingroup$

The $2$-dimensional case of Sperner's lemma is a good introduction to graph theory. The proof is self-contained aside from using the Handshaking lemma, which is also easy to show. Take a triangle and subdivide it into several smaller triangles. Call a triangle minimal if it contains no other triangles. If whenever two minimal triangles touch, they share a side, then we call this subdivision a triangulation. (This is to avoid the possibility that the side of one minimal triangle is part of a side of another triangle.)

Color the nodes of the original triangle three colors, say red, blue, and green. Then color all of the other nodes with those colors, under the condition that if a node lies on a side of the original triangle, then it has to be given one of the colors used for the original two nodes of that side. Nodes inside the triangle can be given any of the three colors. See the picture below. (Apologies for the poor quality- this was made in mspaint and then hastily resized.) Observe that there's a red-blue side, a red-green side, and a blue-green side.

enter image description here

There are five minimal triangles that have a vertex of each color. Sperner's lemma states that there must always be a minimal triangle with a node of each color, and in fact, there must be an odd number of such triangles. To see this, we will construct a graph from this triangulation. We do so by associating a vertex to each face, including the outside face, and draw an edge between two vertices if the side shared by their corresponding triangles has two different colors. See the picture below.

enter image description here

The internal vertices can have degree either $0$, $2$, or $3$. The degree is $0$ if the nodes of the corresponding triangle all have the same color, $2$ if the nodes use two different colors, and $3$ if the nodes all use different colors. We want to show that there are an odd number of internal vertices of odd degree. The Handshaking Lemma tells us that a graph must have an even number of vertices with odd degree, so if we can show that the outside vertex has odd degree, then the lemma follows. For example, the outside vertex in our picture has degree $7$.

To see this, look at any side of the original graph, say the red-green side. Moving from the red node to the green node, that side contributes $1$ whenever the colors switch from red to green or green to red. Since we start with a red node and end with a green node, there must be an odd number of switches. Hence, each side of the original triangle makes an odd contribution to the degree of the outside vertex so the outside vertex has odd degree. By the Handshaking Lemma, Sperner's Lemma follows.

$\endgroup$
1
  • $\begingroup$ Thanks! I did not know this result before. Wikipedia also discusses how this can be used to prove a special case of Brouwer's fixed point theorem! (But I havent fully grokked that proof yet.) $\endgroup$
    – antkam
    Feb 23 at 15:48
2
$\begingroup$

When the numbers are not too bad, we can just do a one-step calculation over a few times: Here I am using decimals; for worse numbers like $\sqrt{61}$

Lubin posted an algorithm (using whole numbers only) that appears to be what Fermat used; I then programmed that. There is a method due (largely) to Gauss and Lagrange that produces a chain or cycle of indefinite quadratic form, I programmed that long ago. Again, no decimal, all whole number, allows for any $\frac{A+\sqrt B}{C}.$ Finally, Conway's Topograph method. For that, I can recommend Weissman for self study or parent-child team study of some sort

Full treatment of $\sqrt{19}$

Method described by Prof. Lubin at Continued fraction of $\sqrt{67} - 4$

$$ \sqrt { 19} = 4 + \frac{ \sqrt {19} - 4 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {19} - 4 } = \frac{ \sqrt {19} + 4 }{3 } = 2 + \frac{ \sqrt {19} - 2 }{3 } $$ $$ \frac{ 3 }{ \sqrt {19} - 2 } = \frac{ \sqrt {19} + 2 }{5 } = 1 + \frac{ \sqrt {19} - 3 }{5 } $$ $$ \frac{ 5 }{ \sqrt {19} - 3 } = \frac{ \sqrt {19} + 3 }{2 } = 3 + \frac{ \sqrt {19} - 3 }{2 } $$ $$ \frac{ 2 }{ \sqrt {19} - 3 } = \frac{ \sqrt {19} + 3 }{5 } = 1 + \frac{ \sqrt {19} - 2 }{5 } $$ $$ \frac{ 5 }{ \sqrt {19} - 2 } = \frac{ \sqrt {19} + 2 }{3 } = 2 + \frac{ \sqrt {19} - 4 }{3 } $$ $$ \frac{ 3 }{ \sqrt {19} - 4 } = \frac{ \sqrt {19} + 4 }{1 } = 8 + \frac{ \sqrt {19} - 4 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccc} & & 4 & & 2 & & 1 & & 3 & & 1 & & 2 & & 8 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 4 }{ 1 } & & \frac{ 9 }{ 2 } & & \frac{ 13 }{ 3 } & & \frac{ 48 }{ 11 } & & \frac{ 61 }{ 14 } & & \frac{ 170 }{ 39 } \\ \\ & 1 & & -3 & & 5 & & -2 & & 5 & & -3 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 19 \cdot 0^2 = 1 & \mbox{digit} & 4 \\ \frac{ 4 }{ 1 } & 4^2 - 19 \cdot 1^2 = -3 & \mbox{digit} & 2 \\ \frac{ 9 }{ 2 } & 9^2 - 19 \cdot 2^2 = 5 & \mbox{digit} & 1 \\ \frac{ 13 }{ 3 } & 13^2 - 19 \cdot 3^2 = -2 & \mbox{digit} & 3 \\ \frac{ 48 }{ 11 } & 48^2 - 19 \cdot 11^2 = 5 & \mbox{digit} & 1 \\ \frac{ 61 }{ 14 } & 61^2 - 19 \cdot 14^2 = -3 & \mbox{digit} & 2 \\ \frac{ 170 }{ 39 } & 170^2 - 19 \cdot 39^2 = 1 & \mbox{digit} & 8 \\ \end{array} $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$\sqrt{21}$ Simple continued fraction tableau:

4.58, 1.7, 1.39, 2.52, 1.89, 1.11,8.58

$$ \begin{array}{cccccccccccccccccc} & & 4 & & 1 & & 1 & & 2 & & 1 & & 1 & & 8 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 4 }{ 1 } & & \frac{ 5 }{ 1 } & & \frac{ 9 }{ 2 } & & \frac{ 23 }{ 5 } & & \frac{ 32 }{ 7 } & & \frac{ 55 }{ 12 } \\ \\ & 1 & & -5 & & 4 & & -3 & & 4 & & -5 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 21 \cdot 0^2 = 1 & \mbox{digit} & 4 \\ \frac{ 4 }{ 1 } & 4^2 - 21 \cdot 1^2 = -5 & \mbox{digit} & 1 \\ \frac{ 5 }{ 1 } & 5^2 - 21 \cdot 1^2 = 4 & \mbox{digit} & 1 \\ \frac{ 9 }{ 2 } & 9^2 - 21 \cdot 2^2 = -3 & \mbox{digit} & 2 \\ \frac{ 23 }{ 5 } & 23^2 - 21 \cdot 5^2 = 4 & \mbox{digit} & 1 \\ \frac{ 32 }{ 7 } & 32^2 - 21 \cdot 7^2 = -5 & \mbox{digit} & 1 \\ \frac{ 55 }{ 12 } & 55^2 - 21 \cdot 12^2 = 1 & \mbox{digit} & 8 \\ \end{array} $$

=======================================

$ \sqrt{41}$

6.403, 2.48, 2.08, 12.40,2.48, 2.08, 12.39

$$ \begin{array}{cccccccccccccccc} & & 6 & & 2 & & 2 & & 12 & & 2 & & 2 & & 12 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 6 }{ 1 } & & \frac{ 13 }{ 2 } & & \frac{ 32 }{ 5 } & & \frac{ 397 }{ 62 } & & \frac{ 826 }{ 129 } & & \frac{ 2049 }{ 320 } \\ \\ & 1 & & -5 & & 5 & & -1 & & 5 & & -5 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 41 \cdot 0^2 = 1 & \mbox{digit} & 6 \\ \frac{ 6 }{ 1 } & 6^2 - 41 \cdot 1^2 = -5 & \mbox{digit} & 2 \\ \frac{ 13 }{ 2 } & 13^2 - 41 \cdot 2^2 = 5 & \mbox{digit} & 2 \\ \frac{ 32 }{ 5 } & 32^2 - 41 \cdot 5^2 = -1 & \mbox{digit} & 12 \\ \frac{ 397 }{ 62 } & 397^2 - 41 \cdot 62^2 = 5 & \mbox{digit} & 2 \\ \frac{ 826 }{ 129 } & 826^2 - 41 \cdot 129^2 = -5 & \mbox{digit} & 2 \\ \frac{ 2049 }{ 320 } & 2049^2 - 41 \cdot 320^2 = 1 & \mbox{digit} & 12 \\ \end{array} $$

============================

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 21 \cdot 0^2 = 1 & \mbox{digit} & 4 \\ \frac{ 4 }{ 1 } & 4^2 - 21 \cdot 1^2 = -5 & \mbox{digit} & 1 \\ \frac{ 5 }{ 1 } & 5^2 - 21 \cdot 1^2 = 4 & \mbox{digit} & 1 \\ \frac{ 9 }{ 2 } & 9^2 - 21 \cdot 2^2 = -3 & \mbox{digit} & 2 \\ \frac{ 23 }{ 5 } & 23^2 - 21 \cdot 5^2 = 4 & \mbox{digit} & 1 \\ \frac{ 32 }{ 7 } & 32^2 - 21 \cdot 7^2 = -5 & \mbox{digit} & 1 \\ \frac{ 55 }{ 12 } & 55^2 - 21 \cdot 12^2 = 1 & \mbox{digit} & 8 \\ \end{array} $$

http://www.maths.ed.ac.uk/~aar/papers/conwaysens.pdf https://www.math.cornell.edu/~hatcher/TN/TNbook.pdf

Find general solution for the equation $1 + 2 + \cdots + (n − 1) = (n + 1) + (n + 2) + \cdots + (n + r) $

When is $5n^2+14n+1$ a perfect square? x^2 - 5 y^2 =44

State 2 values of $x$ for which the value of $3x^2+4x-14$ is a perfect square.

How does one solve this recurrence relation?

Isolating $a_n$ in a recursive formula

Another quadratic Diophantine equation: How do I proceed?

How to find solutions of $x^2-3y^2=-2$?

Generate solutions of Quadratic Diophantine Equation

Why can't the Alpertron solve this Pell-like equation?

Finding all solutions of the Pell-type equation $x^2-5y^2 = -4$

If $(m,n)\in\mathbb Z_+^2$ satisfies $3m^2+m = 4n^2+n$ then $(m-n)$ is a perfect square.

how to solve binary form $ax^2+bxy+cy^2=m$, for integer and rational $ (x,y)$ :::: 69 55

Find all integer solutions for the equation $|5x^2 - y^2| = 4$

Positive integer $n$ such that $2n+1$ , $3n+1$ are both perfect squares

Maps of primitive vectors and Conway's river, has anyone built this in SAGE?

Infinitely many systems of $23$ consecutive integers

Solve the following equation for x and y: <1,-1,-1>

Finding integers of the form $3x^2 + xy - 5y^2$ where $x$ and $y$ are integers, using diagram via arithmetic progression

Small integral representation as $x^2-2y^2$ in Pell's equation

Solving the equation $ x^2-7y^2=-3 $ over integers

Solutions to Diophantine Equations

How to prove that the roots of this equation are integers?

Does the Pell-like equation $X^2-dY^2=k$ have a simple recursion like $X^2-dY^2=1$?

http://math.stackexchange.com/questions/1737385/if-d1-is-a-squarefree-integer-show-that-x2-dy2-c-gives-some-bounds-i/1737824#1737824 "seeds"

Find all natural numbers $n$ such that $21n^2-20$ is a perfect square.

Is there a simple proof that if $(b-a)(b+a) = ab - 1$, then $a, b$ must be Fibonacci numbers? 1,1,-1; 1,11

To find all integral solutions of $3x^2 - 4y^2 = 11$

How do we solve pell-like equations?

Diophantine equation $x^2 + xy − 3y^2 = 17$ <1,1,-3>

$\endgroup$
1
  • $\begingroup$ Wow, thank you for compiling such a long list!! :) $\endgroup$
    – antkam
    Feb 23 at 3:11
1
$\begingroup$

My own math skill tends toward discrete: comp-sci, combinatorics, etc. However I'm open to any idea - esp. if it has worked for you before! - as long as I can learn it during one weekend. :)

Some ideas:

  • modulo arithmetic esp. finite fields: Perfect shuffle is fun. Would cryptography (e.g. RSA) be too difficult? What about codes e.g. Hamming? Any other fun examples of modulo arithmetic?

...

  • algorithm: This is actually my work area, but I don't know what I can cover in an hour. Maybe the $O(N \log N)$ lower bound for sorting? Some of these kids don't even have coding experience... :(

You did probability before. Even without cryptography, I think it's fascinating that one can pretend to have probability using a pseudorandom number generating algorithm. The simplest algorithms are very simple, but still depend on basic results in modulo arithmetic, finite fields, etc. You could teach some basic statistical tests on PRNG quality if you want.

You can get what you need from Knuth's TAOCP vol. 2, ch. 3, or maybe Kneusel's Random Numbers and Computers (too shallow?) or Niederreiter & Winterhof (too deep?).

Another idea: Fourier analysis. Nice graphics. Sum cool curves, infinite series, integrals--or stick with discrete cases. You can even transform Boolean functions.

$\endgroup$
5
  • $\begingroup$ I dont have access to those books. Any free resources (websites, free e-books) you can recommend? If I end up doing crytography (with one "just trust me" about e.g. difficulty of digital logarithm) I would certainly also do PRNG. $\endgroup$
    – antkam
    Feb 23 at 2:57
  • $\begingroup$ Re: Fourier analysis - this would be great at showing them that sine and cosine are not just for geometry! :D But (at least in my mind) the fact you can decompose e.g. a square wave via FA is interesting but...so what? The key (IMHO) is that lots of systems actually have sinusoids as "eigen" solutions (not sure this is the right terminology), and that's what makes FA tremendously useful in practice. But that will take a lot of explaining. Most of these kids have not taken basic linear algebra. BTW what do you mean by transforming Boolean functions? $\endgroup$
    – antkam
    Feb 23 at 3:01
  • $\begingroup$ Not too long ago I got a used copy of the first edition of Knuth's TAOCP vol 2 for roughly $10 including shipping. There are significant changes here and there in the 3rd ed., but most of it is the same. Libraries may have copies. Pierre L'Ecuyer's website has many papers on PRNGs, including some mathematical review articles that you can supplement with what you already know or know of. Melissa O'Neill's paper is less mathematical, but might have elements that would be useful with students. $\endgroup$
    – Mars
    Feb 23 at 5:50
  • $\begingroup$ Fourier transforms of Boolean functions: e.g. see free PDF of book by O'Donnell here $\endgroup$
    – Mars
    Feb 23 at 5:50
  • $\begingroup$ Square waves show what's possible, but you can also analyze functions that aren't really periodic into periodic components. You might need an infinite number of them, maybe with longer and longer wavelengths, but it's just math .... :-) BTW I think it's useful to distinguish cryptographic PRNGs from those used for simulations and modeling. The latter can be simpler because the requirements are simpler: you don't need to thwart a smart attacker. $\endgroup$
    – Mars
    Feb 23 at 5:57
1
$\begingroup$

I've always been a fan of the coin problem. It's basically a generalization of the question, "what is the largest score in American football that cannot be achieved (say, ignoring safeties)?" It's got a built-in hook with the story of the "McNugget numbers". It very naturally motivates $\gcd(a_1, \ldots, a_n)$ and you can discuss existence of the Frobenius number. As I recall there's a nice graphical proof of the formula for two coins. The topic typically uses some basic number theory like Bezout's lemma, but if anything that's a feature and not a bug.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.