Lucas Sta Maria
I'm a third-year Computer Science and Mathematics student at Northeastern University interested in programming languages and developer tooling.
(λx.x x) (λx.x x)
Problems / Brainteasers
This is a relatively small collection of interesting problems and brainteasers that I've come across or come up with. Hopefully you enjoy thinking about them.
A knight is placed in one of the centre four squares of a standard chessboard. The knight has eight possible moves. If in a square close to the board's edge, then a move can place the knight out of bounds.
Author: Me, inspired by an interview question
- Find the probability that the knight remains on the board after 1 move, 2 moves, 3 moves.
- Is there a general equation for the probability that the knight remains on the board after n moves?
A chess board has 64 squares. Place each integer from 1 to 64 inclusive on a square such that the value in the square is the average of the values in its neighbouring squares.
Author: Unknown
Consider a 3x3 chessboard/checkerboard.
Author: Unknown
- How many ways can 4 checkers be placed on the board, up to symmetry? Consider both rotations and flips.
- What is the maximum number of bishops that can be placed on the board such that none are attacking one another?
- What is the maximum number of bishops that can be placed on the board if the board becomes a standard 8x8 chessboard?
The left-hand-rule is famous for being an easy-to-remember algorithm to solve mazes. Unfortunately, it doesn't actually work.
Author: Vir- Prove that there does not exist a deterministic algorithm with O(1) space complexity that can solve any arbitrary maze, or find a counter-example.
A broken clock is right twice a day.
Author: Vir- If your clock is moving R times the rate of a normal clock, how many times is it right a day?
- What about negative R?
Consider a rectangular 2-D grid consisting of an odd number of cells. Each cell initially contains a single coin either showing heads or tails, and the number of coins showing heads is initially odd. You may remove a coin from the grid if it is heads, but after doing so you must flip all of the coins that are in adjacent cells.
Author: Unknown
- Devise a general algorithm to remove all of the coins from the grid.
- Prove that it is impossible to remove all of the coins if the initial number of coins showing heads is even.
You're given an unfair coin with probability P of landing heads and probability (1-P) of landing tails. How could you simulate a fair coin?
Author: Unknown