Questions tagged [combinatorics]

A puzzle based on combinatorics, which is the study of counting discrete structures. Use with [mathematics]

Filter by
Sorted by
Tagged with
1 vote
1 answer
176 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 ...
HelptimeCode's user avatar
5 votes
1 answer
298 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.)
Simd's user avatar
  • 6,627
1 vote
2 answers
966 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?
Dmitry Kamenetsky's user avatar
7 votes
1 answer
378 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 ...
Herbert Kociemba's user avatar
45 votes
4 answers
2k 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 ...
Herbert Kociemba's user avatar
2 votes
1 answer
108 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 ...
qwr's user avatar
  • 693
9 votes
2 answers
633 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 ...
Tilman's user avatar
  • 93
1 vote
1 answer
180 views

Visiting all strings by swapping

Consider the following strings ...
Simd's user avatar
  • 6,627
11 votes
2 answers
403 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 ...
Herbert Kociemba's user avatar
5 votes
1 answer
391 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 ...
Bubbler's user avatar
  • 11.5k
6 votes
1 answer
266 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 ...
Laska's user avatar
  • 1,666
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 ...
Simd's user avatar
  • 6,627
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 ...
Simd's user avatar
  • 6,627
5 votes
1 answer
584 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, ...
Alexander's user avatar
  • 317
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 ...
Dmitry Kamenetsky's user avatar
65 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 ...
SlowMagic's user avatar
  • 13.4k
5 votes
1 answer
325 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 ...
popcorn's user avatar
  • 263
0 votes
2 answers
213 views

Counting combinations with two dice

You are given two identical standard dice as shown below. You can stack them one on top of the other, or place them touching side by side. In all cases the face of one die must fully touch the face of ...
Dmitry Kamenetsky's user avatar
6 votes
1 answer
654 views

Cable with mixed wires

Let's say you have a cable that has n wires. Each wire on the left side corresponds to one wire on the right side. However you cannot distinguish between the wires ...
popcorn's user avatar
  • 263
1 vote
1 answer
204 views

How many ways are there to mark a way to walk around every edge of the triforce?

