Het probleem van 'set!'

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Plaats reactie
Set
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 25 aug 2015, 21:03

Het probleem van 'set!'

Bericht door Set » 25 aug 2015, 21:16

Tijdens een potje set vroegen wij ons af hoeveel kaarten je kan neerleggen zonder dat er een set in zit.
Bij het spelletje set is het de bedoeling dat je drie kaarten bij elkaar zoekt waarbij je let op vier eigenschappen.

1. de hoeveelheid(1,2,3)
2. de kleur (groen, rood, paars)
3. de vorm (ovaal, golf, rechthoek)
4. de vulling (leeg, gestippeld, vol)

Bij elk van deze vier eigenschappen moet je de volgende vraag stellen:
Is het precies gelijk of volledig verschillend?
Alleen wanneer elk van deze vier vragen met ja kan worden beantwoord heb je een set te pakken.
Er zitten 81 totaal verschillende kaarten in het spel.

Maar wij vroegen ons af hoeveel kaarten je neer kan leggen zonder dat daar een set in zit en hoe je dit kan berekenen.

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Het probleem van 'set!'

Bericht door arie » 27 aug 2015, 09:43

Volgens deze pagina zijn dat er 20:
http://www-cs-faculty.stanford.edu/~uno ... s/setset.w:
"A web page of David Van Brink states that you can't have more than 20 \SET/ cards without having a \SET/."
Met andere woorden: altijd als je 21 of meer kaarten hebt moet daar een SET in te vinden zijn.

Ze hebben dit bewezen door met een computer alle mogelijkheden na te gaan.

Een 20-tal kaarten waarin geen SET te vinden is, is bijvoorbeeld deze:
1111
1112
1121
1122
1211
1212
1221
1222
2111
2112
2123
2133
2213
2313
3123
3213
3221
3222
3233
3323

NOOT: elke kaart bestaat uit 4 cijfers, die de 4 achtereenvolgende eigenschappen coderen.
Bijvoorbeeld:
2213 = (hoeveelheid=2=2, kleur=2=rood, vorm=1=ovaal, vulling=3=vol)

Zelfs het met de hand nagaan van deze laatste bewering is al veel werk: uit deze 20 kaarten zijn



verschillende drietallen te kiezen, en geen enkele van deze 1140 drietallen mag een SET zijn.
Om aan te tonen dat geen enkele van die 1140 een SET is, zal je dit voor elk van de 1140 drietallen moeten controleren.

Set
Nieuw lid
Nieuw lid
Berichten: 2
Lid geworden op: 25 aug 2015, 21:03

Re: Het probleem van 'set!'

Bericht door Set » 27 aug 2015, 21:00

Hartelijk bedankt voor deze informatie! Nu ben ik er wel benieuwd naar of je hier ook zonder computer achter kan komen.

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Het probleem van 'set!'

Bericht door David » 28 aug 2015, 12:27

Voor elk paar Set-kaarten is er precies één kaart zodat de drie kaarten een SET vormen. Bijvoorbeeld, met de kaarten 1111 en 1123 kan alleen met 1132 een set worden gevormd. Dit geeft een andere methode om voor 20 kaarten te kijken of er een SET inzit;
Voor elk paar, kijk of de aanvullende kaart er is. Op die manier hoef je checks uit te voeren. Een kaart kan je buiten beschouwing laten. Als het een SET vormt met een paar, kom je dat paar tegen.
Set schreef:Nu ben ik er wel benieuwd naar of je hier ook zonder computer achter kan komen.
Een ondergrens is 2^4 = 16. Elke kaart heeft vier eigenschappen. Kies de kaarten met 1 of 2 voor elke eigenschap, dat zijn 2^4 kaarten, waarin geen SET zit.
Dit artikel (van Chan) geeft een andere methode voor het vinden van een ondergrens 20, http://www-personal.umich.edu/~charchan/SET.pdf.
Er wordt verwezen naar een bewijs dat 20 ook de bovengrens is, maar dat is ingewikkelder;
Charlotte Chan schreef:Because of the similarities between the proofs of Proposition 1 and Proposition 2, it
would seem reasonable to expect that the proof to verify that the maximum size of a 4-
cap is 20 would follow in a similar vein of thought. But in fact it doesn’t. The proof is
significantly more complicated and I will not present it here.
Er is een verwijzing naar dat bewijs onderaan het artikel. Daarin wordt ook het spel voor vijf, zes en zeven eigenschappen per kaart bekeken.

Zie ook http://oeis.org/A090245

Zo krijgt 20 wel mooie eigenschappen; 20 is ook het hoogste aantal zetten dat minstens nodig is om een 3x3x3 Rubiks kubus op te lossen.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

Plaats reactie