Questions tagged [combinatorics]
A puzzle based on combinatorics, which is the study of counting discrete structures. Use with [mathematics]
809
questions
5
votes
3
answers
394
views
What is the expected time this will take?
There are n white balls and m black balls in a bag. Select 2 balls randomly, if they're the same color, repaint both balls white, else repaint both balls black, then replace both balls in the bag. ...
- 171
11
votes
7
answers
2k
views
The hat-check problem
Six men go to the theatre and leave their hats at the cloakroom.
During the play there is a power cut, the six men leave, but it's dark, so the hats are handed back to them at random.
Someone says: ...
- 321
2
votes
1
answer
377
views
How many of the 16 cells of the grid could contain the black dot?
Beginner puzzle
This puzzle is intended to be suitable for people who are new to puzzle solving.
Clarification: Both experienced solvers and new solvers are welcome to post solutions to this puzzle.
...
- 15.8k
15
votes
1
answer
2k
views
The shortest way from A1 to B1
On the square A1 of a regular chessboard is a regular dice, face 1 up and face 2 in front. The only allowed move is to rotate the dice by 90 degrees to an adjacent square.
Find the shortest way from ...
- 581
5
votes
2
answers
893
views
8x8 grid with no unmarked L-pentomino
What is the minimum number of cells on a 8x8 chessboard that need to be marked so that the unmarked cells do not contain an L-pentomino?
An L-pentomino looks like
...
- 1,498
1
vote
0
answers
100
views
How many squares in a large square [closed]
How many squares of all sizes can be found on a large square made of 10000 small squares? I don't want to try them out or count them. I tried finding a pattern, as in a square made of 1^2 small square ...
- 19
1
vote
0
answers
124
views
Strategy for determining graph traversal rules yielding exactly one distinct graph traversal under every permutation [closed]
I am looking for advice/guidance/solutions which can help me with the following problem:
Imagine a spatial graph in the x,y-plane arranged in an m x n grid
e.g. a 4x4 grid
Each vertex in the graph ...
- 111
2
votes
1
answer
280
views
Strategy for solving "Hypatian Enigma" puzzle (all lines add to 38)
The "Hypatian Enigma" puzzle consists of 19 hexagonal blocks numbered 1 through 19.
The blocks are arranged in 5 rows. The first and last rows have 3 blocks, the second and fourth row has 4 ...
- 121
5
votes
1
answer
375
views
Filling a rectangular grid with holes using tetrominoes
There is a rectangular grid of $R$ rows and $C$ columns. $R \times C \bmod 4$ of the cells are painted black, and all other cells are white. In other words, there are at least 0 and at most 3 black ...
- 17k
13
votes
2
answers
612
views
The HH vs HT question
My puzzle is based on this tweet (image):
Flip a fair coin 100 times—it gives a sequence of heads (H) and tails (T). For each HH in the sequence of flips, Alice gets a point; for each HT, Bob does, ...
- 32.6k
2
votes
0
answers
160
views
A quantum physics puzzle [closed]
A new mathematical approach to quantum physics via graphs was found recently, see this paper for more details. It particular, it refers to
papers by Anton Zeilinger, a Nobel laureate in physics of ...
- 231
0
votes
1
answer
212
views
Tile dominoes in a 3x10 space [closed]
How many ways are there to tile 1x2 (unmarked) dominoes in a 3x10 space?
This is a harder version of Tile dominoes in a 2x10 space, since that was too easy.
- 989
20
votes
3
answers
1k
views
Keys and Locks Puzzle
Let $a,b,n$ be positive integers in which $a,b\le n$. You are locked in a room, with $n$ distinguishable keys and $n$ distinguishable locks in it. You know that each lock can be unlocked by a unique ...
- 6,314
5
votes
2
answers
534
views
Rubik's Cube with no two squares of the same color on any horizontal, vertical or diagonal line
Consider the 12 lines depicted below which all run through the centers of the 9 color squares of a single face of Rubik's Cube.
Can you find a scramble such that on each line all squares have ...
- 1,861
5
votes
2
answers
533
views
Number of 3x3 One Up puzzles
Rodolfo Kurchan created a wonderful new grid puzzle called One Up that you can play on his website. There is one main rule:
Each horizontal and vertical sequence of N cells between walls, must contain ...
- 36.9k
2
votes
2
answers
396
views
Tournament Scheduling Puzzle
I have an interesting real life problem that can be turned into an interesting puzzle pertaining to a tournament that can be represented in this way: I have 24 people which are assigned numbers 1 to ...
- 29
3
votes
5
answers
1k
views
Professor Rackbrane: Count the triangles
Professor Rackbrane has just given me the following puzzle as an example of those that interested his party at Christmas. Draw a pentagon, and connect each point with every other point by straight ...
- 15.8k
7
votes
1
answer
593
views
The governor's birthday puzzle
The prison governor surveys the three petty thieves in his panopticon.
"Next week is my birthday. I've a mind to free some of you, if you can solve a little puzzle of mine."
"I'm going ...
- 912
3
votes
3
answers
278
views
All poker hands from a single deck
This question suggested itself to me – and I found a solution – after I solved Can you balance this poker deck?.
Take out two aces from the standard 52-card deck. Your challenge is to partition the ...
- 7,820
4
votes
1
answer
283
views
Can you balance this poker deck?
You are given the digits 0 to 9 in 4 poker suits.
Distribute them onto the 8 highest poker hands (make one of each) of 5 digits each. They are
Royal Flush (9 to 5 of one suit)
Straight Flush (...
- 389
14
votes
5
answers
2k
views
General attacking chessboard squares
This is a general version of this beautiful puzzle.
Place any number of standard chess pieces on a 8x8 chessboard, such that there is at least 1 empty square attacked by exactly 1 piece, at least 1 ...
- 36.9k
-4
votes
1
answer
125
views
Binary Grid Challenge and X & O Conundrum
You are given a 5x5 grid with some cells filled with either "X" or "O". Your goal is to fill the remaining cells with "X" or "O" following these rules:
Each row ...
- 109
1
vote
1
answer
209
views
Maximum filled days
I have two types of items, $i_1$ and $i_2$. $i_1$ items can be used at most $50$ times and $i_2$ items can be used at most $120$ times.
I have $7000$ items $i_1$ and $800$ items $i_2$.
Each item $i\in ...
- 6,504
5
votes
1
answer
977
views
Anna and Boris play the Red Blue game
Anna and Boris play a game on a 9x9 chessboard. Anna goes first and turns alternate thereafter. In each move, Anna puts a red counter on a vacant square while Boris puts a blue counter on a vacant ...
- 15.8k
2
votes
0
answers
89
views
An array of light-bulbs [duplicate]
There is a grid of 2024 by 2024 light-bulbs. Initially, all bulbs are off.
You can switch the state of all 2024 bulbs in a row simultaneously, or all 2024 bulbs in a column simultaneously, and do this ...
18
votes
1
answer
690
views
Alphabetic string theory
According to alphabetic string theory, the words we see are merely the visible portions of highly convoluted loops of multi-dimensional alphabetic string.
For example, here is what we see in our space-...
- 14k
2
votes
1
answer
279
views
Nimber mnemonic combinatorial puzzle
Please see my previous question for more background.
The following represents an unfolded version of PG(3,2) with 1 as the center point:
Given that each number must be an end point of a line which ...
- 53
2
votes
1
answer
249
views
Nimber Mnemonics
Note
I originally tried to ask a variation of this question on math.stack; however 1 commenter pointed out that math.stack is not a puzzle site, which made me think maybe the fine folks of puzzling ...
- 53
3
votes
1
answer
269
views
Longest subsequences and shortest longest ones
This challenge is about permutations of the integers 1 to 30 with longest increasing subsequence length 3. An important part of the definition is that a
subsequence is not necessarily contiguous or ...
- 8,057
-2
votes
1
answer
176
views
If there are 6 men and 6 women around a table, what's the probability that both groups are joined in a single cluster each? [closed]
Suppose we have twelve people: six men and six women. They randomly sat around a circular table. What's the probability that both male and female groups accidentally formed a single conjoined cluster ...
- 605
0
votes
3
answers
182
views
Counting puzzle #1: Function combinations
Not in conjunction with my function optimization puzzles, also sorry for the extremely difficult discrete mathematics puzzle
So as you may or may not know, I have recently uploaded 2 function ...
- 2,423
3
votes
3
answers
458
views
5x5 grid with a special colouring
Can you paint the cells of a 5x5 grid in 5 colours such that for each cell its colour and the colour of its orthogonal (horizontal and vertical) neighbours are all different?
- 36.9k
19
votes
3
answers
2k
views
Playing Mastermind against an angel and the devil
This puzzle is based on a card game. There are 7 suspects and 3 of them committed a crime. The game contains 35 cards that contain the 35 possible choices of 3 out of the 7 suspects. One card is drawn ...
- 2,074
1
vote
1
answer
314
views
How many 4x4 Latin Squares are there?
I thought of this problem when playing Sudoku. Let A = {1,2,3,4}. I have to make a 4x4 box (i.e. the size of A in both dimensions) and fill it with data such that ...
- 11
5
votes
1
answer
354
views
Permutations with given longest increasing subsequence
How many permutations of 1 to 20 are there with 2,5,6,9,13
as a longest increasing subsequence? (It may be tied with others.)
- 8,057
1
vote
2
answers
1k
views
16 queens puzzle
Can you place 8 white queens and 8 black queens on an 8x8 grid, such that no two queens of the same colour occupy the same row, column or diagonal?
- 36.9k
9
votes
1
answer
441
views
Closed path on a dodecahedron
Your task is to draw lines between edges on a regular pentagon such that if you tile a dodecahedron with 12 identical copies of that pentagon you get a single closed line which does not intersect ...
- 1,861
50
votes
4
answers
3k
views
A colorful dodecahedron
Divide a "base" edge of a regular pentagon into three equal parts. Then draw two lines from the base to the center of the other edges such that the lines do not intersect. This splits the ...
- 1,861
1
vote
1
answer
656
views
Tile 1x2 dominoes in a 2x10 space
How many ways are there to tile unmarked 1x2 dominoes in a 2x10 space?
Bonus: What if the dominoes were identical and had pips on their front (face-up), so they could be distinguished by 180 degree ...
- 989
10
votes
2
answers
729
views
Pay each amount with at most two coins
Euro cent coins come in the denominations 1, 2, 5, 10, 20 and 50 cents.
You are inconvenienced by the fact that you need a lot of coins to pay each amount up to 100 cents. To pay 99 cents, you need 6 ...
- 103
1
vote
1
answer
211
views
11
votes
2
answers
496
views
Tiling a dodecahedron
The surface of a dodecahedron is tiled with 6 of the shown tiles, each tile covering two faces of the dodecahedron. In how many essentially different ways this can be done?
Two tiled dodecahedrons are ...
- 1,861
5
votes
1
answer
443
views
Counting Tic-Tac-Toe draws on larger grids
Alice and Bob play a game of Tic-Tac-Toe on a grid of size $N \times M$. The rules of this game are the same as the original Tic-Tac-Toe:
Alice plays first (white); Bob plays second (black).
On each ...
- 17k
6
votes
1
answer
284
views
Permuting officers during a Chess960 game
There are... let me see... ah yes 960 different possible starting positions in Chess960.
Suppose the players never move a pawn, or make a capture, but simply move their officers so that eventually ...
- 1,919
11
votes
6
answers
2k
views
The shorter the message, the larger the prize (version II)
This is a successor question to The shorter the message, the larger the prize . For completeness I will include the entire question even though only the numbers have changed. Solutions to this puzzle ...
- 8,057
14
votes
1
answer
1k
views
The shorter the message, the larger the prize
Andrei and Belle have been set a task by their “friend”, Carroll. Carroll has promised them money depending on how well they do.
Carroll will give a 99 bit array to Andrei and a different one to ...
- 8,057
5
votes
1
answer
600
views
What is the number of ways to spell French word « chrysanthème »?
As many people know, theoretically a lot of words have more than one way to be spelled. I just want to provide a single example from English language: the word "fish". As Bernard Shaw noted, ...
- 605
17
votes
5
answers
4k
views
5 chess pieces dominating a 5x5 grid
This is a puzzle based on work by Rodolfo Kurchan.
Can you place a pawn, a knight, a bishop, a rook and a king on a 5x5 chess grid, such that every empty cell is attacked by at least one piece? Note ...
- 36.9k
69
votes
1
answer
3k
views
Alphabet snake, master of camouflage
The alphabet snake
is a master of camouflage. It finds a section of text in an old book or newspaper...
...crawls upon it...
...and disappears.
Now see if your camouflage skills can match those ...
- 14k
5
votes
1
answer
347
views
Nuts and screws
Imagine that you are given a box with n nuts and n screws. Each screw have different size (diameter) and on each screw there is ...
- 263