A sample go program is show here.

package main

import "fmt"

func main() {
  message := greetMe("world")
  fmt.Println(message)
}

func greetMe(name string) string {
  return "Hello, " + name + "!"
}

Run the program as below:

$ go run hello.go

Normal Declaration:

var msg string
msg = "Hello"

Shortcut:

msg := "Hello"

str := "Hello"

Multiline string

str := `Multiline
string`

Typical types

num := 3          // int
num := 3.         // float64
num := 3 + 4i     // complex128
num := byte('a')  // byte (alias for uint8)

Other Types

var u uint = 7        // uint (unsigned)
var p float32 = 22.7  // 32-bit float

If a random variable $X$ can only take $0$ or $1$ as values, and its probability distribution is given by: $$ P(X=0)=p, P(X=1)=q, p+q=1 $$

such a random variable $X$ is said to follow Bernoulli distribution, denoted as $X\sim B(1,p)$ or $X\sim b(1,p)$

If a random variable’s probability distribution is given by: $$ P(X=k)=C_{n}^{k}p^{k}q^{n-k},k=0,1,2,\cdots,n,\quad (pq>0, p+q=1) $$

such a random variable $X$ is said to follow Binomial distribution, denoted as $X\sim B(n,p)$.

$C_{n}^{k}p^{k}q^{n-k}$ is the $k+1_{th}$ item of $(p+q)^{n}\sum\limits_{k=0}^{n}C_{n}^{k}p^{k}q^{n-k}$.

Here is the translation of the given text into English:

Background of the Binomial Distribution:
Suppose the probability of success in an experiment $S$ is $p$, and the experiment $S$ is repeated $n$ times. Let $X$ represent the number of successes. Then $X\sim B(n,p)$.

If a random variable’s probability distribution is given by: $$ P(X=k)=\frac{\lambda^{k}}{k!}e^{-\lambda},k=0,1,\cdots $$

such a random variable $X$ is said to follow Poisson distribution with parameter $\lambda$, denoted as $X\sim Poisson(\lambda)$, where $\lambda$ is a positive number.

Classical Problem: The number of red lights encountered by a taxi.

If the probability distribution of $X$ is: $$ P(X=m)=\frac{C_M^mC_{N-M}^{n-m}}{C_N^n},m=0,1,\cdots,M $$

such a random variable $X$ is said to follow Hyper Geometric distribution, denoted as $X\sim H(n,M,N)$.

The meaning of Hyper Geometric distribution:

Out of $N$ products, exactly $M$ are defective. If $n$ products are randomly selected, and let $X$ represent the number of defective products among the $n$ selected, then $X$ follows a hypergeometric distribution.

If the number of products is sufficiently large, there is essentially no difference between sampling without replacement and sampling with replacement: $$ P(X=m)=\frac{C_M^mC_{N-M}^{n-m}}{C_N^n}\approx C_n^m p^m (1-p)^{n-m}, (p=\frac{M}{N}) $$

If the probability distribution of $X$ is: $$ P(X=m)=q^{k-1}p,k=1,2\cdots,\quad pq>0,p+q=1 $$

such a random variable $X$ is said to follow Geometric distribution with parameter $p$, denoted as $X\sim Geometric(p)$.

The meaning of Geometric distribution:

Suppose the probability of success in an experiment is $p$, and the experiment is independently repeated until the first success occurs. Then the number of trials needed for the first success follows a geometric distribution with parameter $p$.

Problem

Two gamblers are playing a coin toss game. Gambler $A$ has $(n+1)$ fair coins; $B$ has $n$ fair coins. What is the probability that $A$ will have more heads than $B$ if both flip all their coins?

Solution

First, let’s remove the last coin of $A$, then the number of heads in the first $n$ coins of $A$ and $B$ has three outcomes:

$E_1$: $A$’s $n$ coins have more heads than $B$’s $n$ coins.

$E_2$: $A$’s $n$ coins have equal number of heads as $B$’s $n$ coins.

$E_3$: $A$’s $n$ coins have fewer heads than $B$’s $n$ coins.

Now, denote $P(A)$ as the probability of $A$ win the game after fliping $A$’s $(n+1)_{th}$ coin, we have: $$ \begin{align*} P(A) &= P(A|E_1) + P(A|E_2) + P(A|E_3) \cr &= P(E_1) * 1 + P(E_2) * \frac{1}{2} + P(E_3) * 0 \cr &= \frac{1}{2} \cr (P(E_1) &+ P(E_2) + P(E_3) = 1\quad and\quad P(E_1)=P(E_3)) \end{align*} $$

Problem

