How to Introduce the Basis of Algorithmics? Thanks to the Enumeration and Composition of All Riffle Shuffles from a N Card Deck Used in MathMagic

Affiliation(s)

Art et Recherche NUMérique (ARNUM) Ecole Supérieure d’Informatique, d’Electronique et d’Automatisme (ESIEA) Paris, France.

Art et Recherche NUMérique (ARNUM) Ecole Supérieure d’Informatique, d’Electronique et d’Automatisme (ESIEA) Paris, France.

ABSTRACT

Why use magic for teaching combinatory, algorithms and finally informatics basis as tables, control structure, loops and recursive function? Magicians know that once the surprise has worn off, the audience will seek to understand how the trick works. The aim of every teacher is to interest their students, and a magic trick will lead them to ask ‘how?’ and ‘why?’ and ‘how can I create one myself?’ In this article we consider a project I presented in 2009, the subject of which was ‘How many riffle shuffles does exist from a N card deck? Find the composition of each possible riffle shuffle’. The aim of the paper is not only to describe the project scope, the students’ theoretical studies, their approach to this problem and their computer realizations, but also to give ideas for a course or project using pedagogy. That is why only remarkable students’ realizations are shown. In order to complete the given project, the students must answer three steps: the first one is to answer to the following question: “how can I find all possible riffle shuffles with few cards? (for exe*ample 3, 4 or 5 cards) the second one (to go further ) is to answer to the following question “how can I generalize this solution through an algorithm?” the last one (to obtain the results!) is to program the algorithm with a recursive and a non-recursive solution). Each step of the Matlab? solution code is associated with an informatics basis. Whatever the student's professional ambitions, they will be able to see the impact that originality and creativity have when combined with an interest in one’s work. That’s why, two ameliorations of the ‘basic’ algorithm are proposed and a study of the gain thanks to these ameliorations is done. The students know how to “perform” a magic trick for their family and friends thanks to the use of riffle shuffle in Gilbreath’s principles, a trick that they will be able to explain and so enjoy a certain amount of success with. Sharing a mathematical/informatics demonstration is not easy and the fact that they do so means that they will have worked on and understood and are capable of explaining this knowledge. Isn’t this the aim of all teaching?

Why use magic for teaching combinatory, algorithms and finally informatics basis as tables, control structure, loops and recursive function? Magicians know that once the surprise has worn off, the audience will seek to understand how the trick works. The aim of every teacher is to interest their students, and a magic trick will lead them to ask ‘how?’ and ‘why?’ and ‘how can I create one myself?’ In this article we consider a project I presented in 2009, the subject of which was ‘How many riffle shuffles does exist from a N card deck? Find the composition of each possible riffle shuffle’. The aim of the paper is not only to describe the project scope, the students’ theoretical studies, their approach to this problem and their computer realizations, but also to give ideas for a course or project using pedagogy. That is why only remarkable students’ realizations are shown. In order to complete the given project, the students must answer three steps: the first one is to answer to the following question: “how can I find all possible riffle shuffles with few cards? (for exe*ample 3, 4 or 5 cards) the second one (to go further ) is to answer to the following question “how can I generalize this solution through an algorithm?” the last one (to obtain the results!) is to program the algorithm with a recursive and a non-recursive solution). Each step of the Matlab? solution code is associated with an informatics basis. Whatever the student's professional ambitions, they will be able to see the impact that originality and creativity have when combined with an interest in one’s work. That’s why, two ameliorations of the ‘basic’ algorithm are proposed and a study of the gain thanks to these ameliorations is done. The students know how to “perform” a magic trick for their family and friends thanks to the use of riffle shuffle in Gilbreath’s principles, a trick that they will be able to explain and so enjoy a certain amount of success with. Sharing a mathematical/informatics demonstration is not easy and the fact that they do so means that they will have worked on and understood and are capable of explaining this knowledge. Isn’t this the aim of all teaching?

Cite this paper

Schott, P. (2012). How to Introduce the Basis of Algorithmics? Thanks to the Enumeration and Composition of All Riffle Shuffles from a N Card Deck Used in MathMagic.*Creative Education, 3,* 540-556. doi: 10.4236/ce.2012.34082.

Schott, P. (2012). How to Introduce the Basis of Algorithmics? Thanks to the Enumeration and Composition of All Riffle Shuffles from a N Card Deck Used in MathMagic.

References

[1] Aldous, D., & Diaconis, P. (1986). Shuffling cards and stopping times. The American Mathematical Monthly, 93, 333-348. doi:10.2307/2323590

[2] Ammar, M. (1998). The complete cups & balls. Tahoma, MA: L&L Publishing.

[3] Assaf, S., Soundararajan, K., & Diaconis, P. (2009). Riffle shuffles of a deck with repeated cards. 21st International Conference on Formal Power Series and Algebraic Combinatorics, Hagenberg, 20-24 July 2009, 89-102.

[4] Diaconis, P., Graham, R. L., & Kantor, W. M. (1983). The mathematics of perfect shuffles. Advances in Applied Mathematics, 4, 175-196. doi:10.1016/0196-8858(83)90009-X

[5] Diaconis, P. (1998). From shuffling cards to walking around the building. An introduction to markov chain theory. Proceedings of the International Congress of Mathematicians, 1, 187-204.

[6] Diaconis, P. (2003). Mathematical developments from the analysis of riffle-shuffling. In A. Fuanou, & M. Liebeck, (Eds.), Groups combinatorics and geometry (pp.73-97). Hackensack, NJ: World Scientific.

[7] Erdnase, S. W. (1902). The expert at the card table. Mineola, NY: Dover Publication.

[8] Gardner, M. (1958). Mathematics, magic and mystery. Mineola, NY: Dover Publication.

