Document Open Access Logo

SUPERSET: A (Super)Natural Variant of the Card Game SET

Authors Fábio Botler, Andrés Cristi, Ruben Hoeksma, Kevin Schewior, Andreas Tönnis

PDF
Thumbnail PDF

File

LIPIcs.FUN.2018.12.pdf
  • Filesize: 0.52 MB
  • 17 pages

Document Identifiers

Author Details

Fábio Botler
  • Universidad de Valparaíso, Valparaíso, Chile
Andrés Cristi
  • Universidad de Chile, Santiago, Chile
Ruben Hoeksma
  • Universität Bremen, Bremen, Germany
Kevin Schewior
  • Universidad de Chile, Santiago, Chile
Andreas Tönnis
  • Universidad de Chile, Santiago, Chile

Funding

This research was supported by Millenium Nucleus Information and Coordination in Networks (ICM/FIC RC 130003). Moreover, the first author was supported by CONICYT/ FONDECYT/POSTDOCTORADO 3170878, and the last two authors acknowledge support from CONICYT grant PCI PII 20150140.

Cite As Get BibTex

Fábio Botler, Andrés Cristi, Ruben Hoeksma, Kevin Schewior, and Andreas Tönnis. SUPERSET: A (Super)Natural Variant of the Card Game SET. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FUN.2018.12

Abstract

We consider Superset, a lesser-known yet interesting variant of the famous card game Set. Here, players look for Supersets instead of Sets, that is, the symmetric difference of two Sets that intersect in exactly one card. In this paper, we pose questions that have been previously posed for Set and provide answers to them; we also show relations between Set and Superset.
For the regular Set deck, which can be identified with F^3_4, we give a proof for the fact that the maximum number of cards that can be on the table without having a Superset is 9. This solves an open question posed by McMahon et al. in 2016. For the deck corresponding to F^3_d, we show that this number is Omega(1.442^d) and O(1.733^d). We also compute probabilities of the presence of a superset in a collection of cards drawn uniformly at random. Finally, we consider the computational complexity of deciding whether a multi-value version of Set or Superset is contained in a given set of cards, and show an FPT-reduction from the problem for Set to that for Superset, implying W[1]-hardness of the problem for Superset.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Fixed parameter tractability
Keywords
  • SET
  • SUPERSET
  • card game
  • cap set
  • affine geometry
  • computational complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Gary Antonick. The problem with SET. News Article. URL: https://www.nytimes.com/2016/08/22/crosswords/the-problem-with-set.html.
  2. Mark Baker, Jane Beltran, Jason Buell, Brian Conrey, Tom Davis, Brianna Donaldson, Jeanne Detorre-Ozeki, Leila Dibble, Tom Freeman, Robert Hammie, Julie Montgomery, Avery Pickford, and Justine Wong. Sets, planets, and comets. The College Mathematics Journal, 44(4):258-264, 2013. Google Scholar
  3. Michael Bateman and Nets Katz. New bounds on cap sets. Journal of the American Mathematical Society, 25(2):585-613, 2012. Google Scholar
  4. Jürgen Bierbrauer and Yves Edel. Bounds on affine caps. Journal of Combinatorial Designs, 10:111-115, 2000. Google Scholar
  5. BoardGameGeek. Set. URL: https://www.boardgamegeek.com/boardgame/1198/set.
  6. BoardGameGeek community. Variations on a Set. Forum thread. URL: https://boardgamegeek.com/thread/92588/variations-set.
  7. Sebastian Brandt. Personal communcation, 2014. Google Scholar
  8. A. R. Calderbank and P. C. Fishburn. Maximal three-independent subsets of 0, 1, 2ⁿ. Designs, Codes and Cryptography, 4(4):203-211, 1994. Google Scholar
  9. Kamalika Chaudhuri, Brighten Godfrey, David Ratajczak, and Hoeteck Wee. On the complexity of the game of Set, 2003. Manuscript. Google Scholar
  10. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  11. Brian Corney and Brianna Donaldson. SET. Classroom material. URL: https://www.mathteacherscircle.org/assets/session-materials/BConreyBDonaldsonSET.pdf.
  12. Ernie Croot, Vsevolod Lev, and Peter Pach. Progression-free sets in ℤ₄ⁿ are exponentially small. Annals of Mathematics, 185:331-337, 2017. Google Scholar
  13. Daniel. Answer at Mathematics Stack Exchange. URL: https://math.stackexchange.com/a/202863.
  14. Benjamin Lent Davis and Diane Maclagan. The card game set. The Mathematical Intelligencer, 25(3):33-40, 2003. Google Scholar
  15. Y. Edel, S. Ferret, I. Landjev, and L. Storme. The classification of the largest caps in AG(5,3). Journal of Combinatorial Theory, Series A, 99(1):95-110, 2002. Google Scholar
  16. Yves Edel. Extensions of generalized product caps. Designs, Codes and Cryptography, 31(1):5-14, 2004. Google Scholar
  17. Jordan S Ellenberg and Dion Gijswijt. On large subsets of 𝔽ⁿ_q with no three-term arithmetic progression. Annals of Mathematics, 185:339-343, 2017. Google Scholar
  18. R. Hill. On Pellegrino’s 20-caps in S_4,3. In Combinatorics '81 in honour of Beniamino Segre, volume 78 of North-Holland Mathematics Studies, pages 433-447. 1983. Google Scholar
  19. Raymond Hill. Caps and codes. Discrete Mathematics, 22(2):111-137, 1978. Google Scholar
  20. Erica Klarreich. A simple proof from the pattern-matching card game Set stuns mathematicians. News article. URL: https://www.wired.com/2016/06/simple-proof-card-game-set-stuns-mathematicians/.
  21. Donald Knuth. SETSET-RANDOM. CWEB program. URL: https://www-cs-faculty.stanford.edu/~knuth/programs/setset-random.w.
  22. Michael Lampis and Valia Mitsou. The computational complexity of the game of set and its theoretical applications. In Latin American Theoretical Informatics Symposium (LATIN), pages 24-34, 2014. Google Scholar
  23. Tom Magliery. Set variants. Personal Homepage. URL: http://magliery.com/Set/SetVariants.html.
  24. L. McMahon, G. Gordon, H. Gordon, and R. Gordon. The Joy of SET: The Many Mathematical Dimensions of a Seemingly Simple Card Game. Princeton University Press, 2016. URL: https://books.google.cl/books?id=8JojDQAAQBAJ.
  25. Roy Meshulam. On subsets of finite abelian groups with no 3-term arithmetic progressions. Journal of Combinatorial Theory, Series A, 71(1):168-172, 1995. Google Scholar
  26. Gu Pellegrino. Sul massimo ordine delle calotte in S_4,3. Matematiche (Catania), 25:149-157, 1971. In Italian. Google Scholar
  27. Aaron Potechin. Maximal caps in AG(6,3). Designs, Codes and Cryptography, 46(3):243-259, 2008. Google Scholar
  28. SET Enterprises, Inc. SET instructions. URL: https://www.setgame.com/set/puzzle_rules.
  29. Terence Tao. Open question: best bounds for cap sets. Blog post. URL: https://terrytao.wordpress.com/2007/02/23/.
  30. Terence Tao. A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound. Blog post. URL: https://terrytao.wordpress.com/2016/05/18/.
  31. The New York Times. Daily set feature. URL: https://www.nytimes.com/crosswords/game/set.
  32. Henrik Warne. SET card game variation – complementary pairs. URL: https://henrikwarne.com/2013/04/07/set-card-game-variation-complementary-pairs/.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact