Questions tagged [combinatorics]

A puzzle based on combinatorial mathematics, which is the study of finite or countable discrete structures.

Filter by
Sorted by
Tagged with
52
votes
9answers
77k views

Twelve balls and a scale

You are given twelve identical-looking balls and a two-sided scale. One of the balls is of a different weight, although you don't know whether it's lighter or heavier. How can you use just three ...
10
votes
4answers
8k views

N balls and a scale

The question of twelve balls and a scale is probably the best-known example of the "find the ball of a different weight" problem. But does it generalize? Is there a general way to find a weighing ...
12
votes
4answers
1k views

Nerds, Jocks, and Lockers

Here's an oldie but goodie from The Daily WTF; I paraphrase to avoid copyright issues: A middle school math teacher, who also happened to be the P.E. coach, made the following deal with the non-...
37
votes
3answers
5k views

The coolest checkerboard magic trick

In the small town of Terni (Italy), there's a couple of young friends named Marco and Leonardo, who like to perform magic tricks to a restricted audience of common friends and relatives. They like to ...
30
votes
18answers
30k views

Draw a line through all doors

I saw the following problem on 4chan and couldn't solve it: It's very likely to be some kind of troll (no solution). I'm hoping to see some rigorous proofs that disprove the existence of such a line....
14
votes
2answers
18k views

What's the fewest weights you need to balance any weight from 1 to 40 pounds?

Suppose you want to create a set of weights so that any object with an integer weight from 1 to 40 pounds can be balanced on a two-sided scale by placing a certain combination of these weights onto ...
15
votes
1answer
960 views

One beer too many

You're standing outside your apartment building after a late night out, with perhaps one beer too many, and you realize you have completely forgotten the code to get in. Luckily, you're a mathematical ...
9
votes
4answers
2k views

How many different non congruent polygons can you make on a 3x3 dot grid?

There is a $3\times3$ dot grid. How many different non-congruent polygons can you make on the grid? Rules: All vertices of the polygon must be on the grid Only non self intersecting polygons Only ...
79
votes
18answers
15k views

Nine gangsters and a gold bar

One night nine gangsters stole a gold bar. When the time came for dividing the bar, they faced a problem: two of the criminals put guns to each other's faces. Now it's up to fate whether one of them ...
18
votes
4answers
2k views

The 8-dimensional vegetable kebab

