Category: Combinatorics

Curt Cutting

This challenge is about cutting cards. And therefore about probability and combinatorics.

You have a deck of cards. For convenience, we’ll just use A-9 to have a nice round 40 cards. You cut some number of cards. At least one quarter and less than 3/4. That’s a neat 20 possible number of cards. To keep things simple, make them all have a probability of 5%. Now, from this cutting you cut a number of single cards, shuffling in between cuts of course. Formally, that’s random selection with replacement. At some point, you will cut a card that you have seen previously. At this point, you stop. This cuts short the data you receive about the deck of cards; you haven’t seen half of them. Of course, one can always estimate the remaining number of cards. So say you cut 10 cards before a repetition (11 cards total), and that for some reason you cannot visually approximate how many cards are in the deck. The challenge is to determine the expected number of cards in the deck.

The expected number of cards, to put it simply, is the “best” guess for how many cards are in the deck given your information. “Best” means minimizing the average difference between the actual number and your guess.

Solution

Scrupulist Square

This challenge is spans all the way from graph theory, geometry, and calculus—to algebra and combinatorics.

Example set of points for N = 15

Consider a square with diagonal 1. In it, N points are randomly arranged. A graph is created from these points, such that the probability any 2 points touch is equal to 1 minus their distance. Choose a point at random on this graph. The challenge is to calculate a probability regarding this point: what is the probability that a randomly selected node connected to this one is connected to more nodes? Each node has a loop, so if the node was connected to no other nodes the probability of this is 0. For N=1 or 2, this probability is 0. Try to calculate at least one of the following: chance for a specific N > 2, limit of chance as N approaches infinity, and most difficult, generalized probability in terms of N.

SOLUTION

Galvanizing Growth Python Simulation

import pandas as pd
from random import random
from math import floor, log
import matplotlib
from matplotlib import pyplot as plt
from numpy.random import normal
group = {}
growth = {}
countries = [('China', 137e7, 274e6), ('India', 127e7, 254e6), ('United States', 324e6, 648e5), ('Indonesia', 258e6, 516e5), ('Brazil', 206e6, 412e5), ('Pakistan', 202e6, 404e5), ('Nigeria', 186e6, 372e5), ('Bangladesh', 156e6, 312e5), ('Russia', 142e6, 284e5), ('Japan', 127e6, 254e5), ('Mexico', 123e6, 246e5), ('Philippines', 103e6, 206e5), ('Ethiopia', 102e6, 204e5), ('Vietnam', 953e5, 1906e4), ('Egypt', 947e5, 1894e4), ('Iran', 828e5, 1656e4), ('DR Congo', 813e5, 1626e4), ('Germany', 807e5, 1614e4), ('Turkey', 803e5, 1606e4), ('Thailand', 682e5, 1364e4), ('France', 668e5, 1336e4), ('United Kingdom', 644e5, 1288e4), ('Italy', 62e6, 124e5), ('Burma', 569e5, 1138e4), ('South Africa', 543e5, 1086e4), ('Tanzania', 525e5, 105e5), ('South Korea', 509e5, 1018e4), ('Spain', 486e5, 972e4), ('Colombia', 472e5, 944e4), ('Kenya', 468e5, 936e4), ('Ukraine', 442e5, 884e4), ('Argentina', 439e5, 878e4), ('Algeria', 403e5, 806e4), ('Poland', 385e5, 77e5), ('Uganda', 383e5, 766e4), ('Iraq', 381e5, 762e4), ('Sudan', 367e5, 734e4), ('Canada', 354e5, 708e4), ('Morocco', 337e5, 674e4), ('Afghanistan', 333e5, 666e4), ('Malaysia', 31e6, 62e5), ('Venezuela', 309e5, 618e4), ('Peru', 307e5, 614e4), ('Uzbekistan', 295e5, 59e5), ('Nepal', 29e6, 58e5), ('Saudi Arabia', 282e5, 564e4), ('Yemen', 274e5, 548e4), ('Ghana', 269e5, 538e4), ('Mozambique', 259e5, 518e4), ('North Korea', 251e5, 502e4)]
groupKeys = []
scale = 50
for i, j, k in countries:
  group[i] = [[0, j, 0, k]]
  growth[i] = [0]
  groupKeys.append(i)
group[groupKeys[0]] = [[13, countries[0][1]-13, 0, countries[0][2]]]
growth[groupKeys[0]] = [13]
e = 2.7183
def eDistribute(bottom, top, original):
  if(top == bottom):
    return top
  return top*e**((bottom-original)/(top-bottom))
