## Tuesday, May 9, 2017

### 5/9 Dating for Elementary Students

Today was a special Math Club session. Annie Raymond from the UW Math dept. came and gave a talk to the combined fourth and fifth graders on the topic of combinatorics. So I had the unusual opportunity to act as a photographer more than a facilitator. We started with me asking the kids if they had any initial questions. There were few basic ones like "How do you spend your days?"  Answer: teaching a lot of the time and thinking about research in between.

Annie went a bit bold and chose to talk about the Stable Marriage Problem which is right up my alley as a computer developer. I was a little worried we'd end up with a lot of nervous laughter and asymmetric interest from the boys and girls but the kids exceeded my expectations and were very attentive and engaged.

The kids did a great job calculating the total number of combinations was 3! at this point.

In the middle she brought an interactive version of the algorithm to test out. There were ~10 boy and girl preference sheets handed out. She then had the kids work through the algorithm in rounds with the boys going to their next choices and the girls picking the top selection. Much amusement and chatter soon followed.  This would be fun to do as an ordinary combinatorics exercise on its own.

What's very nice is there is a not too complicated proof by contradiction that the algorithm works. That fit really well with our recent session on proofs. http://mymathclub.blogspot.com/2017/04/418-series-infinite-series.html

Then we observed that the algorithm is asymmetric (with the kids volunteering if they got a good "match") its much better to ask than to choose partners.

Variants you could build more extensions on. She didn't bring it up but I thought a bit about complexity as a tangent. I think the algorithm is O(n^2) for instance in the worst case where everyone has the same preferences. Could this be optimized?

Overall I think this was a grand success with the kids and I'm hoping I can continue this relationship with the UW Math folks next year.