Each of 17 students talked with every other student. Each pair of students talked about one of three different topics. Prove that there are three students that talked about the same topic among themselves.
Posts Tagged ‘graph theory’
Metroplex Math Circle will start its 2011-12 sessions with our own Radu Sorici! This session should be very interesting for students beginning to work on computer programming or accomplished coders who want a better understanding of the mathematical principles behind their work.
In this session Radu will discuss some elementary mathematics that are useful for computer science. Some of the topics covered: logic notation, methods of proof, sets, graph theory, counting principles, etc. In addition, we will look at some real world applications of the topics discussed.
A good friend of the Metroplex Math Circle, Dr. Arthur Benjamin, has just released a new lecture course through the Teaching Company titled “Discrete Mathematics.” We have our pre-ordered copy and its seems to have the unique combination of humor and depth that we know from Dr. Benjamin’s excellent “mathemagic” presentations.
For any students just starting with Math Circles, they will benefit greatly from becoming familiar with the topics on these DVDs: number theory, combinatorics and graph theory.
Here is the description of the course from the Teaching Company:
Welcome to Discrete Mathematics, a subject that is off the beaten track that most of us followed in school but that has vital applications in computer science, cryptography, engineering, and problem solving of all types.
Most of the mathematics taught after elementary school is aimed at preparing students for one subject—calculus, which is the mathematics of how things grow and change continuously, like waves in the water or clouds in the sky. Discrete mathematics, on the other hand, deals with quantities that can be broken into neat little pieces, like pixels on a computer screen, the letters or numbers in a password, or directions on how to drive from one place to another.
While continuous mathematics resembles an old-fashioned analog clock, whose second hand sweeps continuously across a dial, discrete mathematics is like a digital watch, whose numbers proceed one second at a time. As a result, discrete mathematics achieves fascinating mathematical results using relatively simple means, such as counting.
Explore this modern realm of digital math in Discrete Mathematics, 24 mind-expanding lectures by veteran Teaching Company Professor Arthur T. Benjamin, an award-winning educator and mathemagician who has designed a course that is mathematically rigorous and yet entertaining and accessible to anyone with a basic knowledge of high school algebra.
Next Saturday we are pleased to have Brian Basham join us to give a lecture that will touch on conditional probability and graph theory. Brian is well known to many of the country’s top problem solvers as a teaching assistant at both AwesomeMath and IdeaMath. Brian is currently a mathematics major at MIT and like many of our speakers may share his experiences of getting into and studying at a top tier university. Brian’s other accomplishments include:
- Two time USAMO qualifier
- MOSP qualifier 2007
- 1st Place HMMT Combinatorics Subject Test 2008
- AMC 10 Perfect Score 2005
Brian describes the content of his lecture in this way:
A quest to defeat the cannibals that inhabit my favorite math problem. Our journey will start with conditional probability and what it has to with medical diagnoses. We will travel into graph theory and learn how turning people into points can make problems much easier to solve. Finally we discover a concept in computer science which will help us claim victory over the cannibals and keep us from becoming dinner.
Like many of our lectures, Brian’s talk should be accessible to novice problem solvers but challenging to even the most experienced.
Here is an outline of Dr. Alexey Root’s talk 1/31/09 at the Metroplex Math Circle. Please note that we will accept answers for number 6 (the mobility calculation for the King, Queen, Rook, Bishop, and Knight) in the comment section below since Dr. Root did not have a chance to go over the answer to that problem.
1. Dr. Root began with the Knight’s Tour, based on her knight’s tour lesson plan on pages 62-63 of Children and Chess: A Guide for Educators. She was very impressed that Jeffrey Garrity, a math major from the University of Dallas (Irving, Texas) solved it on his first try.
2. Dr. Root had those who played tournament chess and those who knew en passant stand in the front of the room. Those who didn’t have that chess experience stayed seated. Volunteers counted the number of people in each part of the room which lead into a practical math problem of how to group those in attendance so that each group would have one tournament (or en passant-knowledgeable) player.
3. Everyone sat back down in their new groups, as indicated in 2. above.
4. Dr. Root gave an introduction to the role of domination in graph theory and in chess (quoted from her Science, Math, Checkmate: 32 Chess Activities for Inquiry and Problem Solving, pages 37-38 )
5. Dr. Root taught two chess/math activities. These are domination activities from Science, Math, Checkmate: 32 Chess Activities for Inquiry and Problem Solving (SMC):
A. Covering the Board: Rooks (pp. 38-42)
B. Covering the Board: Kings (pp. 42-45)
6. Dr. Root began the Mobility Lesson from pages 79-80 of her Children and Chess: A Guide for Educators. Mobility also has to do with the concept of dominance (coverage of squares). Students calculated the mobility of each piece from the corner and from the center. For example, a queen on an outside edge square can move to 21 squares, but if she is on a central square she can move to 27 squares. What is her average mobility? What is a rook’s average mobility? And so forth for each piece. The pawn is tricky because it moves one way and captures a different way, so you don’t have to calculate the pawn’s mobility unless you want to. Then figure out how this mobility relates to the traditional values listed for the chessmen: P(pawn)=1, N (knight)=3, B (bishop)=3, R(rook)=5, Q(queen)=9, K(king)=infinite but actually around 3.5-4. The answers to this mobility lesson were still being calculated at 4:10 p.m., when the Metroplex Math Circle wrapped up for the day. Please post your answers in the comments section below.
Dallas, TX, January 31, 2009. Dr. Alexey Root will present on chess applications of graph theory to secondary math education. She will highlight the concepts of domination and independence and show how they can be illustrated through chess problems. “The concept of domination is one of the central ideas in graph theory, and is especially important in the application of graph theory to the real world” according to Watkins in Across the Board: The mathematics of chessboard problems. Dr. Root’s lecture will be held on January 31st at 2:00 PM in room 2.410 of the Engineering and Computer Sciences Building (South), at the University of Texas at Dallas.
Dr. Alexey Root has a Ph.D. in education from UCLA. Root has been a tournament chess player since she was nine years old. Her most notable chess accomplishment was winning the U.S. Women’s championship in 1989. She also holds the title of Women’s International Master. Since the fall of 1999, Root has been a senior lecturer at The University of Texas at Dallas (UTD).
From 1999-2003 Dr. Root was the Associate Director for the UTD Chess Program, the number one college chess team in the U.S. Root’s current assignment for UTD is to teach education courses that explore the uses of chess in classrooms. Her courses are available worldwide, via the UT TeleCampus online platform. Her books are Children and Chess: A Guide for Educators (2006), Science, Math, Checkmate: 32 Chess Activities for Inquiry and Problem Solving (2008), and Read, Write, Checkmate: Enrich Literary with Chess Activities (2009).
In Dr. Alexey Root’s presentation, participants will try two domination activities from her books: Mobility (Children and chess: A guide for educators) and Covering the Board: Kings (Science, math, checkmate: 32 chess activities for inquiry and problem solving). Participants will also solve the eight-queens problem (Science, math, checkmate: 32 chess activities for inquiry and problem solving). The eight-queens problem highlights the concept of independence.