You are given two of each from the array of 8 vegetables numbered 1 to 8 as shown above. So in total you have 16 veggies(8 pairs). Your task is to make the longest kebab (sequence of vegetables ...
12
votes
5answers
1k views

99 Bags of Apples and Oranges

You have $99$ bags, each containing various numbers of apples and oranges. Prove that there exist $50$ bags among these which together contain at least half the apples and at least half the oranges. ...
6
votes
2answers
2k views

Minimum moves to have all coins face Heads up

Given a circular list of coins, that all have Tails facing up. In each move, if we flip the coin at position $i$, then the coins at positions $i-1$ and $i+1$ get flipped as well. That is, consider: H ...
8
votes
2answers
693 views

Termite eating through a large cube composed of 27 smaller cubes while not moving diagonally

The is a large cube formed by gluing together 27 smaller cubes of uniform size (see figure). A termite starts at the center of a face of any of the outside cubes and bores a path that takes him once ...
6
votes
3answers
3k views

Flip one of the 64 coins on chess board [duplicate]

I know the answer of this puzzle. I want to know does this puzzle works perfectly for every n × n chess board? Is there a upper bound to n? What is the upper bound for n, if m coins are allowed to ...
43
votes
3answers
3k views

Relabeling two 20-sided dice without changing their total

Usually, 20-sided dice are labeled with the numbers 1 to 20. When you roll two of these, their sum is a random number between 2 and 40. The total 21 is most likely to occur, while 2 and 40 are the ...
30
votes
5answers
6k views

Two spies throwing stones into a river

There is a puzzle about two spies: Two spies must pass each other two secret numbers (one number per spy), unnoticed by their enemies. They have agreed on a method for doing this using only 26 ...
36
votes
9answers
4k views

Filling an 11-by-11 square

Is it possible to fill the $121$ entries in an $11\times11$ square with the values $0,+1,-1$, so that the row sums and column sums are $22$ distinct numbers?
24
votes
4answers
11k views

Plant 9 trees in 10 rows of 3

"Tree-planting" puzzles are also known as "points and lines" puzzles. The English puzzle author and mathematician Henry Ernest Dudeney was very fond of them. In 1917, Dudeney published a collection ...
19
votes
4answers
1k views

Magician's hide and seek with 8 cards

This question is a followup to this question by @Wen1now. After demonstrating the previous trick, the magician decided to make things a bit harder, discarding some cards so that only eight were left. ...
21
votes
6answers
2k views

A game with 52 cards

Alice and Bob play the following game with two (identical) standard decks of $52$ cards. First Alice secretly arranges one deck of $52$ cards in a long row on the table. All cards are face-down, and ...
24
votes
4answers
2k views

Savage Road Signs

There is a highway that starts in the city of Savage. You must must place distance marker signs on this highway for the outgoing traffic. According to highway code, there must be a distance marker ...
19
votes
4answers
1k views

The frog concerto

A pond contains $24$ waterlilies that are arranged in a rectangular $2\times12$ grid (that is, two rows with twelve waterlilies). One evening $24$ frogs give a croaking concerto for the residents of ...
15
votes
6answers
2k views

15 Distinct Weights' Sorting

There are $15$ balls. Each of them has a different weight. You want to sort them according to their weights. You have a friend who will help you with his scale to do this. At each weighing process, ...
23
votes
8answers
4k views

How to choose at least half of everything

Some number of gold, silver, and copper coins are scattered in $N$ chests. You may look into each chest and count each type of coin in them, and then select $M$ of the chests. Your goal is to have at ...
14
votes
1answer
2k views

A classical combinatorial puzzle

It is a classical puzzle by Edsger Dijkstra. Not quoting the original problem but changing it into bag and balls, the puzzle is: A bag contains some black and white balls. The following process is ...
5
votes
2answers
511 views

Paint 7 cells of a 7x7 grid

Can you paint 7 cells of a 7x7 grid such that the largest unpainted rectangle has area of 6 cells? Good luck!
34
votes
9answers
5k views

Can political debates really work?

In the far-off country of Politica, there are three main parties: the Left, the Right, and the Centre. In the last election, there were 19 million Left voters, 21 million Right voters, and 23 million ...
14
votes
2answers
1k views

Crazy Dice - Unusual Dice with Usual Sum

Can you design two six-sided dice (different from the standard ones), where each face has a nonzero number of dots, so that the probability distribution of their total is the same as for two standard ...
9
votes
1answer
2k views

Three button calculator

A calculator has only 3 buttons. The first multiplies the current value by 3, the second adds 2 and the third subtracts 2. Starting with 0 what is the least number of presses you need to reach 100?
5
votes
2answers
3k views

Finding the number of ways of crossing a river

There are $X$ stones in the river.The stones are placed in such a way that a person can jump from one stone to the next one, or skip one and jump to the one after that. Find the number of ways in ...
4
votes
3answers
1k views

Total no of squares on a Chess Board

Is there any formula than calculates the total number of squares on chessboard? For example in a $8\times8$ chessboard, there are squares of sizes $1\times1$, $2\times2$, $\ldots$, $8\times8$. So I ...
12
votes
2answers
2k views

How many squares can you make with equal ranged points?

This question is directly related to How Many Squares on the Peg Solitaire. Is it possible to formulate with a given dimension of equal ranged points $m\times n$ where $m,n\geqslant 2$? For example;...
5
votes
1answer
616 views

Pythagorean coins

To make payments, the Pythagoreans use coins in no more than three denominations. The three denominations are in whole Oboloi amounts, and the sum of the squares of the two smaller denominations ...
10
votes
2answers
3k views

How many Strobogrammatic numbers are there from 0 to 99999

0,1,2,5,8,11,69,96 are Strobogrammatic numbers. We call a Strobogrammatic numbers if: When it is typed on a calculator, and the calculator is spun 180 degrees, the number visually looks the ...
8
votes
1answer
438 views

How many friends does Tiffany have?

Tiffany has 14 classmates; all of her classmates have a different number of friends in the class. How many of them are friends with Tiffany? (If A is a friend of B, then B is a friend of A.)
7
votes
4answers
295 views

Savage Road Signs (Part 2)

Please read part 1 or this might be confusing Since part 1, you have replaced the stolen stickers and your daughter has forgiven you. The highway ended up being a full 700km long, so you are happy ...
6
votes
3answers
2k views

Coloring an n by n grid with four colors

This is a generalization of Place 4x12 detainees on a 7x7 grid of cells. The goal is to color the squares of an $n\times n$ grid with four colors such that at most one square is uncolored no two ...
5
votes
2answers
581 views

Knights covering a 10x10 chess board

What is the minimum number of knights you need to place on a 10x10 chess board, such that every empty cell is attacked by at least one knight? Good luck!
32
votes
11answers
3k views

Coin weighing with a single weighing device

You have 12 coins which each weigh either 20 grams or 10 grams. Each is labelled from 1 to 12 so you can tell the coins apart. You have one weighing device as well. At each turn you can put as many ...
30
votes
8answers
2k views

Wolves and sheep

All the sheep were living peacefully in the Land of Shewo. But suddenly they were struck by a danger. A few wolves dressed up as sheep entered the territory of Shewo and started killing the sheep one ...
16
votes
3answers
2k views

Four buttons on a table

I was asked lately (in an interview) to solve this puzzle, which is similar to the 4 cups on table puzzle. In a certain room there is a rotating round table, with 4 symmetrically located ...
16
votes
1answer
829 views

Rotationpuzzle in hex - The journey beyond the tomb

This is the 3rd themed puzzle of the tomb. (See puzzle 1 and puzzle 2) It is fully independent of the other two and just linked by the common story. After you set the colour-puzzle dials to the right ...
15
votes
3answers
1k views

N-dimensional Tic-Tac-Toe variant

Consider the game surface to be an infinite N dimensional Cartesian lattice. The rules are X moves first, but O gets to move ...
16
votes
2answers
1k views

Automatically a Knight, Knave, and Joker

Let M be a finite positive integer. It's exact value is not known. Suppose we have three classes of automaton, all of which accept a bit stream as input, produce a bit stream as output (one bit per ...
16
votes
5answers
775 views

Maximize the number of paths

You have exactly 990 edges. Assemble them into a simple undirected graph with two distinguished vertices A and B, such that the number of different simple paths from A to B is as large as you can make ...
13
votes
2answers
806 views

The impossible digital sum

There are 10 digit numbers you are supposed to use shown as below; And there is a very special addition where every digit is used only once. As you see, most of the digital signals (blue squares) are ...
8
votes
3answers
566 views

How Many Squares on the Peg Solitaire

We have a well known peg solitaire which is not played yet as seen below: At most how many squares can you make by joining the points as exemplified below? Note: No ball (point) in the middle! so ...
54
votes
3answers
5k views

All numbers in a 5x5 Minesweeper grid

Can you place mines on a 5x5 Minesweeper grid such that each number from 0 to 8 appears exactly once? Good luck!
13
votes
5answers
1k views

A row of 2015 red and white chips

There is a row of 2015 chips, of which 2014 are white and one is red. You are allowed to make moves of the following type: "Choose one red chip, and flip the colors of its two neighboring chips (from ...
25
votes
2answers
4k views

Two chessmasters at work

Viswanathan Anand plays a chess game against Magnus Carlsen. Anand plays white and Magnus plays black. They use a non-standard digital double chess clock that is counting up from zero (instead of the ...