Nathan Karst
  • Home
  • Teaching
  • Research

Berkeley and Perfectly Puzzling

3/21/2013

0 Comments

 
I spent the first part of the week in Berkeley visting my friend David who's out there studying applied mathematics in the context of hydrology. Not too surprisingly, we did quite a bit of mathematics. On a hike, we chewed over NPR's Perfectly Puzzling question of the week:
Eight people are seated at a circular table. Each person gets up and sits down again — either in the same chair or in the chair immediately to the left or right of the one they were in. How many different ways can the eight people be reseated?
Picture
Dave crushed this thing in two parts, and since NPR's solution was along the lines of "count 'em up" and didn't give a formula for the case when you have $n$ people at the table, I figured I'd write up his solution.

Let $C_n$ be the number of ways to seat $n$ people at a circular table according to the restrictions laid out in the problem statement. One hard thing to deal with here is the fact that the table is circular. Dave's first good idea was to break the symmetry. Without loss of generality, choose 2 adjacent people at the table. Now, in each valid configuration, either these two people switch places or they don't, and, most importantly, the remaining people can be thought of sitting in a line rather than a circle. Each case defines a subproblem that is really tractable. 

We define a new and related problem: how many ways are there to reseat $n$ people seated in a line such that each person switches either with their left-hand or right-hand neighbor or remains in their original spot? Define $L_n$ to be the number of ways to seat $n$ people according to these restrictions. Noting $L_1 = 1$ and $L_2 = 2$, we can go forward with induction. Suppose $L_k$ is known for $k < n$ and consider $L_n$. In each valid seating arrangement, either the $n^{th}$ person switches with her neighbor or she does not. In the case where she does not, her neighbor is unconstrained by her presence, and so there are $L_{n-1}$ ways to reseat the remaining $n-1$ people. In the case where she and her neighbor switch positions, the remaining $n-2$ are free to sit however they like subject to the rules in the problem statement, and so there are $L_{n-2}$ ways to reseat them. Assembling our cases gives $L_n = L_{n-1} + L_{n-2}$. Note that this means solutions to this subproblem are Fibonacci numbers! (Our indexing here is off by one, so that $L_n = F_{n+1}$ for $n \geq 1$.)

With this new result in hand, let's turn our attention back to the original problem. Recall that we arbitrarily chose a pair of adjacent people at the table. If the pair does not switch, then all $n$ people at the table are free to reorder themselves as if they were seated in a line. Thus, there are $L_n$ ways to reseat the table if the chose pair does not switch. If they do switch, the remaining $n-2$ people at the table are free to reorder themselves as if they were seated in a line, and so there are $L_{n-2}$ ways to reseat the table in this case. We also must account for the fact that the entire table can rotate either one seat to the right or one seat to the left. So the total number of ways to reseat the table is $C_n = L_n + L_{n-2} + 2$. 

With this new result in hand, let's turn our attention back to the original problem. Recall that we arbitrarily chose a pair of adjacent people at the table. If the pair does not switch, then all $n$ people at the table are free to reorder themselves as if they were seated in a line. Thus, there are $L_n$ ways to reseat the table if the chose pair does not switch. If they do switch, the remaining $n-2$ people at the table are free to reorder themselves as if they were seated in a line, and so there are $L_{n-2}$ ways to reseat the table in this case. We also must account for the fact that the entire table can rotate either one seat to the right or one seat to the left. So the total number of ways to reseat the table is $C_n = L_n + L_{n-2} + 2$. With a little massaging, we can get a statement for $C_n$ that is recursive. 
$$\begin{align*} C_n - C_{n-1} &= L_n + L_{n-2} + 2 - L_{n-1} - L_{n-3} - 2 \\
&= L_{n-2} + L_{n-4} \\
&= C_{n-2} - 2 \\
C_n &= C_{n-1} + C_{n-2} - 2.
\end{align*}$$
For base cases, we have $C_3 = 6$ and $C_4 = 9$. Sure enough, $C_8 = L_8 + L_6 + 2 = F_9 + F_7 + 2 = 34 + 13 + 2 = 49$, just as NPR claimed.  For a long list of values, see the OEIS page. 

Really nice proof, especially for one that Dave busted out while hiking. 

0 Comments

Karsts and miscible fluids

3/12/2013

