Riddler Express: Counting Marbles

A bag contains 100 marbles, and each marble is one of three different colors. If you were to draw three marbles at random, the probability that you would get one of each color is exactly 20 percent.

How many marbles of each color are in the bag?

Solution

If there are \(x\) of the first color and \(y\) of the second color, then there are \(100-x-y\) of the third color. There are \(x*y*(100-x-y)\) ways of selecting all three colors (disregarding order). This number needs to be equal to 20% of the total number of ways we can select 3 marbles. That number is \(\binom{100}{3}*0.2 = 161700*0.2 = 32340\).

Setting up a quick script, we can search for a solution for this problem.

for(x in 1:98){
   for(y in 1:98){
      if(32340-x*y*(100-x-y)==0){
         print(c(x,y,100-x-y))
         break
      }
   }
}
## [1] 21 35 44
## [1] 35 21 44
## [1] 44 21 35

We’ll need 21 of one color, 35 of another color, and 44 of the final color, totaling 100 marbles.

Riddler Classic

Riddler solitaire is played with 11 cards: an ace, a two, a three, a four, a five, a six, a seven, an eight, a nine, a 10 and a joker. Each card is worth its face value in points, while the ace counts for 1 point. To play a game, you shuffle the cards so they are randomly ordered, and then turn them over one by one. You start with 0 points, and as you flip over each card your score increases by that card’s points — as long as the joker hasn’t shown up. The moment the joker appears, the game is over and your score is 0. The key is that you can stop any moment and walk away with a nonzero score.

What strategy maximizes your expected number of points?

Extra credit: With an optimal strategy, how many points would you earn on average in a game of Riddler solitaire?

Solution

If I want to maximize my number of points, than before I draw a card I should ask whether or not drawing will maximize my expected number of points. I have a current score. Will my expected score after drawing a card increase or decrease this score? If it increases, I should draw. If it decreases, I should stay.

An exploration of this strategy will lead to the discovery that you need to draw at least 4 cards and a maximum of 7 cards, with a goal of 28 or more points. As soon as you hit 28 points, the expected score of another draw will drop.

To calculate the probability, I will find the probability distribution of scores after 4 draws first.

## A matrix of all possible selections of four cards out of the 11 
## the joker being zero

Draw4 <- t(combn(0:10,4))

## number of rows should match number of ways to select 4 from 11. 
nrow(Draw4) 
## [1] 330
choose(11,4)
## [1] 330
## eliminate rows with zero
Draw4 <- Draw4[!apply(Draw4, 1, function(x) return(0 %in% x)),]

## now look at a distribution of the row sums given we didn't draw a joker
Dist4 <- table(rowSums(Draw4))

With only 210 of the 330 rows left, we see there is a 120/330 chance of busting with the Joker in the first four draws. There is a 9/330 chance of a score of 28, 6/330 chance of a 29, and so on until 34. We’ll use Dist4 to help compute the expected value later.

If we eliminate all of the rows with a sum greater than 28 and keep those with rows less than 27 we’ll have the instances in which we’ll need to draw a 5th card.

Draw4 <- Draw4[which(rowSums(Draw4)<28),]
nrow(Draw4)
## [1] 183

So, there is a 183/330 chance we’ll have to keep drawing after 4. The next frame builds the possibilities of the 5th draw from these 183 (leaving out 0).

n4 <- nrow(Draw4)
Draw5 <- c()
for(r in 1:n4){
   for(k in (1:10)[-Draw4[r,]]){
      Draw5 <- rbind(Draw5,c(Draw4[r,],k))
   }
}
## Total number of possibilities including selecting a zero next.
nrow(Draw5) +183
## [1] 1281
## Number of possibilities without a zero next. 
nrow(Draw5)
## [1] 1098
## The distribution of possible sums.
Dist5 <- table(rowSums(Draw5))


## Keep those less than 28 for the next draw. 
Draw5 <- Draw5[which(rowSums(Draw5)<28),]
nrow(Draw5)
## [1] 630

There is a 1/7 chance (183/1281) that the next card will be a joker. If we look at the distribution of possible scores so far without having drawn the joker,

