1.River Crossing

A farmer is on a riverbank with a wolf, a goat, and a head of cabbage. He wants to transport all three to the other side of the river in a boat. However, the boat has room for the farmer and just one other item (the wolf, goat, or cabbage). How can he safely carry all three across without the wolf eating the goat, or the goat eating the cabbage?

Show hint

Take the goat first (it's the only pair that can't be left alone together in either direction that matters), then think about what you must bring back before your next trip.

2.Optimization

Four people have to cross a footbridge at night. It is dark and they have one flashlight. A maximum of two people can cross the bridge at a time. Any party that crosses must have the flashlight with them, and it cannot be thrown. Person 1 takes 1 minute, Person 2 takes 2 minutes, Person 3 takes 5 minutes, and Person 4 takes 10 minutes to cross. What is the minimum total time for all four to cross?

Show hint

17 minutes. The trick is to send the two slowest people together rather than one at a time, using the two fastest people to shuttle the flashlight back.

3.Pattern / Modular Arithmetic

A student is counting from 1 to 1000 using the fingers of her left hand. She starts by calling her thumb 1, first finger 2, middle finger 3, ring finger 4, and little finger 5. Then she reverses direction, calling the ring finger 6, middle finger 7, first finger 8, thumb 9, then first finger 10, and so on back and forth. On which finger will she stop at 1000?

Show hint

The pattern repeats every 8 counts (thumb, first, middle, ring, little, ring, middle, first). Find 1000 mod 8 and match it to the position in that 8-count cycle.

4.Weighing / Divide & Conquer

There are eight identical-looking coins; one is fake and lighter than the others. What is the minimum number of weighings needed to identify the fake coin using a two-pan balance scale (no weights)? Now suppose there are nine coins and one is fake, but you don't know whether it's lighter or heavier — what is the minimum number of weighings needed then?

Show hint

For 8 coins: 2 weighings (split into groups of 3-3-2). For 9 coins with unknown weight direction: 3 weighings (split into groups of 3-3-3 first).

5.Counting

Pages of a book are numbered sequentially starting with 1. If the total number of decimal digits used is 1578, how many pages are in the book? Without a calculator, find the total sum of the digits in all integers from 1 to one million inclusive.

Show hint

For the page count: work in chunks — pages 1–9 use 9 digits, pages 10–99 use 180 digits, pages 100–999 use 2700 digits, then figure out how many digits remain for 4-digit pages. For the digit-sum problem, pair numbers cleverly (e.g., 0 and 999999, 1 and 999998, ...) so each pair's digit sum is constant.

6.Construction

A magic square of order 3 is a 3×3 table filled with nine distinct integers from 1 to 9 so that the sum of the numbers in each row, column, and both corner-to-corner diagonals is the same. Find magic squares of order 3, 5, and 7.

Show hint

For odd-order magic squares, the "Siamese method" (start in the middle of the top row, move diagonally up-right, wrap around, and drop down a cell when blocked) generates a valid square for any odd n.

7.Generalization

A stick 100 units long needs to be cut into 100 unit pieces. What is the minimum number of cuts required if you are allowed to cut several stick pieces at the same time (stacking them)? Now generalize an algorithm that performs this task with the minimum number of cuts for a stick that is n units long.

Show hint

Since you can stack pieces and cut them all at once, the number of pieces can double with each cut. You need ceil(log2(n)) cuts for a stick of length n.

8.Invariant

You have 20 black balls and 10 white balls in a bag. You repeat the following operation until a single ball is left: remove two balls at a time. If they are the same color, add a black ball back to the bag; if they are different colors, add a white ball back. What color is the last ball left in the bag? What if you start with 20 black balls and 15 white balls instead?

Show hint

Track the parity (odd/even) of the number of white balls — it's invariant or changes in a very predictable way with each move. That parity determines the final color.

9.Number Theory

There are n lockers in a hallway, numbered 1 to n. All doors start closed. You make n passes by the lockers, starting at locker #1 each time. On the ith pass, you toggle every ith locker's door (open it if closed, close it if open). After the last pass, which locker doors are open, and how many are open?

Show hint

A locker's door is toggled once for each of its divisors. Only perfect squares have an odd number of divisors, so only the perfect-square-numbered lockers remain open. There are floor(sqrt(n)) of them.

10.Search / Decomposition

