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 language | English |
---|---|
Title of host publication | 9th International Conference on Fun with Algorithms, FUN 2018 |
Editors | Hiro Ito, Stefano Leonardi, Linda Pagli, Giuseppe Prencipe |
Publisher | Dagstuhl |
Pages | 12:1-12:17 |
Number of pages | 17 |
ISBN (Electronic) | 9783959770675 |
DOIs | |
Publication status | Published - 1 Jun 2018 |
Externally published | Yes |
Event | 9th International Conference on Fun with Algorithms, FUN 2018 - La Maddalena Island, Italy Duration: 13 Jun 2018 → 15 Jun 2018 Conference number: 9 |
Publication series
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 100 |
ISSN (Print) | 1868-8969 |
Conference
Conference | 9th International Conference on Fun with Algorithms, FUN 2018 |
---|---|
Abbreviated title | FUN 2018 |
Country | Italy |
City | La Maddalena Island |
Period | 13/06/18 → 15/06/18 |
Keywords
- Affine geometry
- Cap set
- Card game
- Computational complexity
- SET
- SUPERSET