0 Comments

 
My brother Casey just had a paper accepted to Physics of Fluids. It's a great publication and a great journal, especially for his first time out of the gate. From the abstract:
The paper describes a theoretical and experimental investigation of the laminar flow of two miscible Newtonian fluids of different density and viscosity through a simple network. The fluids stratify due to gravity and remain as nearly distinct phases with some mixing occurring only by diffusion. ... Once the phase separation at a single junction is known, a network model is developed which predicts multiple equilibria in the simplest of networks. The existence of multiple stable equilibria is confirmed experimentally and a criterion for existence is developed.
I especially love that they confirmed these all these experimentally. And while the plots are nice and clean, I know how hard and long Casey worked to get all those data. Rock on, brother.

The work Casey and his coauthors did is closely related to some more theoretical stuff I've been hacking away at for the past year or so. Hopefully spring break next week will give us a chance to finalize and submit. 
0 Comments

Midterms

3/7/2013

0 Comments

 
It's midterm season! This semester I'm teaching a section of applied calculus and quantitative methods and a section of linear algebra. In both classes, I'm doing a take-home exam with an oral exam at the end. During the week-long take-home phase, students can use any resource they like, including books, notes, the internet, each other, etc. I encourage them to work together. I typically give out several versions of the exam, all with different data used in each example. This is to encourage the students to talk about the problems in general terms and to discourage them from just copying from one another.

After the take-home phase, each student comes in for a 15 minute oral exam. We go over each problem on the exam. If the work they've submitted looks correct, I'll ask the student to walk me through how they approached the problem. If it sounds like they understand the work they've submitted (and haven't just copied a classmate's work) I ask the student to define, explain or clarify a particular concept in the problem and connect it to the problem as a whole. If they can manage this, the real fun starts. I'll tweak one of the conditions in the problem and ask them how the change will affect their answer. I don't ask them to re-solve the problem on the spot typically; I just want to know if they really see all the dependencies and interrelations between the concepts. 

I grade each problem on a 4 point scale with 4 being phenomenal work, and 0 indicating they couldn't even explain how they approached the problem. This also roughly corresponds to the A - F letter scale. Being able to talk your way through how you approached a problem gets you one point. Being able to clearly define, explain or clarify a chosen concept gets you another; this is C level understanding. The "tweak" usually occurs in two parts, an easier version and a harder version. Correctly answering gets you one point each. There are obviously shades of grey in all these, and I typically award partial credit in 1/3 point increments to make the +/- letter scaling work out well.

While I'm still working on the specifics, I love the take-home then oral exam model for a lot of reasons. I think it better simulates projects in the real world, both on time limits and collaboration. And with application-oriented students, connecting something to the business world gives you a ton of traction. One of my linear algebra students stated it really well (I'll paraphrase): "Taking a timed exam without resources or collaboration is like doing Mad Max mathematics." I couldn't agree more. 

Another reason I like the system is the fact that I get to see exactly what each student knows (and doesn't). I have a much better idea of where each of them is on their path to mastery than I used to. I've been genuinely surprised at the level of specificity we can resolve in 15 minutes. For instance, last semester during an oral exam I found out that a student understood everything about nonlinear optimization except evaluating endpoints of the domain. I'm not sure I would've got this level of understanding by looking at a printed exam. 

The last reason is that I can give much more challenging and interesting problems, because I can expect students to learn and teach each other over the course of the take home portion. 

My understanding so far of the student experience is that they're initially really nervous about the idea of an oral exam, which is new to most of them. But they eventually really warm up to the format. Last semester, I put the format of the final exam up to an anonymous vote in class: should it be a traditional exam of a take-home+oral exam? Over 90% of students (N=60) voted for the  nontraditional format. I don't think I could get 90% of them to agree on almost anything, so I took this as confirmation that something about this model was working for them.

For some examples, here's the midterm in applied calculus and the midterm in linear algebra. Notice in linear algebra I can use the midterm to preview things that we'll see more in depth later in the semester like multilinear and logistic regression. In calculus I can give them fairly gnarly 
0 Comments

    Archives

    June 2015
    May 2015
    February 2015
    December 2014
    October 2014
    September 2014
    August 2014
    July 2014
    May 2014
    March 2014
    February 2014
    January 2014
    December 2013
    October 2013
    July 2013
    June 2013
    May 2013
    April 2013
    March 2013
    February 2013
    January 2013

    Nathan Karst

    Doing and teaching mathematics. 

    Categories

    All

    RSS Feed

Powered by Create your own unique website with customizable templates.
Photo used under Creative Commons from ByoLogyc