def grow(sets, keys, past, index, spread=lambda a,b:1, expose=lambda a:1, expand=0.05, cut=5, spreadFactor=0.5, growthFactor=10):
  spreadSum = 0
  for i in keys:
    if(sets[i][index][0]+sets[i][index][1] == 0):
      adjExpand = 0
    else:
      adjExpand = expand * sets[i][index][1]/(sets[i][index][0]+sets[i][index][1])
    if(len(sets[i]) == index+1):
      sets[i].append([sets[i][index][0], sets[i][index][1], sets[i][index][2], sets[i][index][3]])
      past[i].append(0)
    for j in keys:
      if(i != j):
        currentSpread = spread(past[i], past[j])
        spreadSum -= currentSpread
        todaySpread = round(normal(1.5, 1)*eDistribute(0, spreadFactor, currentSpread)*sets[i][index][0]*expand)
        if(todaySpread > 0):
          if(len(sets[j]) == index+1):
            sets[j].append([sets[j][index][0]+todaySpread, sets[j][index][1]-todaySpread, sets[j][index][2], sets[j][index][3]])
            past[j].append(todaySpread)
          else:
            sets[j][index+1][0] += todaySpread
            sets[j][index+1][1] -= todaySpread
            if(sets[j][index+1][1] < 0):
              sets[j][index+1][0] += sets[j][index+1][1]
              sets[j][index+1][1] = 0
            past[j][index+1] += todaySpread
    currentSpread = expose(past[i])
    spreadSum -= currentSpread
    newGrowth = round(normal(1.5, 1)*eDistribute(0, growthFactor, currentSpread)*sets[i][index][0]*adjExpand)
    sets[i][index+1][0] += newGrowth
    sets[i][index+1][1] -= newGrowth
    past[i][index+1] += newGrowth
    if(sets[i][index+1][1] < 0):
      sets[i][index+1][0] += sets[i][index+1][1]
      past[i][index+1] -= sets[i][index+1][1]
      sets[i][index+1][1] = 0
    if(index >= cut):
      if(past[i][index-cut] > sets[i][index+1][0]):
        past[i][index-cut] = sets[i][index+1][0]
      sets[i][index+1][0] -= past[i][index-cut]
      sets[i][index+1][2] += past[i][index-cut]
  for one in sets:
    spreadSum += sets[one][index+1][0]
    if(sets[one][index+1][0] > sets[one][index+1][3]):
      spreadSum += 10*(sets[one][index+1][0]-sets[one][index+1][3])
  return spreadSum

impact = 0
impacts = {}
spreadFactor = 0.5
growthFactor = 1.25
meantime = 11
incperiod = 8
strictness = 100, 70
def adj(maxVal):
  def decorator(f):
    def wrapper(*args, **kwargs):
      raw = f(*args, **kwargs)
      if(raw < maxVal):
        return maxVal - raw
      return 0
    return wrapper
  return decorator
compensate = growthFactor*scale + spreadFactor*scale**2
def testAlgs(ban, close):
  i = 0
  impact = 0
  while i < 10:
    j = 0
    while i < 150:
      impacts[str(i)] = impact
      impact = floor(impact + compensate + grow(group, groupKeys, growth, i, spread=lambda a,b:ban(a, b, i-incperiod), expose = lambda a:close(a, i-incperiod), expand = 0.029, cut=meantime+incperiod, spreadFactor=spreadFactor, growthFactor=growthFactor))
      j += 1
  return impact / 10

Galvanizing Growth

This challenge on growth involves algebra, calculus, and some combinatorics.

Consider a pandemic outbreak. It begins with patient zero in a random country. For this challenge, only consider the countries with the 50 largest populations, rounded to four significant digits. Now, there are two ways the pandemic can grow. It can either expand within a country, or expand by travel to another country. There are then several methods to stop an outbreak: cutting travel, quarantining, and social distancing. The impact of a pandemic can be calculated by the net cost of these method, plus the cost of the sickness. Now, the more seriously we try to do any of these methods, the more costly and inefficient it will become. We express this with the first equation below for quarantine and social distancing, the second for travel restrictions. Now, let the expansion of a virus within a country be dictated by the third equation below, and the expansion between any two, the fourth. The cost of each case is then given by the fifth equation. The challenge is to find a general formula, given a segment of a countries net cases curve, to determine how much a country should enact social distancing, and how strictly it should quarantine victims. And another, complementary function, given curve segments for two countries, that will give the restriction on travel that the first should impose on the latter. The curves represent the data from an incubation period, x, ago, and this is randomly generated each pandemic be the sixth equation. They recover after a recovery time, y, given by the seventh. In the below equations, cn represents money spent on efforts in country n, in cost of cases in country n, pn is population, and r is random number 0 ≤ r < 1, different each time. anx gives the number of interactions between people, with an1 within a country, an2 between two. sn is the number of cases in country n, and gn is the number of new cases in that country from that country. gab is the number of new cases spread from b to a. Good luck! A python simulation of this has been published for you to test your strategy.

