Questions tagged [combinatorics]
A puzzle based on combinatorics, which is the study of counting discrete structures. Use with [mathematics]
206
questions
70
votes
7
answers
129k
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 ...
user88
12
votes
4
answers
13k
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 ...
user88
13
votes
4
answers
2k
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-...
- 474
23
votes
4
answers
3k
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 ...
- 1,313
23
votes
5
answers
35k
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 ...
user88
47
votes
4
answers
10k
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 ...
- 2,555
33
votes
18
answers
68k
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....
- 1,079
22
votes
8
answers
6k
views
Queens attacking exactly one queen
What is the most number of black and white queens that you can place on a standard 8x8 chess board, such that each queen attacks exactly one opponent queen?
- 33.2k
15
votes
1
answer
1k
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 ...
- 696
88
votes
18
answers
17k
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 ...
- 1,317
34
votes
9
answers
6k
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 ...
- 1,198
29
votes
5
answers
18k
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 ...
- 11.2k
15
votes
2
answers
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 ...
- 32.1k
8
votes
1
answer
624
views
How many friends does Tiffany have? [closed]
Tiffany has 14 classmates. This means that there are a total of 15 students in the class. All of her 14 classmates have a different number of friends in the class. Tiffany, however, may have the same ...
- 89
8
votes
6
answers
3k
views
How many different non congruent polygons can you make on a 3x3 dot grid?
There is a 3×3 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 polygons ...
- 197
44
votes
3
answers
4k
views
Controlling a robot blindfolded on a 9x9 grid
A robot is located somewhere inside a 9x9 grid shown below, but you don't know where it is. You can send commands to the robot to make it move one cell left, right, up or down. Shaded areas and edges ...
- 33.2k
29
votes
4
answers
4k
views
Creating the hardest 6x6 maze
You are given an empty 6x6 grid. You are allowed to paint some of its cells as walls (black), while the remaining cells stay empty (white). A robot is programmed to start in the top-left corner of the ...
- 33.2k
26
votes
4
answers
3k
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 ...
- 3,808
19
votes
4
answers
4k
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 ...
- 325
18
votes
1
answer
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 to ...
- 7,262
17
votes
4
answers
1k
views
How many possible starting positions are uniquely solvable for a nonogram puzzle?
This type of puzzle goes by many names: Nonogram, Picross, and Griddlers are all mentioned on the Wikipedia page, Simon Tatham calls it Pattern, I was introduced to it as Descartes Rainbow, ...
The ...
- 116k
14
votes
3
answers
2k
views
How many distinct pentominoes are possible to place on an 8 x 8 board?
Rules
Place some pentominoes into an 8 x 8 grid. They do not touch each other. They can touch only diagonally (with corner).
Pentominoes cannot repeat in the grid. Rotations and reflections of a ...
- 141
13
votes
4
answers
1k
views
Neighboring sums 4x4 game
Here is an interesting game. You start with an empty 4x4 grid. At each turn you can choose an empty cell and place a value in it. The placed value is given by the following rules:
If the chosen cell ...
- 33.2k
13
votes
5
answers
2k
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.
...
- 32.1k
13
votes
7
answers
963
views
Minimize the longest King chain on a 5x5 binary board
Given a grid filled with numbers, let's define a King chain to be a path on the grid such that
the path can be traversed with chess King's moves (moving to one of 8 adjacent cells at a time),
the ...
- 11.6k
10
votes
2
answers
1k
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 ...
- 1,213
9
votes
3
answers
1k
views
Calendar Cubes are Impossible!
An easy one for the middle of the week!
Jane and John were discussing a business idea. John wanted to make a little set to keep track of the date. It was to include two cubes with a single digit on ...
- 22.8k
7
votes
3
answers
11k
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 ...
- 741
6
votes
2
answers
1k
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!
- 33.2k
6
votes
2
answers
3k
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 ...
- 163
2
votes
2
answers
433
views
Two genies and their kind of chess
While playing chess Parcly and Tori Taxel, best friends and genies, got bored and transformed all the pieces into pawns to make pretty patterns. They found this 22-pawn arrangement where every 3×3 ...
- 6,996
51
votes
5
answers
7k
views
A man possesses a large quantity of stamps
James Joseph Sylvester was one the greatest British mathematicians of
the 19th century, who made many fundamental contributions to number theory,
combinatorics, and invariant theory.
In 1884, he ...
- 45.4k
43
votes
3
answers
4k
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 ...
- 32.1k
38
votes
9
answers
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 ...
- 116k
37
votes
9
answers
5k
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?
- 45.4k
34
votes
11
answers
4k
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 ...
- 7,050
31
votes
5
answers
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 ...
- 16.1k
25
votes
8
answers
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 ...
- 16.1k
22
votes
6
answers
3k
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 ...
- 45.4k
21
votes
4
answers
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. ...
- 1,987
21
votes
4
answers
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 ...
- 45.4k
18
votes
5
answers
1k
views
Board with all 2020s
Zeroes are written in all cells of a $5 \times 5$ board. We can take an arbitrary cell and increase by 1 the number in this cell and all cells having a common side with it. Is it possible to obtain ...
- 880
16
votes
2
answers
1k
views
7x7 Golomb square
Can you paint $7$ cells of a $7 \times 7$ grid such that the Euclidean distance* between any pair of painted cells is distinct? Good luck!
*The Euclidean distance between cells $(r_1,c_1)$ and $(r_2,...
- 33.2k
16
votes
1
answer
2k
views
Do Langford squares exist?
A Langford sequence is a permutation of the sequence of 2n numbers 1, 1, 2, 2, ..., n, n in which there is one number between the two 1s, there are two numbers between the two 2s, and more generally ...
- 5,877
15
votes
4
answers
2k
views
Creating the hardest 10x10 maze
You are given an empty 10x10 grid. You are allowed to paint some of its cells as walls (black), while the remaining cells stay empty (white). A robot is programmed to start in the top-left corner of ...
- 33.2k
15
votes
6
answers
3k
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, ...
- 151
15
votes
4
answers
2k
views
Professor Halfbrain's chessboard theorems
Professor Halfbrain has spent his last weekend with analyzing $n\times n$ chessboards. Halfbrain says that a subset $S$ of squares on such a chessboard is queen-connected, if a chess queen can move ...
- 45.4k
14
votes
2
answers
6k
views
A Guide to the Number Rotation Puzzle
This is an extension of What is the strategy to solve Simon Tatham's Twiddle? in that it explicitly goes beyond the default gamemodes of Twiddle
The Number Rotation Puzzle (NRP) is a combination ...
- 9,892
13
votes
5
answers
2k
views
Chess pieces attacking exactly once
Inspired by this question. Actually the same but in a more generic manner.
What is the maximum number of chess pieces of the same type (e.g. kings, bishops, rooks, knights) which can be placed on a ...
- 11.3k
12
votes
2
answers
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;...
- 30.2k