Dist5
## 
##  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32 
##   5   5  10  15  25  35  45  55  70  80  90  95 100 100  87  76  63  51 
##  33  34  35  36  37 
##  36  26  17   9   3

It looks like there are 630 possibilities that result in a score less than 28 (and would require another draw), while the latter 468 result in a score in which we stop. These have been removed from the matrix of possibilities (Draw5), and we can continue to Draw6.

n5 <- nrow(Draw5)
Draw6 <- c()
for(r in 1:n5){
   for(k in (1:10)[-Draw5[r,]]){
      Draw6 <- rbind(Draw6,c(Draw5[r,],k))
   }
}

## Total number of possibilities including selecting a zero next.
nrow(Draw6) +n5
## [1] 3780
## Number of possibilities without a zero next. 
nrow(Draw6)
## [1] 3150
## The distribution of possible sums.
Dist6 <- table(rowSums(Draw6))


## Keep those less than 28 for the next draw. 
Draw6 <- Draw6[which(rowSums(Draw6)<28),]
nrow(Draw6)
## [1] 810

There is a 1/6 chance that the next card picked is a joker given that the first five were not. This is also equal to 630/3780. Let’s look at the distribution of the remaining 3150 possibilities:

Dist6
## 
##  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37 
##  30  30  60  90 150 180 270 300 335 315 315 275 270 205 165 105  55

There are 810 draws that result in a score less than 28, which would require to draw a 7th card. We are now ready to build Draw7.

n6 <- nrow(Draw6)
Draw7 <- c()
for(r in 1:n6){
   for(k in (1:10)[-Draw6[r,]]){
      Draw7 <- rbind(Draw7,c(Draw6[r,],k))
   }
}

## Total number of possibilities including selecting a zero next.
nrow(Draw7) +n6
## [1] 4050
## Number of possibilities without a zero next. 
nrow(Draw7)
## [1] 3240
## The distribution of possible sums.
Dist7 <- table(rowSums(Draw7))

There is a 1/5 chance that the 7th drawn card is a joker given that the first six were not (same as 810/4050). Let’s look at the remaining distribution of scores after drawing 7.

Dist7
## 
##  28  29  30  31  32  33  34  35  36  37 
## 210 180 300 360 390 420 450 390 330 210

Now, we have what we need to compute the expected value.

E <- sum((28:34)*Dist4[19:25]/330) + 
   183/330*(sum((28:37)*Dist5[14:23]/1281) + 
               630/1281*(sum((28:37)*Dist6[8:17]/3780) + 
                            810/3780*(sum((28:37)*Dist7/4050))))

E
## [1] 15.4531

Simulation will confer. We build a function to compute the expected score of the next draw given a current score first.

expScore <- function(curScore, cardsLeft){
   k <- length(cardsLeft)
   PossibleScores <- curScore + cardsLeft
   ## Replace all possible scores that are equal to current score with 0. 
   PossibleScores[which(PossibleScores==curScore)] <- 0
   return(sum(PossibleScores)/k)
}

Now, use this to simulate a game.

RidSol <- function(N){ #input number of simulations
   Scores <- 0  ## accumulate all the Scores from the games
   for(p in 1:N){
      cards <- sample(0:10,11)  ## random ordering of cards
      play <- 1
      game <- cards[play]!=0  ## if first card is joker, no need to play
      curScore <- cards[play] 
      while(game){
         play <- play + 1  #iterate the play
         ## if your current score is less than the expected score 
         ## from drawing, we draw!
         if(curScore < expScore(curScore, cards[play:11])){
            game <- cards[play]!=0
            curScore <- ifelse(game, curScore + cards[play],0)
         }
         else{
            break
         }
      }
      ## Increment the Scores by curScore
      Scores <- Scores + curScore
   }
   ## Return the average
   return(Scores/N)
}

Let’s simulate 100,000 times a few times.

RidSol(100000)
## [1] 15.39802
RidSol(100000)
## [1] 15.45912
RidSol(100000)
## [1] 15.45068

The theoretical answer of 15.4531 looks legit!