You are given a sorted array of n distinct integers, some of which may be negative. Describe an algorithm to determine whether there exists an index i such that array[i] = i, using far fewer than n comparisons. What is the time complexity of your algorithm?

Show hint

Because the array is sorted, array[i] − i is non-decreasing. Use binary search: O(log n) time.

11.Graph Thinking

A group of 10 people at a party each shake hands with some subset of the others (no one shakes their own hand, and no pair shakes hands twice). Prove that at least two people at the party shook hands with the same number of people.

Show hint

This is a pigeonhole-principle argument. Each person's handshake count is between 0 and 9, but 0 and 9 can't both occur — work out why, then count the remaining possible values against 10 people.

12.Simulation

Conway's Game of Life is played on an infinite grid of cells, each either "alive" or "dead." Each generation, a cell's next state depends only on its 8 neighbors: a live cell with 2 or 3 live neighbors survives (otherwise it dies), and a dead cell with exactly 3 live neighbors becomes alive. Starting from a single row of 3 live cells in a row (a "blinker"), what does the grid look like after 1 generation? After 2 generations?

Show hint

The blinker oscillates with period 2: a horizontal row of 3 becomes a vertical column of 3, then back to horizontal.

13.Sorting Networks

You have three numbers stored in variables A, B, and C, and you may only swap the contents of two variables at a time using a temporary variable. What is the minimum number of swaps needed, in the worst case, to sort A, B, and C into ascending order? Describe your algorithm.

Show hint

3 swaps suffice in the worst case: compare-and-swap A,B then B,C then A,B again (a 3-element sorting network).

14.Recursion

The Tower of Hanoi puzzle has 3 pegs and n disks of different sizes stacked in decreasing size on one peg. You must move the entire stack to another peg, moving one disk at a time and never placing a larger disk on a smaller one. What is the minimum number of moves required as a function of n? Describe the recursive algorithm.

Show hint

2^n − 1 moves. Recursively move the top n−1 disks out of the way, move the largest disk, then move the n−1 disks on top of it.

15.Encoding / Abstraction

Design a system so that a blindfolded person can determine, using only touch, whether a coin placed in front of them is heads-up or tails-up, without being allowed to flip or feel the coin's face design. You may arrange any number of coins on a table beforehand in any configuration you like, and the blindfolded person must separate them into two groups — "heads" and "tails" — using only the rule you devise, even though they cannot tell heads from tails by touch or sight.

Show hint

This is a classic "abstraction" puzzle: pick any number of coins equal to however many are currently showing heads, flip only that subset over, and the two groups are now guaranteed to have equal numbers of heads. It works regardless of which coins were flipped, since only counts matter, not identities.

16.Combinatorics

A robot starts at the top-left corner of an m×n grid and can only move right or down one cell at a time. How many distinct paths are there to reach the bottom-right corner? Describe both a direct formula and a decomposition (recursive) approach.

Show hint

C(m+n−2, m−1) using combinations. Recursively, paths(m,n) = paths(m−1,n) + paths(m,n−1), which is Pascal's Triangle in disguise.

17.Logic Grid

Three boxes are labeled "Apples," "Oranges," and "Apples and Oranges." All three labels are wrong. Each box is filled with either only apples, only oranges, or a mix of both. You may draw exactly one piece of fruit from exactly one box (without looking inside) to correctly relabel all three boxes. Which box do you draw from, and how do you deduce the rest?

Show hint

Draw from the box labeled "Apples and Oranges" — since all labels are wrong, this box must be pure apples or pure oranges. That single fruit lets you deduce the true contents of all three boxes by elimination.

18.Algorithm Design

You are given a list of n integers and want to find the two numbers that sum to a given target value, T. Describe a brute-force algorithm and its time complexity, then describe a faster algorithm using a hash set. What is the time complexity of the improved approach?

Show hint

Brute force checks every pair: O(n²). Using a hash set, for each number x check whether T−x has already been seen: O(n) time, O(n) space.

19.State Machines

A vending machine accepts nickels (5¢) and dimes (10¢) only, and an item costs 25¢. Design a state diagram (or table) that tracks the total amount inserted so far as states, with transitions on "insert nickel" and "insert dime," until reaching or exceeding 25¢. How many distinct states (amounts) are reachable before the machine dispenses the item?

Show hint

Reachable amounts under 25¢ using only 5s and 10s are 0, 5, 10, 15, 20 — five states — each with two outgoing transitions (+5 or +10) leading toward or past 25.