A casino offers a simple card game. There are 52 cards in a deck with 4 cards for each value 2,3,4,5,6,7,8,9,10,J,Q,K,A. Each time the cards are thoroughly shuffled (so each card has equal probability of being selected). You pick up a card from the deck and the dealer picks another one without replacement. IF you have larger number, you win; if the numbers are equal or yours is smaller, the house win – as in all other casinos, the house always has better odds of winning. What is your probability of winning?

Solution 1

Similarly, this problem can be solved as the former Coin Toss Game, it also has three outcomes:

$E_1$: your number is larger than the dealer’s.

$E_2$: your number is equal to the dealer’s.

$E_3$: your number is smaller than the dealer’s.

Now, $P(E_1)$ is the probability we want to get. By symmetry, $P(E_1)=P(E_3)$. And we also have $P(E_1) + P(E_2) + P(E_3) = 1$.

$P(E_2)$ denotes the two cards have equal numbers. If you have selected one card randomly, then there are only 3 cards withe the same value in the remaining 51 cards, so $P(E_2)=3/51$.

Then we can get: $$ P(E_1)=\frac{1-P(E_2)}{2}=\frac{8}{17} $$

Solution 2

If you select a card first, there are 13 outcomes. Each outcome has a corresponding probability of winning the game. $$ \begin{align*} P(Win) &= P(Win|2) + P(Win|3) + \cdots + P(Win|A) \cr &= \frac{1}{13} \times (0 + \frac{4}{51} + \frac{8}{51} + \cdots + \frac{48}{51}) \cr &= \frac{4}{13} \times \frac{6\times 13}{51} = \frac{8}{17} \end{align*} $$

Problem