a_{n1}=125\ e^\frac{-c_n}{100}\\[8pt] a_{n2}=5\ e^\frac{-c}{5}\\[16pt] g_n=\left\lfloor a_{n1}s_n{\left({3-2\sqrt2\operatorname{erfc^{-1}}{(r)}\over200}\right)}\left(1-\frac{s_n}{p_n}\right)\right\rfloor\\[16pt] g_{a_b}=\left\lfloor a_{b2}s_b{\left({3-2\sqrt2\operatorname{erfc^{-1}}{(r)}\over200}\right)}\left(1-\frac{s_a}{p_a}\right)\right\rfloor\\[16pt] i_n=s_n+10\left(s_n-\frac{p_n}5+|s_n-\frac{p_n}5|\right)\\[16pt] x=5-3\sqrt2\operatorname{erfc^{-1}}{(2r)}\\[8pt] y=11-5\sqrt2\operatorname{erfc^{-1}}{(2r)}
SIMULATION
SOLUTION

Didactic Dice

Combinatorics is needed to solve today’s challenge.

Shown in the diagram to the right is the board for a dice game. The rules are as follows: start at the point. On your turn, roll 2 six sided dice. Move forward thet many spaces allong the path. The path is marked by the arrow and has 24 squares. If you reach the black square and have more moves, move back to the dot. You do not continue moving; your turn ends immediately. The first player to end exactly on the black square wins. You play this game with a friend. The challenge is to find the average number of turns the game will take. After 1 player wins, the other does not continue. This is very important.

solution

Complex Coins

You will need to use algebra and combinatorics to solve this challenge.

A normal coin has 2 flat sides and one thin round edge. When tossed, the coin always lands on a flat side. A brand new pencil has 2 small flat sides and 1 long round side. When tossed, the pencil always lands on the round side. Somewhere in the middle is the 3 sided coin, where all 3 sides are equally likely to be rolled. You happen to have 5 such 3 sided coins*. You call the 3 sides heads, tails, and round, or H, T, and R for short. You and your friend John a game with these coins. For every H, you get a point. For every T, John gets a point. But for every R, you both get a point. First to 5 points wins. You start playing, and roll 2 tails and a round. What is the probability that you win?

*Despite various lengthy efforts, nobody has been able to produce a perfect 3 sided coin as described in this challenge. So far. Some have come close, see “How thick is a three-sided coin?” from Standupmaths on Youtube, available below.

Solution

Recursive Renewals

You will need to do algebra, combinatorics, calculus, and trigonometry, and also use multiple matrices, to solve today’s challenge.

When you take a book out at the Leibniz Library, you must return it before the fine equation, f(x), rises above zero. If not, your fine is determined by the fine equation. The variable r represents the number of times you have renewed the book, beggining at zero. The variable d counts days and increases by 1 every day, beggining at zero. The variable t counts days and increases by 1 each day, beggining at 0. Each time you renew the book, the variable r in the fine equation, which begins at zero, increases by 1, and the variable t is reset to 0. You may not renew the book if someone else has it on hold or the fine equation is above 0. The probability that someone puts your book on hold on any given day is determined by the hold equation, h(x). How can you maximize the number of days you have with your book without paying anything?

f(x)=d^2+5d-7cos(r)+r^3-100\\[10pt] h(x)=\frac{t^2+3sin(t)+15}{100}
Solution

Peculiar Pets

You will need matrices and combinatorics to solve this challenge.

In a city with infinite people, there are only three types of pets. They are dogs, cats, and fish. 60% of people have a pet. The ratio of dogs to cats is 2:3, and the ratio of poeple with cats to those with fish is 5:6. All pets are randomly distributed. The challenge is to find what fraction of the people own dogs.

Solution

Fascinating Fruits

Diagram of the Fascinating Fruits.

You will need an understanding of algebra and combinatorics to solve today’s challenge.

Today’s challenge begins with 3 rows of fruits. They begin with an apple, and orange, and a pear. The fruits behind the front are unknown. Directly behind any apple, there is an equal chance of a plum, a banana, or an orange. There is no other fruit directly behind an apple, but one apple is at the end of a row. Behind any plum is the same fruit that was in front of it. Directly behind an orange, there is a one third probability there are grapes. There is an equal probality of pears and blueberries, and 1 orange leads to a banana. For any banana there is an equal chance of blueberries or a plum. 1 banana is followed by grapes, and another ends a row. Behind blueberries, there is a one third chance of a pear, otherwise grapes. Directly behind grapes, there is a 50% chance of more grapes, a 25% chance of a plum, and otherwise a pear. Finally, directly behind a pear there is the fruit of the colour in the rainbow following that of the fruit in front of the pair. The exception is the 1 pear that ends a row. The apples in this question are red, which is considered to follow purple, the colour of the plums. The fruit following the pair at the front is an apple. The challenge is to use this information to find the probability that the row started by a pear ends with one.

Solution

Puzzling Probabilities

This challenge, though it appears simple, is far more difficult than you might expect. Knowledge of algebra, combinatorics, and graph theory, as well as ingenuity and effort, are necessary to successfully complete this challenge. Be warned.

Bob goes to Scam Casino to lose some money. He decides to play the game “Stupid Spin.” There are many equal pieces of the spinner, and only a few give Bob a point. Otherwise, the Casino gets one. The probability that Bob gets a point is a, and the first to b points wins. The challenge is to find the probability that Bob will win a given game of Stupid Spin.

Solution