Katkat
Back

Solve tiling, probability, and nested-radical puzzles

J.P. MorganData Scientist · Onsite
MediumData ScientistOnsiteCoding & Algorithms

Last updated

This problem tests your ability to derive recurrence relations for combinatorial tiling, solve infinite series limits, and calculate exact probabilities using combinations.

Part 1: Domino Tiling

Find the number of ways to tile a 2 x N board using 2 x 1 dominoes. Write a function count_tilings(N) that returns the number of ways to tile the board.

Example:

  • N=1: 1 way
  • N=2: 2 ways (two vertical or two horizontal)
  • N=3: 3 ways

Part 2: Infinite Nested Radical

Evaluate the following expression where x = sqrt(6 + sqrt(6 + sqrt(6 + ...))).

Part 3: Selecting Couples

There are 10 married couples (20 people total) at a party. If 4 people are chosen at random, what is the probability that exactly one married couple is among the 4 chosen? Express your answer as a simplified fraction.

Constraints

  • Part 1: N is a positive integer up to 1000. Use modulo 10^9 + 7 if needed for larger N.
  • Part 2: Show the algebraic steps to derive the exact value.
  • Part 3: Assume selection is without replacement.

Hints

Hint 1

For tiling, observe that the last domino added can either be vertical (leaving a 2x(N-1) space) or horizontal (requiring a second horizontal domino to complete the block, leaving a 2x(N-2) space).

Hint 2

For the radical, set the expression equal to x, square both sides to get x^2 = 6 + x, and solve the resulting quadratic equation.

Hint 3

For the probability, use the formula (Number of ways to choose 1 couple * Number of ways to choose the remaining 2 people from different couples) / Total ways to choose 4 people.

Follow-up questions

  • How would the tiling recurrence change if you were tiling a 3 x N board?
  • If the infinite radical was sqrt(k + sqrt(k + ...)), what condition must k satisfy for the result to be an integer?
  • How would the probability change if you were asked for at least one married couple instead of exactly one?