A line of 100 airline passengers are waiting to board a plane. They each hold a ticket to one of the 100 seats on that flight. For convenience, let’s say that the $n_{th}$ passenger in line has a ticket for the seat number $n$. Being drunk, the first person in line picks a random seat (equally likely for each seat). All of the other passengers are sober, and will go to their proper seats unless it is already occupied; In that case, they will randomly choose a free seat. You’re person number 100. What is the probability that you end up in your seat (i.e., seat #100) ?

Solution

Let’s consider seats #1 and #100. There are two possible outcomes:

$E_1$: Sear #1 is taken before #100;

$E_2$: Sear #100 is taken before #1.

By symmetry, $P(E_1) = P(E_2) = \frac{1}{2}$.

If $E_1$ happens, no matter which passenger takes #1, all passengers after him(her) will take their own seats, so you will end up in your own seat.

If $E_2$ happends, you will definited noe end up in your own seat.

Problem

Given $N$ points drawn randomly on the circumference of a circle, what is the probability that they are all within a semicircle?

Solution

Denote $E_i, i\in {1,2,\cdots,N}$ as starting at point $i$, all the other $N-1$ points are in the clockwise semicircle. We can verify that these events are mutually exclusive.

For example, if we, starting at point $i$ and proceeding clockwise along the circle, sequentially encounters points $i+1,i+2,\cdots,N,1,\cdots,i-1$ in a half circle, then starting at any other point $j$, we cannot encounter all other points within a clockwise semicircle.

Hence, all these events are mutually exclusive.

For any $E_i$, if point $i$ is determined, the clockwise semicircle is also determined, every point is located on that semicircle with probability $\frac{1}{2}$, so $P(E_i)=\frac{1}{2^{N-1}}$.

So we have: $$ P(\cup_{i=1}^{N}E_i) = \sum_{i=1}^{N}P(E_i) = \frac{N}{2^{N-1}} $$

Problem

Pocker is a card game in which each player gets a hand of 5 cards. There are 52 cards in a deck. Each has a value and belongs to a suit. There are 13 values, 2,3,4,5,6,7,8,9,10,J,Q,K,A, and four suits, spade, club, heart and diamond.

What are the probability of getting hands with four-of-a-kind (four of the five cards with the same value)? Hands with a full house (three cards of one values and two cards another value)? Hands with two pairs?

Solution

The total number of selecting 5 cards from 52 cards randomly is $\binom{52}{5}$.

Hands with a four-of-a-hand $$ N = \binom{13}{1}\times \binom{48}{1} = 13\times 48 $$

Hands with a full house $$ N = \binom{13}{1}\times \binom{4}{3}\times \binom{12}{1}\times \binom{4}{2} = 13\times 4\times 12 \times 6 $$

Hands with two pairs $$ N = \binom{13}{2}\times \binom{4}{2}\times \binom{4}{2}\times \binom{44}{1} = 78\times 6\times 6\times 44 $$

Problem

A rabbit sits at the bottom of a staircase with $n$ stairs. The rabbit can hop up only one or two stairs at a time. How many different ways are there for the rabbit to ascend to the top of the stairs?

Solution

Denote $f(n)$ as the number of ways for the rabbit to ascend to the top when there are $n$ stairs.

If $n=1$, obviously $f(1)=1$.

Similarly, if $n=2,f(2)=2$ (one 2-stair hop or two 1-stair hops).

For any $n>2$, there are always two possibilities for the last hop: either it’s a 1-stair hop or a 2-stair hop. In the former case, the rabbit is at $(n-1)$ before reaching $n$, and it has $f(n-1)$ ways to reach $(n-1)$. In the latter case, the rabbit is at $(n-2)$ before reaching $n$, and it has $f(n-2)$ ways to reach $(n-2)$.

So we have $f(n)=f(n-1)+f(n-2)$. Then we can get all $f(n)$ based on $f(1)=1$ and $f(2)=2$.

Problem

Having peacefully divided the loot (in chapter 2), the pirate team goes on for more looting and expands the group to 11 pirates. To protect their hard-won treasure, they gather together to put all the loot in a safe. Still being a democratic bunch, they decide that only a majority - any majority - of them ($\geq6$) together can open the safe. So they ask a locksmith to put a certain number of locks on the safe. To access the treasure, every lock needs to be opened. Each lock can have multiple keys; but each key only opens one lock. The locksmith can give more than one key to each pirate.

What is the smallest number of locks needed? And how many keys must each pirate carry?

Hint: every subgroup of 6 pirates should have the same key to a unique lock that the other 5 pirates do not have.

Solution

Let’s randomly select 5 pirates, they can’t open the safe. But once the $6_{th}$ pirate joins, who holds a unique key to a unique lock, they can open the safe. So every subgroup of 5 pirates corresponds to 1 unique lock, so there are $\binom{11}{5}$ locks.

Every lock should have 6 keys so that anyone in a subgroup of 6 pirates joins the selected 5 pirates can make the safe open. So every pirate should have $\frac{\binom{11}{5}\times 6}{11}$ keys.

Problem

A chess tournament has $2^n$ players with skills $1>2>\cdots>2^n$. It is organized as a knockout tournament, so that after each round only the winner proceeds to the next round. Except for the final, opponents in each round are drawn at random. Let’s also assume that when two players meet in a game, the player with better skills always wins.

What’s the probability that players 1 and 2 will meet in the final?

Hint: Consider separating the players to two $2^{n-1}$ subgroups. What will happen if player 1 and 2 in the same group? Or not in the same group?

Solution 1

Suppose we have finished a complete game, player 1 definitely won the game no matter how the game proceeded. But let’s focus on the two player participating in the final round, we can divide the left $2^n - 2$ players into two subgroups according to which one defeated them. So we get two $2^{n-1}$ subgroups.

If player 2 was also a participant of final round, he/she must be in the subgroup different from player 1.

Since any of the remaining players in $2,3,\cdots,2^n$ are likely to be one of the $(2^{n-1}-1)$ players in the same subgroup as player 1 or one of the $2^{n-1}$ players in the subgroup different with player 1, the probability that player 2 is in a different subgroup from player 1 is simply $\frac{2^{n-1}}{2^n-1}$

Solution 2

The game has $n$ rounds for there are $2^n$ players.

Define $E_i, i=1,2,\cdots,n-1$ as the event that player 1 and 2 do not meet in round $1,2,\cdots,i$.

At the first round, every player except 1 has the same probability $\frac{1}{2^{n}-1}$ to be the rival of player 1. So $E_1=\frac{2^{n}-2}{2^n-1}=\frac{2(2^{n-1}-1)}{2^n-1}$.

Similarly: $$ \begin{align*} E_2 &= \frac{2^{n-1}-2}{2^{n-1}-1} = \frac{2(2^{n-2}-1)}{2^{n-1}-1} \cr &\vdots \cr E_i &= \frac{2^{n-i+1}-2}{2^{n-i+1}-1} = \frac{2(2^{n-i}-1)}{2^{n-i+1}-1} \cr &\vdots \cr E_{n-1} &= \frac{2^2-2}{2^2-1} = \frac{2(2-1)}{2^2-1} \end{align*} $$

Then we can get: $$ P(\text{player 1 and 2 meet in the final round}) = P(E_1)\times P(E_2|E_1)\times\cdot\times P(E_{n-1}|E_1E_2\cdots E_{n-2}) = \frac{2^{n-1}}{2^n-1} $$

Problem

You’re sending job applications to 5 firms: Morgan Stanley, Lehman Brothers, UBS, Goldman Sachs, and Merrill Lynch. You have 5 envelopes on the table neatly typed with names and addresses of people at these 5 firms. You even have 5 cover letters personalized to each of these firms. Your 3-year-old tried to be helpful and stuffed each cover letter into each of the envelopes for you. Unfortunately she randomly put letters into envelopes without realizing that the letters are personalized. What is the probability that all 5 cover letters are mailed to the wrong firms?

Hint: The complement is that at least one letter is mailed to the correct firm.

Solution

Denote $E_I, i=1,2,\cdots,5$ as the event that the $i_{th}$ letter has the correct envelope. Then $P(\cup_{i=1}^{5}E_i)$ is the probability that at least one letter has the correct envelope and $1-P(\cup_{i=1}^{5}E_i)$ is the probability that all letters have the wrong envelopes.

$P(\cap_{i=1}^{5}E_i)$ can be calculated using the Inclusion-Exclusion Principle: $$P(\cup_{i=1}^{5}E_i)=\sum_{i=1}^5P(E_i) - \sum_{i_1<i_2}P(E_{i_1}E_{i_2}) + \cdots + (-1)^6P(E_{i_1}E_{i_2}\cdots E_{i_5})$$

It’s obvious that $P(E_i)=\frac{1}{5},i=1,2,\cdots,5$ so that $\sum_{i=1}^5P(E_i)=1$.

$P(E_{i_1}E_{i_2})=P(E_{i_1})P(E_{i_2}|E_{i_1})=\frac{1}{5}\cdot\frac{1}{4}=\frac{1}{20}$ so that $\sum_{i_1<i_2}P(E_{i_1}E_{i_2})=\binom{5}{2}\frac{1}{20}=\frac{1}{2!}$

Similarly we have $\sum_{i_1<i_2<i_3}P(E_{i_1}E_{i_2}E_{i_3})=\frac{1}{3!}$, $\sum_{i_1<i_2<i_3<i_4}P(E_{i_1}E_{i_2}E_{i_3}E_{i_4})=\frac{1}{4!}$ and $P(E_{i_1}E_{i_2}\cdots E_{i_5})=\frac{1}{5!}$.

So $1-P(\cup_{i=1}^{5}E_i) = 1 - \frac{1}{2} + \frac{1}{3!} - \frac{1}{4!} + \frac{1}{5!} = \frac{11}{30}$.

Problem

How many people do we need in a class to make the probability that two people have the same birthday more than 1/2? (For simplicity, assume 365 days a year.)

Solution

Suppose there are $n$ people in the class, so there are $365^n$ possible combinations. The probability of their birthday are all different is: $$ P = \frac{365\times(365-1)\times(365-2)\times\cdots\times(365-n+1)}{365^n} $$

Solve: $$ \begin{align*} &\min\quad n \cr &s.t.\quad 1 - P > \frac{1}{2} \end{align*} $$

The smallest such $n$ is 23.

Problem

What is the $1OO_{th}$ digit to the right of the decimal point in the decimal representation of $(1 + \sqrt{2})^{3000}$?

Hint: $(1+\sqrt{2})^2+(1-\sqrt{2})^2=6$. What will happen to $(1-\sqrt{2})^{2n}$ as $n$ becomes large?

Solution

Applying the binomial theorem for $(x+y)^n$, we have: $$ (1+\sqrt{2})^n = \sum_{k=0}^n\binom{n}{k}1^{n-k}\sqrt{2}^k = \sum_{k=2j, 0\leq j\leq\frac{n}{2}}^n\binom{n}{k}1^{n-k}\sqrt{2}^k + \sum_{k=2j+1, 0\leq j<\frac{n}{2}}^n\binom{n}{k}1^{n-k}\sqrt{2}^k $$

and: $$ (1-\sqrt{2})^n = \sum_{k=0}^n\binom{n}{k}1^{n-k}(-\sqrt{2})^k = \sum_{k=2j, 0\leq j\leq\frac{n}{2}}^n\binom{n}{k}1^{n-k}\sqrt{2}^k - \sum_{k=2j+1, 0\leq j<\frac{n}{2}}^n\binom{n}{k}1^{n-k}\sqrt{2}^k $$

So we have: $$ (1+\sqrt{2})^n + (1-\sqrt{2})^n = 2\times \sum_{k=2j, 0\leq j\leq\frac{n}{2}}^n\binom{n}{k}1^{n-k}\sqrt{2}^k, $$ which is always an integer.

It’s easy to see that $0<(1-\sqrt{2})^n«10^{-100}$. So the $100_{th}$ digit of $(1 + \sqrt{2})^n$ must be 9.

Problem

Let $x$ be an integer between 1 and $10^{12}$, what is the probability that the cubic of $x$ endswith 11?

Hint: The last two digits of $x^3$ only depend on the last two digits of $x$.

Solution

All integers can be expressed as $x=a+10b$, where $a$ is the last digit of $x$. So we have $x^3=(a+10b)^3=a^3+30a^b+300ab^2+1000b^3$.

The unit digit of $x^3$ only depends on $a^3$, so $a=1$.

The tenth digit only depends on $30a^2b$, so $b=7$.

Consequently, the last two digits of $x$ should be $71$, which has a probability of $1$% for integers between $1$ and $10^{12}$.