This was another Riddle, posed by Ollie. The question was:
-
From a shuffled deck of 100 cards that are numbered 1 to 100, you are dealt 10 cards face down. You turn the cards over one by one. After each card, you must decide whether to end the game. If you end the game on the highest card in the hand you were dealt, you win; otherwise, you lose.
What is the strategy that optimizes your chances of winning? How does the strategy change as the sizes of the deck and the hand are changed?
So up to ten times you pick up a card from the deck and decide to ACCEPT or PASS it. The criteria for selection was:
- If it is the last card you must ACCEPT it
- If you PASSED a card larger than your current card then you must pass this (unless this violates rule #1)
- If there is a fifty percent chance or higher that all the consecutive cards are smaller then ACCEPT the current card (unless this violates rule #2)
The equation for determining if all the consecutive cards are smaller than the current card is:
where i is the index of the card you are evaluating (the first card would be 0, the second would be 1, etc.)
The result for the 10 card hand size, 100 card deck is that you can successfully determine the card 62.2% of the time. This changes with as follows:
varying hand size:
varying deck size (no apparent change):
#!/usr/bin/python import random import matplotlib.pyplot as plt import numpy deck_size = 100 threshold = 0.5 def make_hand(hand_size): got_hand = False while not got_hand or len(hand) != len(set(hand)): hand = [] for i in range(0,hand_size): hand.append(random.randint(1,deck_size)) got_hand = True return(hand) def run_hand(hand_size): hand = make_hand(hand_size) for i in range(0,len(hand)): decision = False skip_evaluation = False max_skipped_card = 0 percent_lowest = 1 saved_card = 0.1 #Skip immediately if you've skipped a larger card already if hand[i] < max_skipped_card: skip_evaluation = True #Skip if its the last card if i == len(hand)-1: saved_card = hand[i] skip_evaluation = True #Evaluate the % every consecutive card is lower if hand[i] > len(hand)-i and not skip_evaluation: max_skipped_card = max(max_skipped_card,hand[i]) for w in range(1,len(hand)-i): percent_lowest = percent_lowest * ((hand[i]-w-i)/(deck_size-i-w)) if percent_lowest > threshold: decision = True saved_card = hand[i] break return saved_card == max(hand) def run_trial(hand_size,deck_size,iterations): successful_trials = 0 for i in range(0,iterations): successful_trials = successful_trials + run_hand(hand_size) return [deck_size,(successful_trials / iterations)] results = [] for i in range(2,20): results.append(run_trial(10,i*10,100000)) x, y = zip(*results) plt.plot(x,y) plt.plot(x,y,'ko') plt.title('Pick A Card, Any Card! With Variable Deck Size\nThreshold: 0.5, Deck Size: 100') plt.ylabel('Correct Selection (%)') plt.xlabel('Deck Size') plt.ylim((0,1)) plt.show()
Pingback: Can You Solve These Colorful Puzzles? | A bunch of data