[9] Gardner, M. (2005). Martin Gardner’s mathematical games: The entire collection of his scientific American columns. Washington DC: Mathematical Association of America.

[10] Gilbreath, N. L. (1958). Magnetic colors. The Linking Ring, 3, 60.

[11] Gilbreath, N. L. (1966). Second Gilbreath principle. Linking Ring, June 1966.

[12] Gilbreath, N. L. (1989). Magic for an audience. Series of 3 Articles in Genii, 52.

[13] Huet, G. (1991). The Gilbreath trick: A case study in axiomatisation and proof development in the Coq Proof Assistant. Proceedings of Second Workshop on Logical Frameworks, Edinburgh, May 1991. doi:10.1017/CBO9780511569807

[14] Lachal, A., & Schott, P. (2012). Cartomagie: Principes de Gilbreath (I). Quadrature, 85, 24-35.

[15] Magid, A. (2005). Notices. Washington DC: American Mathematical Society.

[16] Mayol, H. (2000). La magie des cordes maestro. Gassaway, WV: HBM Production.

[17] Mulcahy, C. (2003). Fitch Cheney’s five card trick. Maths Horizon, 10.

[18] Mulcahy, C. (2004). Top 5 reasons to like mathematical card tricks. American Mathematical Society, 11,

[19] Mulcahy, C. (2007). An ESPeriment with Cards. American Mathematical Society, 14.

[20] Poincaré, H. (1912). Calcul des probabilités. Paris: Gauthier-Villars.

[21] Schott, P. (2009). The use of magic in mathematics: From primary school to higher education. Proceedings of ICERI2009 Conference, Madrid, 16-18 November 2009, 58-70.

[22] Schott, P. (2010). The use of magic in optics in higher education. Creative Education, 1, 11-17.

[23] Schott, P. (2011). How to introduce the cyclic group and its properties representation with Matlab? Thanks to Magic using the perfect Faro shuffle. Creative Education, 1, 27-40.

[24] Sheynin, O. B. (1991). H. Poincaré’s work on probability. Archive for History of Exact Sciences, 42.

[25] Xuereb, C., Clement, O., & Haddad, D. (2010). Le mélange américain. Projet IRI 5, Paris: ESME Sudria.

[1] Aldous, D., & Diaconis, P. (1986). Shuffling cards and stopping times. The American Mathematical Monthly, 93, 333-348. doi:10.2307/2323590

[2] Ammar, M. (1998). The complete cups & balls. Tahoma, MA: L&L Publishing.

[3] Assaf, S., Soundararajan, K., & Diaconis, P. (2009). Riffle shuffles of a deck with repeated cards. 21st International Conference on Formal Power Series and Algebraic Combinatorics, Hagenberg, 20-24 July 2009, 89-102.

[4] Diaconis, P., Graham, R. L., & Kantor, W. M. (1983). The mathematics of perfect shuffles. Advances in Applied Mathematics, 4, 175-196. doi:10.1016/0196-8858(83)90009-X

[5] Diaconis, P. (1998). From shuffling cards to walking around the building. An introduction to markov chain theory. Proceedings of the International Congress of Mathematicians, 1, 187-204.

[6] Diaconis, P. (2003). Mathematical developments from the analysis of riffle-shuffling. In A. Fuanou, & M. Liebeck, (Eds.), Groups combinatorics and geometry (pp.73-97). Hackensack, NJ: World Scientific.

[7] Erdnase, S. W. (1902). The expert at the card table. Mineola, NY: Dover Publication.

[8] Gardner, M. (1958). Mathematics, magic and mystery. Mineola, NY: Dover Publication.

[9] Gardner, M. (2005). Martin Gardner’s mathematical games: The entire collection of his scientific American columns. Washington DC: Mathematical Association of America.

[10] Gilbreath, N. L. (1958). Magnetic colors. The Linking Ring, 3, 60.

[11] Gilbreath, N. L. (1966). Second Gilbreath principle. Linking Ring, June 1966.

[12] Gilbreath, N. L. (1989). Magic for an audience. Series of 3 Articles in Genii, 52.

[13] Huet, G. (1991). The Gilbreath trick: A case study in axiomatisation and proof development in the Coq Proof Assistant. Proceedings of Second Workshop on Logical Frameworks, Edinburgh, May 1991. doi:10.1017/CBO9780511569807

[14] Lachal, A., & Schott, P. (2012). Cartomagie: Principes de Gilbreath (I). Quadrature, 85, 24-35.

[15] Magid, A. (2005). Notices. Washington DC: American Mathematical Society.

[16] Mayol, H. (2000). La magie des cordes maestro. Gassaway, WV: HBM Production.

[17] Mulcahy, C. (2003). Fitch Cheney’s five card trick. Maths Horizon, 10.

[18] Mulcahy, C. (2004). Top 5 reasons to like mathematical card tricks. American Mathematical Society, 11,

[19] Mulcahy, C. (2007). An ESPeriment with Cards. American Mathematical Society, 14.

[20] Poincaré, H. (1912). Calcul des probabilités. Paris: Gauthier-Villars.

[21] Schott, P. (2009). The use of magic in mathematics: From primary school to higher education. Proceedings of ICERI2009 Conference, Madrid, 16-18 November 2009, 58-70.

[22] Schott, P. (2010). The use of magic in optics in higher education. Creative Education, 1, 11-17.

[23] Schott, P. (2011). How to introduce the cyclic group and its properties representation with Matlab? Thanks to Magic using the perfect Faro shuffle. Creative Education, 1, 27-40.

[24] Sheynin, O. B. (1991). H. Poincaré’s work on probability. Archive for History of Exact Sciences, 42.

[25] Xuereb, C., Clement, O., & Haddad, D. (2010). Le mélange américain. Projet IRI 5, Paris: ESME Sudria.