20.Evaluation / Debugging

A classmate writes an algorithm to find the maximum value in a list: they initialize a variable max to 0, then loop through the list comparing each element to max and updating it when a larger value is found. Identify the flaw in this algorithm, construct a specific test case (list of numbers) that exposes the bug, and describe the fix.

Show hint

If every number in the list is negative, the algorithm incorrectly returns 0 since max is never updated. Fix: initialize max to the first element of the list instead of 0.

21. Configuration

Place eight queens on a standard chess board (8 x 8) so that no queen can capture another queen.

22. Computation

A software engineer lived in a neigborhood where all the houses were on one side of the street. The houses were numbered sequentially starting from 1.

Every morning she would walk her dog in one direction and in the evening she would walk her dog in the other direction. On one of these walks she noticed something special about her house - the sum of addresses on one side of her house was equal to the sum of the addresses on the other side of her house. [Her house address was not in either sum.]

Now her house address was 6 and the last house on the street had an address of 8. The sum of addresses on one side was 15 [= 1 + 2 + 3 + 4 + 5] and on the other side was also 15 [= 7 + 8]. She was convinced that hers was a lucky house since it had that property.

When she relocated to another town she went to the real estate agent and asked for a house that had exactly the same property - the sum of addresses on one side had to be equal to the sum of addresses on the other side. Now the lucky house number is dependent on the last house on the street. We know that the first set of numbers (the lucky house and the last house on the street) that satisfies that property is 6 and 8. What is the next set of numbers that have the same property. Assume that the last house on the street could be at most 10,000.

23. Probability

Samuel Pepys once wrote to Issac Newton to determine which was more probable: at least one six in six throws of a fair die or at least two sixes in twelve throws of a fair die? Give a convincing argument which scenario has the higher probability.

24. Coin Weighing

You have 20 coin machines, each of which produce the same kind of coin. You know how much a coin is supposed to weigh. One of the machines is defective, in that every coin it produces weighs 1 gram less than it is supposed to. You also have an electronic weighing machine. How can you determine which of the 20 machines is defective with only one weighing?

By one weighing, we mean you put a certain number of coins on the weighing machine and make a note of the reading and that is all. You are not allowed to add a few coins at a time on the weighing machine and watch the reading increase. That is multiple weighings.

You are allowed to crank out as many coins from each machine as you like.

25. Numeric

What is the four-digit number in which the first digit is one-third the second, the third is the sum of the first and second, and the last is three times the second?

26. Logic

On Citrus Island there are three tribes - the Tangerines, the Oranges, and the Lemons. They have different standards of veracity but otherwise are indistinguishable. Tangerines always tell the truth; Oranges always lie; Lemons, when asked a series of questions, tell the truth and lie alternately. A Lemon's first answer in a series may be either true or otherwise.

A visitor was somewhat confused recently when he was introduced to three natives named Tangerine, Orange, and Lemon, who are - not necessarily respectively - a Tangerine, an Orange, and a Lemon. There was also a fourth native, a lady named Pomelo. The visitor asked each of the first three natives (a) what his own tribe was, and (b) what was Ms. Pomelo's tribe.

To these questions, Mr. Tangerine replied: "I'm not a Tangerine and Ms. Pomelo is an Orange."

Mr. Orange replied: "I'm not an Orange and Ms. Pomelo is a Lemon."

Mr. Lemon replied: "I'm not a Lemon and Ms. Pomelo is a Tangerine."

To which tribe does Ms. Pomelo actually belong?

27. Inference

Here is an exercise in inference that appealed to Lewis Carroll. You are given a series of statements that may seem absurd but are all factually correct. What conclusion can you draw from these statements?

1. Pickled walnuts are always provided at Professor Piltdown's parties.
2. No animal that does not prefer Beethoven to Mozart ever takes a taxi in Bond Street.
3. All armadillos can speak the Basque dialect.
4. No animal can be registered as a philatelist who does not carry a collapsible umbrella.
5. Any animal that can speak Basque is eligible for the Tintinnabulum Club.
6. Only animals that are registered philatelists are invited to Professor Piltdown's parties.
7. All animals eligible for the Tintinnabulum Club prefer Mozart to Beethoven.
8. The only animals that enjoy pickled walnuts are those who get them at Professor Piltdown's.
9. Only animals that take taxis in Bond Street carry collapsible umbrellas.