Description

CS 70 Discrete Mathematics and Probability Theory

1 Zerg Player
A Zerg player wants to produce an army to fight against Protoss in early game, and he wants to have a small army which consumes exactly 10 supply. And he has the following choices:
• Zerglings: consumes 1 supply
• Hydralisk: consumes 2 supply
• Roach: consumes 2 supply
How many different compositions can the player’s army have? Note that Zerglings are indistinguishable, as are Hydralisks and Roachs.
2 Strings
What is the number of strings you can construct given:
(a) n ones, and m zeroes?
(b) n1 A’s, n2 B’s and n3 C’s?
(c) n1,n2,…,nk respectively of k different letters?
3 Counting Game
RPG games are all about explore different mazes. Here is a weird maze: there are 2n rooms, where each room is the vertex on a the n-dimensional hypercube, labeled by a n bit binary string.
For each room, there are n different doors, each door corresponding to an edge on the hypercube. If you are at room i, and choose door j, then you will go to room i⊕2j (flips the j+1-th bit in number i).
(a) How many different shortest path are there from room 0 to room 2n −1?
(b) How many different paths of n+2 steps are there to go from room 0 to room 2n −1?
(c) If n= 8, how many different shortest pathes are there from room 0 to room 63 that pass through 3 and 19?