SUPERSET: A (Super) natural variant of the card game SET

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Downloads (Pure)

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 F4 3, 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 F3, we show that this number is Ω(1.442d) and O(1.733d). 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.

Original languageEnglish
Title of host publication9th International Conference on Fun with Algorithms, FUN 2018
EditorsHiro Ito, Stefano Leonardi, Linda Pagli, Giuseppe Prencipe
PublisherDagstuhl
Pages12:1-12:17
Number of pages17
ISBN (Electronic)9783959770675
DOIs
Publication statusPublished - 1 Jun 2018
Externally publishedYes
Event9th International Conference on Fun with Algorithms, FUN 2018 - La Maddalena Island, Italy
Duration: 13 Jun 201815 Jun 2018
Conference number: 9

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume100
ISSN (Print)1868-8969

Conference

Conference9th International Conference on Fun with Algorithms, FUN 2018
Abbreviated titleFUN 2018
CountryItaly
CityLa Maddalena Island
Period13/06/1815/06/18

Keywords

  • Affine geometry
  • Cap set
  • Card game
  • Computational complexity
  • SET
  • SUPERSET

Fingerprint Dive into the research topics of 'SUPERSET: A (Super) natural variant of the card game SET'. Together they form a unique fingerprint.

Cite this