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
2
votes
1answer
79 views

4x4 square with no increasing triples

Can you fill a 4x4 grid with numbers from 1 to 4 such that: Every number occurs exactly once in each row and in each column (Latin square). No row or column contains 3 adjacent numbers that are all ...
-4
votes
6answers
666 views

Somebody ordered a pizza

Somebody ordered a pizza. They ordered X slices with pepperoni, Y slices with mushrooms, and Z slices with cheese. If no two slices were identical, and no combinations of toppings were not present, ...
8
votes
2answers
1k views

How many descendants can this spaceship crew produce?

A spaceship is on a very long voyage. It starts with a crew of 4 women and 4 men, none of whom are related by blood. How many descendants at most can this 8-person crew produce without inbreeding? ...
3
votes
1answer
195 views

Moving coins in a grid

Here is a great puzzle from Ed Pegg Jr. Place two coins in the center cell of the following grid. Now you can choose a coin X and move the second coin Y one cell in the direction of the arrow under ...
4
votes
2answers
244 views

Place 4 players to make 6 distances between pairs

Is it possible to place 4 players on a football field in such a way that the 6 distances between every pair of them are 1, 2, 3, 4, 5, 6 meters? Source: Moscow Math Olympiad 2001 (Look Inside to Page ...
8
votes
2answers
385 views

Rack 'Em Up! 🎱

In a game of English eight-ball pool, a set of 15 balls are arranged or 'racked' in the shape of an equilateral triangle. In order for the balls to be racked fairly, they must be arranged like so: <...
1
vote
1answer
154 views

Cut the string!

There are five pieces of blue string on the table with different lengths, the total length of which is 30 cm. There are also five pieces of red string with different lengths, the total length of which ...
14
votes
3answers
1k views

The maximum period of dancing program

Sixteen people named A, B, ..., P are standing in line in the order ABC...P. They "dance", or swap places, according to some predefined instructions. ...
9
votes
5answers
1k views

Professor Halfbrain and the 9x9 chessboard (Part 2)

This puzzle is the continuation of Professor Halfbrain and the 9x9 chessboard (Part 1). The difference is that "distance at least $2$" has now become "distance more than $2$". ...
12
votes
3answers
906 views

8 soldiers lining up for the morning assembly

There are 8 soldiers, gathering and lining up every morning for their military service. The commander at the head of these soldiers demands that the morning lineup of these soldiers be arranged ...
3
votes
2answers
157 views

Generalized rectangular tilings with no "fault lines"

I recently came across this question: One rectangle, indivisible The goal is, by tiling 2x1 rectangles, to create a larger rectangle that cannot be split into 2 smaller rectangles. But my question is ...
15
votes
6answers
1k views

Tommy's Train Tracks

Tommy just got a new train set. It only came with one type of train track piece, a quarter circle, all of which were the same size. $\hspace{2.5in}$ Prove that, whenever Tommy makes a closed loop ...
4
votes
2answers
341 views

The 7 face up/down card

Note: This puzzle is a very old puzzle I got from the Internet, however I changed it a bit to be more interesting. INSTRUCTIONS You have got 7 blank cards. You are playing with a friend of yours. Your ...
4
votes
1answer
272 views

Grids with trominoes

Let's have two 8x8 grids. By visual inspection we see they are filled with trominoes of three different colors. There are 7 trominoes of each color. On the grids the trominoes are not allowed to touch ...
-3
votes
1answer
145 views

a 17X17 grid filled with trominoes of three different colors

Let's have an 17x17 grid. We can fill this grid with 96 trominoes of three different colors, 32 trominoes of each color. On this particular grid the empty single square is the position A1. By visual ...
6
votes
1answer
290 views

Alice and Bob playing Neighboring Sums Game

Alice and Bob are playing the neighbouring game which is originally single game to get the highest point at the end. You start with an empty 4x4 grid. At each turn you can choose an empty cell and ...
7
votes
2answers
353 views

Pentomino tiling on wrap-around 5x5 grids

It is known that P pentominoes cannot tile a 5x5 square board. Q1: If the east and west edges of the 5x5 square board are "wrapping around" (if you move a piece through one of the edges, the ...
37
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 ...
9
votes
1answer
637 views

Puzzles like Sokoban?

I am looking for some puzzles like Sokoban or 15-puzzle but more difficult to solve and satisfy the following requirements: The number of possible moves at each step should be limited, let's say < ...
-2
votes
1answer
240 views

How many shapes can you form with squares? [closed]

There is a 6 by 6 dot-grid. You will draw two squares by joining the dots. The squares cannot have common dots/points or areas. Rotations or reflections of a drawing are considered distinct. In How ...
5
votes
3answers
316 views

Optimal Strategy for Matching Pairs

I found a reality TV show recently that I thought would make a fun puzzle. On the show are 10 men and 10 women that have been "matched by experts" (ie. randomly paired). Their goal is to ...
2
votes
1answer
311 views

Forming pairs of trominoes on an 8X8 grid

On an 8x8 grid I put 21 trominoes of thee different colors. Each group of 7 trominoes has one color. By visual inspection we see the trominoes cover the whole surface except the single empty square ...
7
votes
4answers
803 views

Neighboring sums 5x5 game

You start with an empty 5x5 grid. At each turn you choose an empty cell and place a value in it. The placed value is given by the following rules: If the chosen cell has no neighboring (horizontal or ...
3
votes
1answer
217 views

n rows and 18 columns

I haven't posted for a long long time, so here is an interesting combinatorics problem! There is a table with 𝑛 rows and 18 columns. Each of its cells contains a 0 or a 1. The table satisfies the ...
11
votes
4answers
967 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 ...
-3
votes
1answer
145 views

Self-intersecting polygonal chains in a hexagon [closed]

This is continuation of this Q&A. Given a regular hexagon with center at point O: Question: How many self-intersecting polygonal chains are there that connect 7 points? The self-intersecting ...
5
votes
4answers
598 views

Every tournament has a dominant player

A tournament was played round-robin: each pair of players played a match where one defeated the other. Prove that there was a player for which every other player either lost to them or lost to someone ...
6
votes
1answer
195 views

Plus-sized amoeba escapes

As an extension to @WhatsUp 's question here, the rules of which are included below, with the following differences: In one of the squares, there lives an amoeba (marked as a circle in the following ...
21
votes
2answers
749 views

Amoebas escaping the prison

There is an infinite grid of squares. In one of the squares, there lives an amoeba (marked as a circle in the following pictures). Amoebas cannot move, but they can perform their unique action: an ...
2
votes
2answers
144 views

Prime stepping stones

Start by placing number $1$ anywhere on an infinite square grid. Now place numbers $2, 3, 4, \ldots, K$ in order. A number $k$ can be placed if the following rules hold: It must be adjacent (...
0
votes
2answers
101 views

Car registration similarity [closed]

In my city, car registration plates contain 3 numbers (0 to 9) and 3 letters (A to Z). Today I've noticed that my neighbour's car has the same registration as my car except for one character. Should I ...
10
votes
2answers
506 views

What is the minimum number of problems in the pool? [closed]

Using a pool of problems, 16 tests will be formed, following certain conditions: Every test should have the same number of problems. Any problem should be included in at most 8 tests. Every group of ...
25
votes
12answers
4k views

Tiling a Hexagon with Diamonds

A regular hexagon is divided into a triangular grid, and completely tiled with diamonds (two triangles glued together). Diamonds can be placed in one of three orientations. Prove that, no matter how ...
8
votes
1answer
229 views

Generalized color balls in a 4x4 grid

This is a generalization of the Colored balls in a 4x4 grid puzzle that was proposed by Darrel Hoffman. Colored balls from 4 different colors are placed in a 4x4 grid. There is at least one ball from ...
13
votes
1answer
559 views

The tip of a colorful triangle

Original source: Problem 1 of British Informatics Olympiad 2017, Round 1 You're given a bunch of red (R), green (G), and blue (B) balls. I arrange some balls on a line. Then I ask you to complete the ...
7
votes
1answer
182 views

My two button microwave

Long ago, I encountered a microwave with a display in the "HH:MM:SS" format. But instead of a number pad, you entered the desired time through two buttons: An "up" button, which ...
1
vote
3answers
179 views

How many ways are there to read 5556789 without repeating digits?

The problem is as follows: The figure below shows a triangular arrangement with a set of numbers. Each time you read a number, you cannot repeat the same digit and the distance between the digits ...
9
votes
2answers
389 views

Maximize my flags

You are given the next list of 48 flags. For each pair of flags that are side by side, you score 1 point per color they share as a frontier. For instance France and Finland score 1 point thanks to ...
8
votes
4answers
1k views

Colored balls in a 4x4 grid

Colored balls are placed in a 4x4 grid. A move consists of swapping two adjacent (horizontally or vertically) balls. What is the least number of moves required to form 4 connected components*, one for ...
4
votes
1answer
241 views

Most 5s in a 5x5 Super Minesweeper grid

In a Super™ Minesweeper grid each cell is either a mine or a value. A value in row $𝑟$ and column $𝑐$ represents the total number of mines located in row $𝑟$ or column $𝑐$. What is the most number ...
5
votes
1answer
460 views

All values in a 6x6 Super Minesweeper grid

In a Super™ Minesweeper grid each cell is either a mine or a value. A value in row $𝑟$ and column $𝑐$ represents the total number of mines located in row $𝑟$ or column $𝑐$ Can you fill a 6x6 Super™...
10
votes
1answer
680 views

All values in a 5x5 Super Minesweeper grid

In a Super™ Minesweeper grid each cell is either a mine or a value. A value in row $r$ and column $c$ represents the total number of mines located in row $r$ or column $c$. Can you fill a 5x5 Super™ ...
3
votes
1answer
200 views

Variation of 100 Prisoners' names in boxes

100 Prisoners' Names in Boxes The following puzzle is a variation of the above puzzle. Names in Boxes The names of 4 prisoners are placed in 4 wooden boxes , one name to a box, and the boxes are ...
-1
votes
2answers
331 views

How many triangles can you obtain using the 6 vertices and center of a regular hexagon?

Let's say there is a regular hexagon with center at point O. Question 1. How many triangles can you obtain using the 6 vertices and its center? Question 2. What is the largest number of different ...
5
votes
1answer
153 views

Sorting 9 numbers with 9 flips

You want to sort a sequence of numbers into ascending order. You can perform flips: take a sub-sequence of 4 numbers (a, b, c, d) and reverse their order to obtain (d, c, b, a). Can you sort the ...
3
votes
2answers
145 views

Presidential Election

This puzzle was inspired by the current 2020 US presidential election. You are running for president in a country with 10 states. To win a state you must conduct more rallies than your opponent. ...
3
votes
4answers
162 views

Given pairs of weights find individual values

The problem is as follows: A kid has five marbles. These marbles have different weights and the child weighs them in pairs in all possible ways. He records the weights in his notebook. These are the ...
1
vote
1answer
105 views

Special arrangement of 16 cards

This puzzle is from Martin Gardner. You are given 16 cards containing all aces, kings, queens and jacks from a standard deck of cards. Can you arrange them in a 4x4 grid such that each row and each ...
1
vote
1answer
130 views

Visiting primes on a line

Recently I have been playing a great mobile game called Dicast: Rules of Chaos and it has inspired me to make this puzzle. This puzzle proceeds on an infinite number line, where each integer is ...
14
votes
5answers
1k views

Stepping Stones 1, 2, 3

I came across this beautiful puzzle and decided to create my own version. Start by placing numbers 1, 2 and 3 anywhere on an infinite square grid. Now place numbers 4, 5, 6 ... $m$ in order, subject ...

1 2
3
4 5
15