Mathematics can be a nuanced subject. Subtle differences in the context or wording of a problem can lead to drastic differences in complexity. I find this especially true with the topic of combinatorics. I remember the first time I taught a course including counting with combinations and permutations. I created a worksheet for my students with what I thought were some fairly straight forward questions. It turns out that some of the problems I created were much more complicated to solve correctly than I had intended. I learned from this mistake and was much more careful from then on. My son and I were recently playing with a roll of tickets (a great math manipulative as it turns out). This led to some questions that appeared similar but were quite different in complexity. I took the pictures below and posted them to twitter. Sharing CandyThe answer to the question on the right can be calculated with a single combination. You can use the "stars and bars" approach to think about the calculation required. First you have to decide if everyone gets a candy or not. If everyone gets at least one candy, then you can think of the problem as putting the twelve candies in a row (the "stars") and inserting 3 dividers in between them (the "bars") to divide the row into four sections. As an example, {★★★|★★|★★★|★★★★} would be one solution. Mathematically, there are 12 identical objects placed in 4 distinct bins, such that all bins contain at least one object. Given the 11 spaces between candies, how many ways are there to choose three of these spaces to place dividers. For the same situation, if you allow each person to receive zero candies, there are more possibilities. Using the same "stars and bars" approach, you can think of all twelve candies and the three dividers and being placed in a row. How many ways are there to do this? There are a total of 12+3 spaces and either a candy or divider is placed into each one. As an example, {★★||★★★★★★|★★★★} would be one solution. Ripping TicketsThe answer to the question on the left regarding tearing tickets is actually a much more complicated question than the one on the right despite appearing very similar. In this question, we are separating identical objects into identical bins. This means that {★★|★★|★★|★★★★★★} is the same solution as {★★|★★★★★★|★★|★★} since they are both three groups of 2 and one group of 6. This type of problem involves partition numbers and they have been studied by mathematicians such as Leonhard Euler, Srinivasa Ramanujan and more recently Ken Ono. Partition numbers are an open area of mathematics research. The solution for this problem is closely related to partition numbers. For every natural number n, its partition number, p(n), is defined as the number of ways we can write it as a sum of positive integers. For example, since the number 3 can be written as three different unique sums (1+1+1, 1+2 or 3), we say that p(3)=3. If we were looking for the total number of ways to partition the twelve tickets into any number of groups, our answer would be p(12) = 77 (from OEIS A000041). In our problem above however, we're looking for the number of ways to partition 12 into exactly 4 positive integers. We can do this either by counting with an organized list (brute force) or using recursion. For a description of the recursion method, see https://brilliant.org/wiki/identical-objects-into-identical-bins/.
Exploring Problem StructuresI recently tried out some problem sets from Craig Barton's SSDD problem website. SSDD stands for Same Surface, Different Deep Structure math problems. These are a set of problems (typically four) that have a very similar context but different solution strategies. The intent is for students to focus on determining the structure of each question and then to identify the corresponding strategy needed to solve it. I think this is an interesting routine for mathematics outcomes where there are a large variety of similar structures (like solving quadratics word problems or combinatorics problems). Michael Pershan wrote a blog post reflecting on the SSDD problem structure and how it might cause students to think in different ways. This type of reflection is why I write this blog and read other teachers blogs. Michael continued the conversation on Twitter and suggested that SSDD problems, “vary the deep differences while keeping the surface the same, and you draw attention to the way minor differences trigger different structure” I think that the type of Same and Different question prompt that I wrote about above also generates the same type of student thinking about the solution strategies required to solve a problem. I think that the SSDD structure could lead to a variety of similar question routines. For example, you could give students variety of questions but instead of answering them, they could be asked to group the questions together that share a similar solution strategy. Or perhaps, you could give students a general context and ask them to create several different questions from this context connected to a variety of mathematics topics (similar to a Notice and Wonder strategy). I think it is exciting to have so much collaboration and thoughtful conversation online between mathematics educators. Nova Scotia Mathematics Curriculum Outcomes Mathematics 12 P05 - Solve problems that involve permutations. Mathematics 12 P06 - Solve problems that involve combinations. EL
As a math teacher, I always love to see folks doing real math on television. Last week, on The Amazing Race Canada (Season 3, Episode 7), there was a 'tricky' mathematical challenge. Contestants were given a list of Air Canada flights and asked to create a flight plan using Air Canada destinations from around the world. They had to find a set of flights that had a total flight time of 25 hours (or 1500 minutes). They also had to ensure they used "a combination of routes that travel to at least three continents". Calculating the flight time was the first hurdle. Since arrival and departures are listed in local time and the vast majority of these flights crossed multiple time zones, contestants had to use the universal time code for each city to correct for time changes. A number of teams were confused right from the start (there was a lot of fixed mindset talk from the contestants). One team used an 'Express Pass' to skip this challenge while two other teams gave up and took a 2 hour time penalty instead of continuing with the challenge, That is a lot of flights! There are 12 flights listed on the Europe board, 11 flights on the Asia Pacific board and 15 flights on The Americas board. If we use just one flight from each board (so that we visit three continents), there are a total of 1980 combinations (12*11*15=1980). The rules state that we have to visit at least three continents but it doesn't say how many flight to use so we could have a flight plan with more than three flights. If we add one additional flight to make a flight plan with four flights, now we have 69300 possible flight plans (12*11*15*35=69300... one flight from each board and any one of the remaining 35 flights). That is a LOT of trial and error. The two solutions shown on the episode contained 4 flights. Are there any 3 flight plans that would work? Here is what I did.
First I got some screen captures of the flight boards so I could read all the flight times. Then I put them all into an Excel spreadsheet to calculate the flight times in minutes. Next I played with Excel for about an hour to try to find an efficient way to calculate all the combinations of flights that I wanted to try and then gave up. Instead, I created a quick program in Python to calculate all the possible sets with just three flight plans. This turned out to be much easier than using Excel (just 8 lines of code). AList=[924,731,635,1016,802,640,831,744,767,658,772] BList=[566,453,488,408,447,433,424,461,457,490,522,514] CList=[343,87,99,192,325,616,324,363,650,335,337,77,183,640,316] for i in AList: for j in BList: for k in CList: if i+j+k==1500: print 'Eureka!',i,j,k Now, assuming that I calculated the correct flight times in my Excel spreadsheet, this gave me three possible solutions: 1- AC025 Vancouver to Shanghai, AC824 Toronto to Amsterdam, AC541 Toronto to Seattle 731 + 453 + 361 = 1500 minutes 2- AC084 Toronto to Tel Aviv, AC898 Edmonton to London, AC962 Toronto to Bogota 635 + 522 + 343 = 1500 minutes 3- AC056 Toronto to Dubai, AC1904 Toronto to Edinburgh, AC1973 Halifax to Calgary 767 + 408 +325 = 1500 minutes The two solutions that were shown on the episode using four flights are below: AC480 Toronto to Montreal, AC918 Toronto to Miamai, AC882 Toronto to Copenhagen, AC007 Vancouver to Hong Kong 77 + 192 + 447 + 784 = 1500 minutes AC230 Vancouver to Calgary, AC541 Vancouver to Seattle, AC1910 Montreal to Nice, AC009 Calgary to Tokyo 87 + 316 + 457 + 640 = 1500 minutes
There was a nice article posted online that interviewed the Air Canada captain that handed out the clue cards for the challenge. He mentions the factors that he said made this such a challenging competition.
EL |
Categories
All
|