| Home | 1st Year Circle | 2nd Year Circle | Archive | About | Math Hour | Math Hour Olympiad |
Here you can see the weekly newsletter containing an update of what we're up to this week. This newsletter is emailed out every Friday after a Math Circle meeting. If you're not receiving these email updates but want to be, just let Chris know via email.
First, there are only TWO more Math Circle meetings left this year: Thursday (5/31) and Thursday (6/07). The Olympiad on Sunday, June 10, marks our last activity of the year.
In Thursday's Math Circle, we continued studying cryptography, this time focusing on ciphers. We learned about simple Caesar ciphers, substitution ciphers, Hill ciphers, and turning grille ciphers, and more -- all ways of encrypting blocks of text to look like gibberish to the untrained eye.
Since we're all getting so well-trained in cryptography, the Math Circle will be holding its own cryptography competition this coming Thursday (5/31): the CryptOlympiad. All your cryptography practice will come into use as you compete for points to decrypt encrypted text. For all the practice you can get, make sure you do the homework for this week, helping decrypt Martian ciphers!
There were two winning teams last week, both with 16 points: -The Best Team (Conrad, David, Joshua, Tiffany) -Insert Your Team Name Here (Anderson, Eli, Lola, Nate).
All team point totals can be found on the website. Thursday's CrytOlympiad and homework presentations are the last chance to get points for the year. Make them count!
First and most importantly: registration for the UW Math Olympiad on June 10 WILL SOON BE CLOSING! If you have not yet registered as a participant in the Olympiad, please do so AS SOON AS POSSIBLE! Due to size constraints, we have very few remaining positions.
On Thursday in Math Circle we further studied cryptography. In the context of two parties wanting to communicate without any third-party spies being able to notice what they're talking about, we discussed three different methods for transmitting information "safely". We talked about what "safe" even means here by thinking about what kind of information would be needed to decode an encrypted message. Our worksheet provided a number of real-world encryption methods: the encryption method outlined in Problem 3 on our worksheet is the basis for Diffie-Hellman key exchange. The method outlined in Problem 2 plays an integral part of the famous RSA algorithm.
The homework for this week involves decoding some substitution ciphers. A substitution cipher is a block of text in which all the letters have been switched around by some sort of permutation. This is just one way of encoding a message you want to send to someone -- another method than those methods already discussed in class.
Congratulations to both The Best Team (Conrad, David, Joshua, and Tiffany) and Deductive Induction (Akhi, Alexander, Ruta, and Steven) for both having 18 points this week! The overall team points can be found online. As they stand now:
On Thursday we started to revisit modular arithmetic (adding and multiplying with remainders). We are keeping a keen eye on applications to encoding certain information. We'll keep this in mind as we work our way towards a discussion of the RSA algorithm -- a public key encryption system for keeping real-life data safe from prying eyes.
We played Battleship yesterday on a 4x4 grid. The squares on the grid were labelled 1-16, and we found that we could increase the security of our ships by encoding their positions. We encoded by multiplying each grid number by some fixed integer N, and then reducing everything modulo 17 (taking the remainder when dividing by 17). It turns out that it's actually pretty easy to decode this encoding if you have access to the fixed N -- all you have to do is find some M such that N*M=1 (mod 17). On the homework you'll see a different kind of encoding scheme. Do you think there's a simple algorithm for breaking this new encoding method?
The homework this week has some longer problems, so make sure you give yourself enough time to think about each problem and let it sit in your subconscious. Problem 1 actually appeared on the 2011 Math Hour Olympiad, so this is good practice for the next Olympiad on June 10. By the way, registration is still open for the June 10 Olympiad, but it will close at least by May 21. Registration is required -- make sure you sign up so that you can experience a day's-worth of problem solving!
The homework presentations involved a lot of cutting and pasting together of different topological spaces. The winning team in points was the Pascalian Pandas (Cynthis, Kyle, Thomas) with 14 points. Good work!
Before talking about Math Circle, I just want to remind you all the second lecture of the UW Math Hour lecture series. This FREE talk will be held from 1-2pm on THIS SUNDAY in Savery Hall 260. Steven Klee from UC Davis will be talking to us about "The Mathemagic of Magic Squares."
On Thursday we completed our study of relations and in particular equivalence relations. In the past few weeks we've seen how to vastly generalize "less than", "greater than", and "equals" to objects such as partial orders and equivalence relations. We've only touched on the subjects, and I invite you to ask me for some related ideas if you want to learn more about this on your own!
In the case of equivalence relations, we've seen how to form equivalence classes and create beautiful geometric objects out of these classes (i.e. quotient sets). For example, we saw how to think of all rational numbers as a quotient set of a particular equivalence relation on pairs of integers. Yesterday, we defined the projective line and projective plane by means of quotient sets. The projective line is a way of algebraically adding infinity to the real number line, and the projective plane is doing the same with a 2-dimensional plane. In fact, we saw that *all lines* intersect on the projective plane (parallel lines intersect "at infinity"!). The homework for this week constitutes our last foray into quotient sets.
Last week on Thursday we moved to a new topic: relations. These are a vast generalization of terms like "less than", "greater than", and "equal to". There are many different types of relations (symmetric, transitive, reflexive, etc.), and we'll be considering their usefulness/differences in the upcoming weeks. For instance, in the next Math Circle we'll discuss in detail equivalence relations and see their beautiful associated geometry.
We have moved to new teams -- the four (self-named) teams below:
This week we had a tie for the winning team: Deductive Induction (Akhi, Alexander, Ruta, Steven) and Insert Your Team Name Here (Anderson, Eli, Lola, Nate)!
Look soon for a separate email from me detailing the teams and students from the Winter quarter with the most points.
The homework this week is posted online. We did not cover as much of equivalence relations as planned, so remember that Problem 2 (on equivalence classes) is omitted!
On Thursday we spent our time working through some interesting puzzles. We first saw how to use some basic logic to determine complete information about a hidden word based on very partial information obtained through guessing. Then we had some great homework presentations by Nate, Lola, David, Eli, and Conrad.
On the worksheet we devised a couple of algorithms: one for catching a spy (based on our algorithm from a while ago on counting the rational numbers), one for getting a fair coin toss out of an unfair coin, and one for "efficiently" determining a poisoned wine from 1000 possible choices. More precisely on this last point: we saw an introduction of how to use binary numbers to gather a whole lot of information into an arrangement of just a few 1s and 0s.
The winning team this week is the Giant Iron Potatoez (Conrad, Nate, and Lara) with 24 points! We'll be switching up teams again soon as we start into some more topics.
Next week we're going to work on a few linguistic puzzles -- the homework this week has some introductory problems towards this end. These require some great logical bookkeeping skills! After that we'll begin learning about binary relations -- kind of generalizations of "greater than", "less than", and "equals". I hope to use these to eventually talk about a way of algebraically formalizing the idea of "infinity" with something called the projective plane. This will serve as a starting example for studying some neat mathematical surfaces via topology.
Before anything else, I'd like to give a final reminder of the Monthly Math Hour talk this Sunday 3/11 at 1pm, in Savery Hall room 260 on the UW campus. Jon Brundan from the University of Oregon will be speaking on "Domino Tilings and Determinants". The MATH HOUR talks are all free of charge and open to more than just Math Circle students. See the MATH HOUR website for more details.
Yesterday in the Math Circle we continued our investigation into mathematical invariants. Many mathematical puzzles can be formulated as a type of game -- an invariant is a certain aspect of such a game which does not change from turn to turn, or maybe which changes in a perfectly predictable way from turn to turn. An example is a knight moving on a chessboard: each turn it alternates between black and white squares.
On Thursday we saw some enlightening homework solutions from Kyle, Joshua, and Ruta, which involved constructing a possible invariant for a given problem, and then somehow using that to solve the problem. We then discussed some games played by two mathematicians Newton and Leibniz. Particularly, we talked about noticing some particular invariant-y aspects of each game, and then using that to develop strategies. The homework this week further investigates these ideas.
At the end of class, we saw that it is impossible to switch the sequence 1234 to 4321 in an odd number of moves, where each move involves switching a single adjacent pair of numbers. Do you think that it would be possible in an odd number of moves if each move now allows switching of *any* pair of numbers (not necessarily adjacent)?
Last week I did not send out an email, so I'd like to congratulate the winning team LMS (Akhi, Anderson, and David) with 21 points. This week's winning team is the KLRful Cuttlefish (Kyle, Lola, Ruta, and Steven) with 26 points.
Yesterday we spent the class studying Conway's Game of Life, which relates to the automata we have looked at earlier, but is still very different: it is "played" on an infinite board of square cells which can be "on" or "off" and which "die" and "reproduce" by a system of four simple rules. We played with different interesting patterns and discovered that the rules don't have to be difficult for the possible life forms to be very complex! There are "still life" forms, which never change, "gliders" and "spaceships," which move along the board, "Gardens of Eden," which cannot be generated by any other pattern, and much more. For anyone interested, the site http://conwaylife.com/ has articles on everything Life, as well as a link to a free downloadable simulator with many patterns built in.
Since there was no homework due, there's no winning team this week (despite everyone's enthusiasm about Life), but there is a new homework on the topic of invariants, on which the next couple of weeks shall be spent.
I'd also like to remind you that the first Monthly Math Hour talk is coming up on Sunday, March 11, given by Jon Brundan from the University of Oregon. I encourage you all to go and to bring your friends, too! Here is a link for more information.
Before anything else, I'd like to mention that the Monthly Math Hour at UW is starting up again this spring quarter with a first talk by Jon Brundan from the University of Oregon on March 11. These are free monthly lectures at the UW campus on fun mathematical subjects aimed at all middle school students and open to all. Keep an eye on your inbox for another email from me containing more information about all these Sunday afternoon lectures!
On Thursday we finished up our recent development of combinatorics and counting techniques. We have learned about stars and bars, bijective proofs, and recurrence relations. Yesterday we even saw the possibility of putting some of those techniques together with induction to obtain some identities involving the Fibonacci numbers. We saw a two weeks ago how to use recurrence relations to develop the abundant Catalan numbers.
This week there is no homework. We have ended combinatorics for the time being. We will take the next meeting to spend one day learning about John Conway's Game of Life, a cellular automaton which is a little different than the automata we studied earlier this quarter. We'll see some pretty amazing animations of the Game of Life in progress. The Game of Life is an excellent example of some deep, beautiful mathematics coming out of a simple-sounding premise.
The winning team this week was the Archimedean Armadillos (Alexander, Joshua, and Thomas) with 26 points. We also had great homework solutions by Conrad, Kyle, Joshua, and Thomas this week! Keep it up!
Yesterday we learned about a combinatorial technique called 'recurrence relations'. This is for when we have a sequence of numbers for any given n (for example, the number of ways of tiling a 3xn board with any number of 2x2 blocks), and you can naturally describe the next number of the sequence in terms of some or all of the ones before it. An example which you've all seen at some point before is the Fibonacci numbers, where the next Fibonacci number is just the sum of the two before it (and to get the ball rolling from somewhere, the first two Fibonacci numbers are 0 and 1).
In the last hour of class we were pirates on board on mighty ship, the Katy Lan. Each team had a specific pirate task assigned to them, and they had to count the number of different ways that they could accomplish this task. All the five tasks are posted online. It turns out no matter which task a team was assigned, the number of ways of finishing it was exactly the same. We discussed at the end of class how to view some of the jobs as just restatements of some of the other ones -- I encourage you to try this for all five tasks!
The number of ways of accomplishing any of the pirate tasks (for a given n) defines the Catalan numbers. Like the Fibonacci numbers, the Catalan numbers can also be defined in terms of a recurrence relation and a few starting numbers. I tried and failed to describe this recurrence relation at the end of class yesterday, and I promise to start class next time with a much better explanation! In the meantime, try a web search for Catalan numbers to at least see what the formula is for any n (this will be useful for one of the homework problems this week -- try to interpret it as one of the pirate tasks and then use the formula for whatever n you have).
We had three great homework presentations this week from Thomas, Akhi, and Ruta. Next class I expect more volunteers to present solutions! I want to see homework presentations on Thursday from students who have not yet presented a solution this quarter!
The winning team this week was the KLRful Cuttlefish (Kyle, Lola, Ruta, and Steven). There are lots of points available on the homework for next week. If you have not presented yet this quarter, now's your chance to grab some points for your team!
On Thursday we pressed onwards into combinatorics! We defined something called "chooses", which are quick notational devices for representing numbers which appear quite often in counting. In particular, what we called "n choose k" represents the number of ways of choosing collections of k things from a larger collection of n distinguishable things.
I was again impressed with how well the homework went! We had well-delivered presentations on all four homework problems, including a lot of enthusiasm for wanting to present. One technique which was presented may be useful again for a problem on this week's homework: specifically Thomas' "books and shelves" argument for the Yahtzee problem (what I called "stars and bars").
This homework for this week is posted online. It only has three questions, but these are types of questions that deserve some extra thought and care, so some of them are worth more points than usual. I expect some awesome solutions.
When writing up solutions, don't forget that you *do not* want to delve into the actual gross algebraic definition of "chooses". This definition involves three separate factorials and can get unwieldy. Instead, focus on finding bijective proofs like we practiced in class. That is, if you want to prove that two expressions are equal, prove that they both represent the number of ways of doing the same thing.
The winning team this week is the Giant Iron Potatoez (Conrad, Lara, and Nate) with 33 points. Those homework problems this week are worth a bunch of points, so there's a great chance to build up points next week!
As always, please email me if you have any questions at all!
The first thing I want to make sure I mention is that our very own UW Math Circle has been featured in the College of Arts and Sciences newsletter, Perspectives. You can check out the full article here!
Math Circle has started back in full force for the quarter! In the first class of the year we learned about a mathematical formulation of a mini computer called an automaton. We constructed automata which can accomplish all sorts of surprising tasks! In the homework we tested the limits of these simple machines.
Yesterday we started moving away from the theory of computation. We're leaving the world of automata and formal grammars behind, but we may revisit it in the form of Conway's Game of Life at a later date. The next major topic is combinatorics -- a fancy word that mathematicians use for "counting". I was happy to see that a lot of the students have seen some combinatorial techniques before. We're going to learn fantastic new techniques for coating all sorts of things -- inclusion-exclusion, recurrence relations, and stars-and-bars to name a few.
In presenting the homework questions on automata, we had great class participation, including a complete solution to Problem 4 through fun some tag-teaming. The homework for this week includes some combinatorial exercises, and I'm excited to see this same level of engagement in future homework presentations!
The winning team this week is the KLRful Cuttlefish (Kyle, Lola, and Ruta) with 20 points! Total points of all teams can be found on the website, along with the homework and the two worksheets from class.
Lastly, I really want to reiterate just how much I enjoyed all the class participation I saw yesterday. I had a really fun time!
I'll start off with some information. Next week, 12/15, is the last Math Circle session this quarter. Therefore, the new worksheet (posted online) that was given out yesterday will not be discussed until January, so there is plenty of time to think about the problems. Instead, to celebrate, we will hold a fun group problem-solving game together with the 7th grade circle. Afterwards, we will count up all the team points and give out awards and prizes! Please plan on us finishing about 30 minutes later than usual.
Also, there might be a photographer for the UW College of Arts and Sciences newsletter at the next class. If there are any photos of your child that the newsletter would like to use, we'll contact you to request a photo release form beforehand. Please let us know before class if you object to being photographed.
Yesterday, we worked on more challenging problems about formal grammars and languages. It's great that everyone is having fun "decoding" formal rules into English descriptions of patterns. One of the problems from last time that was discussed on Thursday was about finding what was generated by the rules S->SS, S->aSb, S->ab. Conrad gave a great explanation about how to figure out whether any given string of a's and b's could be generated. Then we realized that the problem could be made even simpler by thinking of an 'a' as a '(' and of a 'b' as a ')'! Then, the language would contain exactly those sequences of opening and closing parentheses that had the parentheses matched "correctly".
Something that came up often in the discussion of the homework was that when we define a grammar, we must say precisely four things:
So, if we want to talk about the words generated by some new grammar, we must make clear what the states are, what the letters are, and what we start with -- not just the rules we can use to get there.
Congratulations to the Pythagorean Penguins and the Null Set, winners for this week with 30 points.
Again, please let us know if you have any concerns about the use of photographs.
We hope to see everyone there next Thursday.
On Thursday we started into the world of formal languages and grammars -- mathematical models for their real-world counterparts. One application besides that of studying the mathematical core of "language" is that this is a useful mindset for developing parsers for computers, e.g. for realizing that (4+3)*15 makes sense but *5(+()4 does not. Next week we'll be focusing mainly on this perspective by generating languages for different classes of robots.
The two worksheets from this week are posted online. These worksheets show how this formal grammar concept can also be used to understand the generation of certain secret codes. The homework this week is also posted online. Problem #1 on the homework refers only to Problem #9 from the Hacking worksheet and Problem #3 on the Generating worksheet. When doing the homework, remember that using grammars to generate languages is just like a game: from the start state S, follow the rules of the game to see all the places that you can end up!
This week there were no presentations on the board. Instead, we spent a lot of time in teams playing through the worksheets. Because of this, there weren't many points earned, and so there is no declared winning team this week. As always, the total team scores are on the website. Next week (12/8) is the actually the last chance to earn points for your team, since the last day of class is 12/15, where we'll officially declare the winners! So hopefully all that groupwork that we had yesterday can be used to help pull your team points up to where you want them!
A serious note to students: it is clear that many of you are not doing any of the homework problems, and this is reflected in your team point totals. If you ever have any questions or comments, I am completely open by email! Let me know what you're thinking!
Next week is Thanksgiving, and so we will not have Math Circle. Our next meeting is on Thursday, December 1. We will also have class on December 8, and then the last class of this quarter will meet on Thursday, December 15.
Since we finished up induction today, there is no homework over the Thanksgiving break. At our next meeting we'll start right in at the beginning of class with a new subject: formal languages and grammars. I just introduced this idea at the end of class today; we'll make everything crystal clear next meeting. One way to think of this topic is as trying to unambiguously say exactly what the correct syntax is for a certain given code (be it a secret government code, a secret software key, or even the correct way of writing algebraic expressions that make sense syntactically). In fact, one worksheet next class will have the students decoding some collections of secret keys into everyday language, and conversely encoding some infinite collections of keys into these formal grammars.
There are two winning teams this week, both tied with 24 points: The Pythagorean Penguins (Cynthis, Nate, Ruta, and Thomas), and the Random Llamas (Eli, Joshua, Katrina, Kyle, and Ted). There are only two more classes left in which to earn points, so if you're not where you want to be, now is the time to step up!
Have a fun break, and I'll see you in two weeks!
Once again, it's important to remember that when proving by induction, one must show both the base case (the SPARK -- the statement for a small, simple case) and the induction step (that if it's true for any number, it's also true for the next number). Today, we also had some problems where there were several base cases. In the problem about cutting a square into many squares, Kyle ingeniously showed how to cut it into 6, 7, or 8 squares, and then noticed that if a square can be cut into n pieces, one can take any little square and divide it into fourths to make n+3!
In the second half of the class, there was a group worksheet on induction. We had time to go over the first problem in class -- it asked to show that if many circles are drawn on a plane, then the resulting regions can be painted in two colors so no two adjacent regions have the same color. It took us some time before someone pointed out that this was actually the same problem as the one from the first-day Olympiad -- when we add a new circle, we can simply swap all the colors on the inside, and the new coloring will work.
There's also a new homework assignment, posted online, with a few algebraic induction problems and a fun one about cutting a chessboard. Also, since the new homework is relatively short, we'd like the students to think about the problems their groups didn't finish in class, which we'll discuss next week. #4, about the rover, is a particularly important example.
Congratulations to the Pythagorean Penguins (Cynthis, Nate, Ruta, and Thomas) for again earning the most (26) points today! The Null Set (Akhi, Lola, Nathanial, and Tiffany) are currently in the lead with 83 total points.
Have a great three-day weekend!
Problem 4 on our last homework concerned paying 7 days rent with only 3 pieces of silver. Lola gave a fabulous presentation of this problem, perfectly laid out and explained on the board! A generalization of this problem led us into the concept of mathematical induction. Induction is a two-step proof technique which can be useful for proving certain statements about positive integers. The first step I like to think of as setting up a FUSE which links each problem statement to the next one. This FUSE says that if the problem statement is true for the integer k, then it's also true for the integer k+1. That is, if it's true for 1, then it's also true for 2, and therefore also for 3, and so on. The second step is sometimes called the base case; I like to call it the SPARK. This is when we prove the problem statement for a first simple case. This SPARK ignites the FUSE, and explodes the truth down the chain of implications.
We spent a while in class proving the generalization to the silver question by induction. All those k's and (k+1)'s floating around are *really* hard to follow on the board, so be sure to re-take a look at your notes and email me if you have any questions! This generalization is pretty cool, though, so it was important to see the proof all written out. Thomas brought up a point about binary today -- those interested among you can try to think about how this same generalization about pieces of silver can be used to prove that any integer can be represented uniquely in binary (with just 0's and 1's).
There was an induction handout passed out at the end of class, too. Look it over, and if you have any questions be sure to email me and ask. The homework this week is a lot of practice in induction, so the techniques shown on that handout and in class will be relevant to presenting some of the homework problems next week!
The winning team for this week is The Pythagorean Penguins: Cynthis, Nate, Ruta, and Thomas with 28 points! As always, the complete point totals are available on the website. Next week we have four homework problems: each team (except the Null Set -- sorry guys!) will be given precisely one problem to present. *All* teams will still have the chance to earn points by paying attention to the presentations and finding major errors. And we instructors will be randomly choosing the presenter from each group :)
The students presented homework solutions on Hilbert's infinite hotel most of the class time. The homework due next week has a few more problems exploring the infinite, and we'll start a new topic (formal languages!) in the last half of next class.
One thing I hope the students were able to take away from the presentations yesterday is that NONE OF THIS IS EASY. By virtue of this, intuitive-sounding arguments are a good place to kick off on solving a problem; but a full solution MUST consist of rigorous explanations which do not require hand-waving. Nearly every single presentation in class yesterday had at least one point which was justified with "Here are some examples, and it must work the same for all other cases". Kolya was able to show us at least in one case how such an argument is quite dangerous! In writing up the solutions for this week, make sure you stay away from hand-waving!
The winning team for this week is The Null Set: Akhilan, Lola, Nathanial, and Tiffany with 33 points! The complete point totals can be found on the website. Next week I will be looking for solutions mainly from the Pythagorean Penguins and the Random Llamas -- and make sure those solutions are complete, because the other teams are going to try to fill in the gaps for a piece of the points-pie!
We had some great answers from the students related to the open-ended homework question about the relative sizes of infinite sets. These served as the starting point for the second half of class, which we spent playing through a worksheet on infinity -- it's much larger than you think (just ask the students)! Specifically, the Math Circle teams served as consultants for David Hilbert's hotel with infinitely many rooms. The homework for this week (due next Thursday) is to finish up all those problems on the Hilbert's Hotel worksheet (Problems 2,4,5,6,7) found here. Hilbert needs his consultants' help! I look forward to hearing some inventive solutions next week.
This week the teams and individual students started earning points based (mainly) on their homework presentations. The winning team for this week is The Random Llamas: Eli, Joshua, Katrina, Kyle, and Ted with 23 points! And the competition is fierce: the teams all range between 17-23 points! The point totals will accumulate throughout the year, and the winning team will be rewarded at the end of the quarter, when we'll switch up teams again for the next quarter. Each week will also have a winning team based solely on the performance of that class day, and I'll announce said team in each week's update. So keep up the good work teams -- the competition is on!
The homework and worksheets will always be posted on the 8th-grade Math Circle website, so be sure to check there even if you weren't able to make it to class. Note that on this week's homework, we've decided to omit problem 3 -- don't worry about it!
The students in the class have now been formed into teams of 4. If you were not able to make it to class yesterday, don't worry: we'll sort your team situation out next week. The teams formed on Thursday are:
Beginning next week, the teams will start earning and building up points! Points will be given for answering and forming questions -- overall involvement. But mostly, the homework is a major place to earn points, so make sure you've gone through all the problems for next week! Email me or Kolya if you have any questions about the homework; we're here to help.
Next week we will start with a 5-minute review of last week, and then the students will earn points by presenting the homework problems on the board and by making sure the presenter has thoroughly justified all his or her reasoning! We'll then pick up where we left off with infinite sets!
See you next week, teams!