A triforce for the purposes of this question is a plane figure with an equilateral triangle at its center, with one additional vertex connected to each pair of original vertices (forming an additional ...
Cong Chen's user avatar
  • 179
24 votes
1 answer
1k views

Selectively neglected collection

These mannequins are complete and ready for display. These parts were found in a storage closet. Create four additional mannequins by assembling the parts appropriately and designing a suitable ...
SlowMagic's user avatar
  • 13.4k
-1 votes
1 answer
133 views

Rotating teams through stations without repeating a topic?

I am putting together a gallery walk activity and want to rotate 6 teams through 4 unique “topics.” This activity will take place in a rectangular room. There will be 6 “stations” set up. Each station ...
hxksbq's user avatar
  • 11
3 votes
1 answer
351 views

Micropoker: small hands on deck

Raise your hand if you are ready for micropoker, which minimalistically resembles 5-card poker. The deck has just 8 cards with 2 suits of 4 cards each. A hand is dealt as 3 cards that are final, with ...
humn's user avatar
  • 21.8k
5 votes
1 answer
288 views

n*n*n Rubik's cube algorithm

Is there a universally working (I mean, regardless of n) algorithm for Rubik's cube n×n×n ? It is acceptable to divide ...
imida k's user avatar
  • 153
5 votes
1 answer
356 views

Do non-trivial Skolem squares exist?

Define a Skolem sequence to be a permutation of the sequence of 2n numbers 0, 0, 1, 1, 2, 2, ..., n-1, n-1 in which there are no numbers between the two 0s (the 0s are in adjacent positions), there is ...
Will Octagon Gibson's user avatar
6 votes
2 answers
701 views

Attacking Hyenas

$N$ Hyenas are standing on a plane region in a forest. At $t=-1$, they see dead meat nearby. Being selfish, at $t=0$, each Hyena attacks the Hyena which is closest to it. All pairwise distances ...
thisIs4d's user avatar
  • 1,038
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 ...
Will Octagon Gibson's user avatar
3 votes
1 answer
175 views

Creating a clever hemisphere

Given five points on a sphere, can you always draw an equator such that four or more points lie on one hemisphere? How? Points on the equator count as being on either side.
weissguy's user avatar
  • 195
14 votes
3 answers
2k views

Wizard of subsets

Can you change this into this in three moves? You are the wizard of subsets. With only your mind, you can grab any subset of the 16 stone blocks and move them one unit in any direction (north, ...
SlowMagic's user avatar
  • 13.4k
20 votes
7 answers
1k views

Save now! All the digits at half the price

... or double the price depending on where you're coming from Consider the set $PD10$ of pan-digital ten-digit numbers, i.e. positive whole numbers whose decimal representation has each of the digits ...
loopy walt's user avatar
  • 18.2k
6 votes
1 answer
397 views

Clock hands get it Right

I was asked this question in an entrance exam. In one day, how many times the hour hand and the minute hand of a clock are at right angles to each other? My answer was 48. My reasoning was that during ...
user avatar
1 vote
2 answers
177 views

How Many Magic Hexagons that use repeated digits?

There exists only 1 normal magic hexagon that uses non repeating consecutive digits for 1 to 19. If We allow digits to repeat we can create something like this hexagon that is made up using ...
Maff's user avatar
  • 601
8 votes
2 answers
388 views

Colour the positive integers without making a blue equation

This puzzle is related to How do we find the numbers? but has a slightly more striking solution in my opinion. It is also based on one of my MathsSE answers. What is the least number of colours you ...
Parcly Taxel's user avatar
  • 6,954
24 votes
10 answers
4k views

7 mathematicians around the clock in prison

In a very strange kingdom, 7 mathematicians (let's call them Ann, Ben, Cid, Dan, Eve, Flo and Guy) were sent to prison because they did a calculation which was correct, but was not in favor of the ...
theozh's user avatar
  • 1,214
12 votes
6 answers
1k views

Twenty-four coins

I have twenty-four identical-looking coins, but two are fake and weigh possibly different from each other, though definitely different from the remaining genuine coins. I have a weighing scale and a ...
Bernardo Recamán Santos's user avatar
2 votes
1 answer
235 views

Good and bad numbers of remaining mines

You've been tasked with finishing solving this Minesweeper board: "How many mines remain?", you ask. "I'm just choosing that now, actually. Tell you what: I was going to consider every ...
Joseph Sible-Reinstate Monica's user avatar
9 votes
2 answers
524 views

How many Nonconsecutive Sudoku solutions are there?

Consecutive Sudoku is a variant with the additional rule that orthogonally adjacent numbers are consecutive if and only if there is a dot/bar on the line between them. A Nonconsecutive Sudoku is one ...
bobble's user avatar
  • 10.1k
7 votes
1 answer
514 views

Two arcs equal three arcs

(Gonna answer my own question, as is encouraged.) To set the stage: an arc (or a Jordan arc) is a non-self-intersecting curve with two distinct endpoints. (For those who are familiar with topology, it'...
Akiva Weinberger's user avatar
6 votes
1 answer
754 views

Infected squares warmup: infect a 7x7 board with 21 squares

You can consider this a "warmup" to my other question about infected squares. On a $7\times7$ square, some cells are infected; if a cell shares an edge with $3$ infected squares, it becomes ...
Akiva Weinberger's user avatar
8 votes
2 answers
432 views

Infected cubes puzzle in 3D with threshold 4

(This question was previously posted on Math SE, but received no answers.) 3D infected cubes puzzle with threshold $4$: On an $n\times n\times n$ cube, some cells are infected; if a cell shares a ...
Akiva Weinberger's user avatar
9 votes
3 answers
1k views

Tiling a chessboard

Say I have an eleven by eleven chessboard, so there's 121 squares total. I remove the centermost piece so there's 120 pieces. I want to tile the chessboard with 1x4 or 4x1 pieces in a way that none of ...
Joey's user avatar
  • 203
6 votes
3 answers
500 views

More Genuine and Fake Coins

I have 36 identical coins of which four, all weighing the same, are known to be fake. Fake coins are either all heavier than genuine coins, or all lighter. At most how many weighings on a balance ...
Bernardo Recamán Santos's user avatar
0 votes
0 answers
38 views

Impossible tiling of board using dominoes [duplicate]

prove that no matter how you tile a 6 x 6 board using 2 x 1 tiles, there would always be a vertical or horizontal line separating the board. Separation here means that no tile would be cutting across ...
Rishabh Jain's user avatar
12 votes
4 answers
2k views

Prime lights out

You start with a 4x4 grid filled with zeroes. If you press a cell then the cell and all its neighboring (horizontally and vertically) cells will have their numbers increased by 1. What is the most ...
Dmitry Kamenetsky's user avatar
0 votes
2 answers
199 views

How can 8 , 10 or 12 teams rotate through 7 or 8 games without overlaps? [closed]

We are scheduling a big scout event with children, and we have 7 or 8 games organized for them to rotate and play with each other. Set up a game schedule that follows these rules: There are 3 ...
Bill Papadodemas's user avatar
13 votes
1 answer
2k views

The Lufthansa Lottery

In order to pass free time while striking for better pay, some Lufthansa workers organise a lottery where each ticket picks three distinct numbers from $1$ to $11$ inclusive the draw picks five ...
Parcly Taxel's user avatar
  • 6,954
0 votes
1 answer
162 views

Number of 6-person events so all groups of 3/10 people have dined together [closed]

Assume 10 people numbered 1-10 have to be invited for dinner events. However, the hotel can accommodate only 6 at a time. Therefore, they will be invited in batches until all groups of 3 people have ...
2FaceMan's user avatar
  • 103
2 votes
1 answer
287 views

Generalization of twelve balls and scale problem

This problem is a generalization of Twelve balls and a scale problem. So I can solve and understand how things are going if we have 12 balls or 9 balls but how do I generalize? If say we have $3^n$ ...
Charlie's user avatar
  • 635
20 votes
3 answers
2k views

The universal ticket

I am submitting a very interesting problem from a French mathematical recreation site: http://www.diophante.fr/problemes-par-themes/g-probabilites/g2-combinatoire-denombrements/1434-g248-le-billet-...
franck vivien's user avatar
6 votes
2 answers
365 views

Taking turns adding a number 1,2,3 to a 3x3 matrix without repeating numbers in the rows or columns: does the first player always win?

Alice and Bob are playing a game on an initially empty 3x3 matrix. They take turns, and each turn: They add a number in {1,2,3} to an empty cell. They are not allowed to repeat a number in a row or ...
Rebecca J. Stones's user avatar

1
2 3 4 5
16