Problem set

by Ben Rosenberg

Problems are rated as follows:

DifficultyMeaning
Easy
Intermediate
Hard
Harder
Hardest
Dubious
Questionable
Suspicious
Dastardly
Iniquitous
Vile
  • 1. [Open-top cone] What is the volume of an open-top cone, given its height, bottom radius, and top radius?

    • 1.1 What is its surface area?

    • 1.2 Let p be a point level with the cone’s base and suppose p is three times the radius of the cone away from the cone’s center. Let \theta_\text{min} be 0 and let \theta_\text{max} be the the angle of elevation from p to the cone’s (open) top. Suppose \theta is chosen randomly from a triangle distribution with \mu = \frac{\theta_\text{min} + \theta_\text{max}}{2}. What is the expected area of the triangle \triangle ABp, where A is the endpoint of the segment from p to the cone’s base and B is the endpoint of the segment from p to the cone with angle of elevation \theta?

  • 2. [Rectangle inscribed in normal distribution] What is the maximum area of a rectangle inscribed inside the normal distribution?

    • 2.1 What is the maximum area of an ellipse inscribed inside the normal distribution?

    • 2.2 What are the dimensions of the cone in \mathbb R^3 with the smallest absolute difference in overlap with the bivariate normal distribution N(x,y)?

    • 2.3 What are the dimensions and location of the maximal sphere in \mathbb R^3 inscribed in the bivariate normal distribution N(x,y)?

    • 2.4 What are the dimensions and location of the sphere in \mathbb R^3 with the smallest absolute difference in overlap with the bivariate normal distribution N(x,y)?

  • 3. [Expected time to heads-tails sequence] Given a sequence of heads and tails HTHTTH, find the expected time until the sequence is seen when flipping a coin repeatedly.

    • 3.1 What is the expected time until the above sequence is seen 5 times in a row?

    • 3.2 Given an arbitrary sequence of heads and tails, find the expected time until the sequence is seen.

    • 3.3 Given a discrete random variable and an arbitrary sequence of its outputs, find the expected time until the sequence is seen.

  • 4. [TSP] Given a list of 2-dimensional coordinates, determine the shortest time to visit all the coordinates and return to the starting point.

    • 4.1 Scale the edge lengths by average endpoint distance from the origin relative to one another and give the new solution. (For example, (0,0)-(0,1) has avg distance of 0.5 from origin, as does (0,0)-(1,0), so nothing is scaled if these are the only two edges. But if we add (0,9)-(0,11), which has an average distance from the origin of 10, that edge would be scaled up to (\text{distance}/\text{min distance}) = 10/0.5 = 20.)

    • 4.2 Let N(x,y) be the bivariate normal distribution. Choose points in \mathbb R^2 with probability according to N(x,y). What is the expected area enclosed by the TSP path?

    • 4.3 Let N(x,y) be the bivariate normal distribution. Choose points in \mathbb R^2 with probability according to N(x,y). What is the expected area enclosed by the TSP path, if you scale the edge lengths according to the above methodology?

  • 5. [Coin on a hexagon tiling] Given a tiling of hexagons with diameter 1, place a coin of diameter 1 onto the surface at random. What is the expected number of hexagons that are touched by the coin?

    • 5.1 Now consider a tiling of squares with side length 1. What is the expected number of squares that are touched by the coin?

    • 5.2 Now consider a (P3) Penrose tiling with random offset in the plane and tile side length 1. What is the expected number of tiles that are touched by the coin?

  • 6. [Ant on a cube] Suppose there is an ant on a cube. The ant starts at a certain vertex and does a random walk along the edges of the cube, going from vertex to vertex. (At each step, the ant has a 1/3 chance of choosing each direction.) How many steps are expected before the ant returns to its starting vertex?

    • 6.1 How does this vary when the ant is instead walking on a hypercube of dimension n\geq 2?

    • 6.2 Suppose the ant is continuously walking rather than taking discrete steps. At time t, what is the expected (Euclidean) distance of the ant from its starting point?

    • 6.3 Suppose ants arrive at a vertex on a cube continuously with rate r (so interarrival times T_n have distribution \text{Exp}(r), n \geq 0). Each ant behaves as before, but ants wait an additional k units of time before moving one more step in the cube, where k is the number of ants present at that state when the ant first arrived. What is the expected time until there are X ants at the opposite corner of the cube?

    • 6.4 Now assume instead of waiting k steps the ants wait \lfloor k/2 \rfloor steps. How does the above answer change?

    • 6.5 Assume instead of a cube the ants are on an infinite grid, starting at (0,0), and are able to move one unit in the four cardinal directions. Derive a formula for the time until there are X ants at position (i,j) on the grid.

    • 6.6 Now allow ants to move one unit diagonally, so their moves match those of a king’s in chess. How does your formula change?

    • 6.7 How does your above answer change if the ants move like knights in chess?

    • 6.8 Now for grid point (i,j), consider each of the following functions on i and j as a value for k: \min(i,j), \max(i,j), i+j, i\cdot j, i-j, i//j (integer division), i\bmod j, i^j, i\& j (binary and), i \mid j (binary or), \delta(i,j) (Kronecker delta), (i+j)/2. How does the time until there are X ants at (i,j) change?

    • 6.9 Suppose the ants can now move like any chess piece - pawn, knight, bishop, rook, queen, or king. The piece is chosen uniformly at random by each ant each time it moves. For pieces that can move infinitely, let the move distance have distribution \text{Exp}(r), where r is the ants’ arrival rate. Revise your answers to the above questions.

    • 6.10 Generalize each of the above grid problems to \mathbb Z^N (the above grid problems assume \mathbb Z^2).

  • 7. [Chord intersections] Choose 3 random chords on a circle. What is the expected number of intersections between the chords?

    • 7.1 What about with n chords?

  • 8. [Random walk marbles] Consider a random walk on a grid (distance-1 rook moves), in which a marble is placed every n steps. What is the distribution of the distance between any two marbles after m steps?

    • 8.1 What is the distribution of the distance between every 2 marbles (e.g., for path a\to b\to c \to d, the distance between a and c, and b and d)?

  • 9. [Enclosing random walk] Consider a random walk on a grid (distance-1 rook moves), which ends once a nonempty region has been completely enclosed by the path. What is the expected perimeter of the enclosed region?

    • 9.1 What is the expected area of the enclosed region?

    • 9.2 Let the walk continue for n steps. What is the expected enclosed area formed by the path, in terms of n?

    • 9.3 Let the walk continue for n steps. What is the expected enclosed area of the convex hull of the enclosed regions?

    • 9.4 Let N(x,y) (the bivariate normal distribution) be the height map for the plane. Start the random walk at the origin. What is the expected volume of the first enclosed region?

    • 9.5 Let N(x,y) (the bivariate normal distribution) be the height map for the plane. Start the random walk at the origin. What is the expected volume of the enclosed regions after n steps?

    • 9.6 Suppose the probability that a step is taken in a given direction from (x,y) to (x',y') on the random walk is given by the relative height of N(x',y'), scaled so that all the direction probabilities sum to 1. How do the answers to the above questions change?

    • 9.7 Suppose the probability that a step is taken in a given direction from (x,y) to (x',y') on the random walk is given by the relative height of \displaystyle z = \frac{1 + \cos(x)\sin(x) + \cos(y)\sin(y)}{2}, scaled so that all the direction probabilities sum to 1. How do the answers to the above questions change?

  • 10. [Random shape created by lines] Pick points in \mathbb R^{2} according to N(x,y) (the bivariate normal distribution) and assign them random angles (uniformly in the range (0, 2\pi)) so that they create a line. Do this until there is at least one closed region. (This will be after 3 steps.) Take the closest region to the origin. What is its expected area?

    • 10.1 What is the volume of the first shape, using N(x,y) as the height map?

    • 10.2 Instead of lines, instead create rays starting at the chosen point and extending in the chosen direction. (This means that the first shape will no longer be guaranteed to be created after 3 steps.) What is the first shape’s expected area and what is its expected volume, using N(x,y) as the height map?

  • 11. [Quadrilateral in a square] Choose 4 random points on the perimeter of a square (they could be all on the same side of the square). What is the expected area of the resulting (convex) quadrilateral?

    • 11.1 Suppose you are given a height function H(x,y) = x+y. What is the expected volume of quadrilateral region?

    • 11.2 Now choose n points on the square. What is the expected area (and volume, using H(x,y)), in terms of n?

    • 11.3 Now choose n points on a regular k-gon. What is the expected area (and volume, using H(x,y)), in terms of n and k?

  • 12. [Random walk chase] Consider a pair of walks in \mathbb R^2. The first is a random walk, making distance-1 rook moves, which starts at time zero. The second is a walk that chases the first walk, making distance-1 king moves (able to use diagonals), which starts at time 1. What is the expected time before the second walk catches the first?

    • 12.1 What if the first walk instead makes knight moves, and the second walk is able to move arbitrary distances with queen moves?

    • 12.2 What if the first walk instead makes knight moves, and the second walk is able to move arbitrary distances with bishop moves (only diagonally)?

  • 13. [Convex hull area] Given a list of 2-dimensional coordinates, find the area of the convex hull of those coordinates.

    • 13.1 Given a height map H(x,y) = x+y, what is the volume of the above region?

  • 14. [Tetrahedron collision] Take two tetrahedrons of side length 1 aligned opposite each other on the x-axis in \mathbb R^3. Move them towards (into) each other until the tip of one touches the back of the other (and vice-versa, as they are the same size). What is the total volume of the resulting shape?

    • 14.1 Let D(x,y,z) = \sqrt{x+y+z} be a density function over \mathbb R^3. What is the volume of the shape, given this density?

    • 14.2 Instead of a tetrahedron, suppose you have a k-pyramid, where the base is a regular k-gon, and the sides are triangles as in the tetrahedron. What is the total volume, in terms of k, of the shape created by pushing the shapes into one another as before? What is its volume, using D(x,y,z)?

    • 14.3 What is the volume when taking k\to \infty (a cone)?

  • 15. [Area enclosed by chords] Choose n chords in a circle randomly. What is the expected area of the smallest shape enclosed by chords?

    • 15.1 What is the expected area of the largest shape enclosed by chords?

    • 15.2 What is the area of the smallest polygon enclosed by the chords (the shape is only bounded by chords, not the circle)? If there is no polygon, consider its area to be 0.

    • 15.3 What is the area of the largest polygon enclosed by the chords (the shape is only bounded by chords, not the circle)? If there is no polygon, consider its area to be 0.

  • 16. [Pentagon packing] Suppose you have a square with sides of length 10. How much area is left after optimally packing the area with pentagons of side length 1?

    • 16.1 How much area is left after optimally packing the area with regular k-gons, for your choice of k?

    • 16.2 For which k \geq 5 is the packing best (uncovered area minimized)?

    • 16.3 Suppose that after packing the area with pentagons of side length 1, you do another round of packing. You can choose the k for which you pack as many regular k-gons into the remaining space as possible. (Each of the polygons you add in the second round must have the same size.) What k do you choose, and what is the expected area left after this second round?

    • 16.4 Now suppose that there are m rounds. How does your above answer change?

  • 17. [Tetromino packing] Given a set of 100 random tetrominos, determine the minimum area into which they can be packed.

    • 17.1 Fix the dimensions of the board to width 10 and height 20. Suppose that lines are cleared when the entire line is filled with minos. The scoring system for line clears is that single line clears are worth 1 point, double line clears are 2, triple line clears are worth 6, and quadruple line clears are worth 10. All clears are worth 14 points. What is the expected maximum score achievable with perfect play, assuming the tetrominos come into the field in order and you are allowed to hold a piece as in typical gameplay?

    • 17.2 Consider the above problems with k-minos.

  • 18. [Minimal automata states] Let \Sigma be an alphabet (set) of characters with |\Sigma| = n and let k be a nonnegative integer. What is the expected number of states in the minimal NFA accepting s, where s is a randomly generated string of characters from \Sigma with length k?

    • 18.1 What about the minimal DFA?

    • 18.2 Take s as before, and let s' be a string over \Sigma with random length \ell, where k \leq \ell \leq 2k. Let D_s = (Q_s, \Sigma, \delta_s, q_{0_s}, F_s) be the minimal DFA accepting s, and let D_{s'} = (Q_{s'}, \Sigma, \delta_{s'}, q_{0_{s'}}, F_{s'}) be the minimal DFA accepting s'. Perform a (1-indexed) topological sort over the states in D_s and in D_{s'}, starting from q_{0_s} and q_{0_{s'}} respectively and choosing states in alphabetical order based on their in-edges, and denote these orderings by T_s : Q_s \to \mathbb N and T_{s'} : Q_{s'} \to \mathbb N. Recall that the transition function \delta of a DFA D = (Q, \Sigma, \delta, q_0, F) is of the form \delta : Q \times \Sigma \to Q. Let T be the general topological sort order for a DFA D, and let the string representation \gamma(d) of a transition d\in \delta, where d = ((q,\sigma),q') for q,q'\in Q and \sigma\in \Sigma, be the string '[a&b>c]' where a is T(q), b is \sigma, and c is T(q'). Let the string representation \Gamma(D) of a DFA D be given by the concatenation (represented here by \cap) of the stringified elements of \delta as follows: \Gamma(D) = \bigcap_{d\in\delta}\gamma(d) What is the expected (Levenshtein) edit distance between \Gamma(D_s) and \Gamma(D_{s'})?

  • 19. [Penrose resistors] What is the minimum equivalent resistance between vertices 2 edges apart on an infinite (P3) Penrose tiling of 1-ohm resistors?

  • 20. [Random regular expression] Let r be a random regular expression over \Sigma = \{a,b,c\} of length k > 10, in reverse polish notation (RPN). Suppose r is generated by selecting i<k symbols from the simple three regular operators (\circ for concatenation, \mid for union, and \phantom{}^* for Kleene star) and interspersing them randomly so that they create a valid expression in RPN. What is the expected length of the minimal DFA accepting r, in terms of i and k?

  • 21. [Shaded chessboard] The left half of a (regular, 8-by-8) chessboard is shaded, and the right half is not. There is a king one the board that starts on a random square, and moves randomly in any of the 8 directions available to it (or the subset of legal moves from those 8 choices). When the king is in the shaded area of the chessboard it takes one move for each time interval, and when in the sunny area it takes n moves for each time interval. What is n so that the king spends on average, as t\to \infty, 75 percent of its time in the shaded region? Assume that the squares through which the king passes are counted with 1/k the weight of the square on which the king stops, for some k\in \mathbb Z^+.

    • 21.1 Extend the problem to an m by m board.

    • 21.2 Extend the problem to arbitrary percentage p.

    • 21.3 Now assume the king’s speed (steps per time interval) is equal at any point to the Manhattan distance from the bottom left square. (For example, if the king is at (4,4), then he should take 8 steps, and then recalculate his speed.) What subset of squares should be shaded to most closely approximate a percentage p by the average amount of time the king spends in the shaded area?

  • 22. [Adjacent tiles of same color on a Rubik's cube] What is the number of positions a Rubik’s cube can be in so that no face has any adjacent tiles of the same color? What percentage of the total states is this?

    • 22.1 What about, rather than no adjacent tiles, fewer than k adjacent tiles of the same color on each face?