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
3
votes
1answer
303 views

Two knight tours on a 4x4 grid

Two knights are placed on opposite corners of a 4x4 grid. Can you move* each knight 7 times, such that each cell of the grid is visited exactly once by exactly one of the knights? *Note that a knight ...
-2
votes
1answer
125 views

Minimize the longest King chain on a 6x6 ternary grid

This puzzle is an extension of this one: Minimize the longest King chain on a 5x5 binary board Given a grid filled with numbers, we define a King chain to be a path on the grid such that: The path ...
-2
votes
1answer
101 views

Minimize the longest King chain on a 7x7 binary grid

This puzzle is an extension of this one: Minimize the longest King chain on a 5x5 binary board Given a grid filled with numbers, we define a King chain to be a path on the grid such that: The path ...
6
votes
1answer
170 views

Choosing squares on a square board

I have an $8 \times 8$ board. On the board, I want to choose 2 unit squares in each column and row such that none of the chosen squares are touching. This means they cannot share a side or a corner. ...
3
votes
2answers
83 views

Dividing the first 10 numbers into two groups with similar product

Can you paint all numbers from 2 to 10 with red and blue colour, such that the product of all red numbers is as close as possible to the product of all blue numbers?
-1
votes
0answers
46 views

How to find the number of knight-routes moving upwards to the top of the board [duplicate]

In chess, a knight moves in L-shaped jumps consisting of two squares along a row or column plus one square at a right angle. If it can only move up the board, how many routes can it take to reach any ...
13
votes
7answers
801 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 ...
9
votes
2answers
441 views

Sixteen chess pieces on a square board

It is well known that the eight main chess pieces cannot cover a chess board. Suppose I have two sets of the eight main pieces. What is the size of the largest chess-like square board all of whose ...
13
votes
2answers
2k views

Three queens and two rooks covering the chess board… again!

Three queens and two rooks can be placed on a chess board so that all empty squares are under attack, as has been shown here: 3 queens and 2 rooks covering a 8x8 chess board. What if we require that ...
7
votes
2answers
888 views

21 knights covering a 11x11 chess board

Can you place 21 knights on a 11x11 chess board, such that every empty cell is under attack? Good luck! Here is a similar question for 10x10: Knights covering a 10x10 chess board
4
votes
1answer
820 views

3 queens and 2 rooks covering a 8x8 chess board

Can you place 3 queens and 2 rooks on a 8x8 chess board, such that every empty cell is under attack? Good luck!
3
votes
2answers
189 views

Determine minimal number of moves to find cells on a square table 10×10 in which a treasure is hidden

In a 10x10 square table, two neigbouring 1x1 cells contain a hidden treasure. John needs to guess these cells. In one move he can choose some cell of the table and can get information whether there is ...
2
votes
2answers
485 views

Lightbulbs in a 3×3 square

Suppose we have a $3\times 3$ arrangement of lightbulbs and we switch them on/off randomly (probability $½$). What is the probability the no adjacent bulbs are on? My attempt was: Let $1= $ on and $0 =...
1
vote
2answers
75 views

No four cells forming a rectangle

You are given a 5x5 square grid with 25 cells. Can you paint 12 cells, such that no 4 painted cells form the corners of a rectangle with sides parallel to the edges of the grid? Good luck!
9
votes
3answers
1k views

No three points in a line

You are given a 4x4 square grid. It has 16 cells and 25 grid intersections. Can you place 10 points at grid intersections, such that no three points lie on the same straight line? Lines can be ...
5
votes
2answers
189 views

Running Out of Digits, Level 3

The challenge idea is credited to HelloWorld1337. You initially have x of each digit from 0 to 9. This means you have x * 10 digits in total. This count for each digit is shown in the table below. ...
6
votes
2answers
449 views

Covering a 15x15 grid with rectangles

You are given a 15x15 grid and asked to cover it with rectangles whose dimensions are a power of 2. For example you can use rectangles 8x1 and 4x4, but not 2x3. The rectangles must cover every cell of ...
10
votes
1answer
387 views

Grid infection with diagonal adjacencies

A community consists of 81 houses laid out in a 9 x 9 square grid. Every household is friends with their eight orthogonal and diagonal neighbors (except for the houses on the perimeter which have only ...
13
votes
4answers
609 views

Domino tiling on 8x8 checkerboard with four squares removed

I once posted this problem on the (now deleted) Area 51 Math Puzzles proposal. It was well-received there, but obviously I didn't get an answer. I still don't know the answer, and I'm not even sure if ...
2
votes
4answers
198 views

The Greenhouse Problem version 2

This is an extension of Nilster's great puzzle: The Greenhouse Problem The task is the same, but this time sprinklers cover only a 3x3 square around them. For completeness, here is the full set of ...
2
votes
1answer
166 views

How long will it take to hand out the shuffled papers?

A teacher has $n$ students sit in a circle in her classroom. She holds in her hands a perfectly shuffled stack of the students' graded homework, with Juan's on top. She is currently standing in front ...
4
votes
2answers
277 views

Mathematics for the English major

An entry in Fortnightly Topic Challenge #48: Unusual tag mix I was looking at the unusual tag mixes post, and one of the ones listed is combinatorics and english. I thought "who's going to be ...
1
vote
2answers
209 views

Dividing the first 10 primes into groups whose sum is prime [closed]

Take the first 10 primes. Can you divide them into $g$ disjoint groups, such that the sum of numbers in each group is prime. In particular can you make this work for every value of $g$ in the range $[...
1
vote
3answers
90 views

5x5 grid with no tetrominoes containing repeating colors

Paint the cells of a 5x5 grid with 𝑛 colors, such that every possible tetromino found in the grid uses 4 different colors. What is the smallest value of 𝑛 possible in such a coloring? Here is a ...
3
votes
3answers
354 views

4x4 grid with no trominoes containing repeating colors

Paint the cells of a 4x4 grid with 𝑛 colors, such that every possible tromino found in the grid uses 3 different colors. What is the smallest value of 𝑛 possible in such a coloring?
5
votes
4answers
549 views

8x8 square with no adjacent numbers summing to a prime

Can you fill a 8x8 grid with numbers from 1 to 8 such that: Every number occurs exactly once in each row and in each column (Latin square). No two adjacent (horizontally or vertically) numbers sum to ...
2
votes
1answer
69 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 ...
8
votes
2answers
992 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
184 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 ...
1
vote
1answer
145 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 ...
4
votes
2answers
229 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
353 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: <...
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. ...
12
votes
3answers
877 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
141 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 ...
4
votes
2answers
335 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 ...
-3
votes
1answer
132 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 ...
4
votes
1answer
263 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
336 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 ...
-2
votes
1answer
236 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 ...
4
votes
1answer
261 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
204 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 ...
7
votes
4answers
776 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 ...
11
votes
4answers
939 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 ...
2
votes
1answer
305 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 ...
5
votes
3answers
272 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 ...
-3
votes
1answer
142 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 ...
6
votes
1answer
186 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
714 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
137 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 (...

1
2 3 4 5
14