Questions tagged [discrete-optimization]
For questions about discrete optimization, which is a branch of optimization with discrete variables, opposed to continuous optimization in applied mathematics and computer science.
1,200
questions
65
votes
11
answers
12k
views
7 fishermen caught exactly 100 fish and no two had caught the same number of fish. Then there are three who have together captured at least 50 fish.
$7$ fishermen caught exactly $100$ fish and no two had caught the same number of fish. Prove that there are three fishermen who have captured together at least $50$ fish.
Try: Suppose $k$th fisher ...
- 90.2k
43
votes
5
answers
37k
views
Belt Balancer problem (Factorio)
So this question is inspired by the following thread: https://forums.factorio.com/viewtopic.php?f=5&t=25008
In it, the poster is examining an $8$-belt balancer (more on that to come) which he ...
- 4,020
25
votes
4
answers
1k
views
square cake with raisins
Alice bakes a square cake, with $n$ raisins (= points).
Bob cuts $p$ square pieces. They are axis-aligned, interior-disjoint, and each piece must contain at least $2$ raisins.
Note that a single ...
- 10.9k
23
votes
0
answers
404
views
Maximizing $\sum_{i,j=1}^{n}|\operatorname{deg}\ x_{i}-\operatorname{deg}\ x_{j}|^{3}$ over all simple graphs with $n$ vertices
For a simple graph $G$ on $n$ vertices, let us define
$$\mathcal{I}_{n}(G)=\sum_{i,j=1}^{n}|\operatorname{deg}\ x_{i}-\operatorname{deg}\ x_{j}|^{3}$$
I am highly interested in finding $\sup \...
user617199
19
votes
3
answers
1k
views
A question about the minesweeper game
This is just out of curiosity. Suppose the game has $m \times n$ boxes for positive integers $m$ and $n$. How can we make the sum of the numbers on a finished game the most?
There are two extreme ...
- 367
19
votes
1
answer
499
views
Choose signs such that $\pm\sqrt{1}\pm\sqrt{2}\pm\dots\pm\sqrt{2022}$ is as close as possible to $0$.
Choose signs such that $\pm\sqrt{1}\pm\sqrt{2}\pm\dots\pm\sqrt{2022}$ is as close as possible to $0$.
I tried looking at examples for small $n$ (up to $8$) for inspiration:
$$\begin{align}
&1: -\...
- 1,111
18
votes
2
answers
572
views
Largest rectangle not touching any rock in a square field
You want to build a rectangular house with a maximal area. You are offered a square field of area 1, on which you plan to build the house. The problem is, there are $n$ rocks scattered in unknown ...
- 10.9k
16
votes
4
answers
864
views
We have $n$ charged and $n$ uncharged batteries and a radio which needs two charged batteries to work.
We have $n$ charged and $n$ uncharged batteries and a radio which needs two charged batteries to work. Suppose we don't know which batteries are charged and which ones are uncharged. Find the least ...
- 90.2k
16
votes
2
answers
1k
views
Domination problem with sets
Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
of $M$, satisfying:
$|S_i|\leq 3,i=1,2,...,k$
Any element of $M$ is an element of at least $4$ sets among
$S_1,....,S_k$.
Show that one ...
- 90.2k
15
votes
3
answers
11k
views
Greatest number of parts in which n planes can divide the space
Find the greatest number of parts including unbounded in which n planes can divide the space.
I am trying like this, since it is very hard to visualize( or draw in paper).
Equation of plane in 3 ...
- 860
15
votes
3
answers
2k
views
Maximizing the value of a determinant
Given the entries of a matrix how can we optimize its determinant?
So, if the entries of a $n\times n$ matrix belong to the set $\{a_1,a_2,\ldots ,a_p\}$, how to arrange them to maximize or minimize ...
- 704
14
votes
3
answers
2k
views
Maximising determinant problem
The problem is to maximize the determinant of a $3 \times 3$ matrix with elements from $1$ to $9$.
Is there a method to do this without resorting to brute force?
- 6,930
14
votes
1
answer
339
views
$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.
$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.
There was no information about $n$ in a original problem.
Attempt: Choose at random and ...
- 90.2k
14
votes
0
answers
282
views
Maximum number of permutations not repeating smaller permutations
There are $n$ soldiers, lining up every morning for their military service. The commander demands that the morning lineup of these soldiers be arranged differently for every next day according to the ...
- 12.6k
13
votes
2
answers
702
views
Find the minimum number of edges in a graph with $3n+1$ vertices if ...
Let $G$ be a simple graph with $3n+1$ vertices. For any vertex $v$, there exists $n$ disjoint $K_3$ (i.e. triangle) such that none of them contains $v$. Find minimum number of edges of graph $G$.
If ...
- 90.2k
13
votes
1
answer
333
views
What is the name of this class of (combinatorial?) problems?
Judging from the number of similar questions, I've found myself in a rather common situation: I've come up with a problem, encountered a dead end and am now searching for the name of the problem in ...
- 796
12
votes
3
answers
1k
views
Combinatoric Problem in Stardew Valley about Keg Layout
I will first give the mathmatical description of the problem, which I think is a good problem for high school MOers.
Given positive integers $m, n \geq 3$, where $m$ is an odd number, consider a ...
- 507
12
votes
1
answer
2k
views
Maximize the trace of a matrix by permuting its rows
I have been struggling with a combinatorial problem that eventually translates to the following:
Given an $n \times n$ nonnegative matrix, find a permutation of the rows that maximizes the trace.
...
- 976
11
votes
2
answers
809
views
Maximise $\left( \sum_{i=1}^{n} p_i \cdot i \right) - \left( \max_{j=1}^{n} p_j \cdot j \right)$ with $p$ permutation of size $n$
I'm trying to maximise the following value:
$\left( \sum_{i=1}^{n} p_i \cdot i \right) - \left( \max_{j=1}^{n} p_j \cdot j \right)$
where $p$ is an array consisting of $n$ distinct integers from $1$ ...
11
votes
5
answers
529
views
Elevator stops in building
Bill is working in the 38th floor of an 100-floors building. This building has a strange elevator which only has 2 buttons: the green one which takes you to the next floor every time you press it (and ...
- 1,603
11
votes
2
answers
407
views
Smallest diameter of a balanced subset of the Hamming cube
Let $\{0,1\}^n$ be the Hamming cube with the Hamming metric. It's a metric space of diameter $n$.
Let's call a set $B\subset \{0,1\}^n$ balanced if its center of mass is the center of the cube; that ...
user357151
10
votes
1
answer
216
views
The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$.
Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each ...
- 90.2k
10
votes
2
answers
231
views
Find a permutation $x_{\sigma(1)},\ldots,x_{\sigma(n)}$ of $x_1,\ldots,x_n$ that maximises $\sum_{k=1}^{n-1}\vert x_{\sigma(k)}-x_{\sigma(k+1)}\vert.$
Suppose $\ x_1,\ x_2,\ \ldots,\ x_n\ $ are real numbers with $\ x_1 < x_2 <\ldots < x_n.$
Is there an efficient way to find a permutation $\ x_{\sigma(1)},\ x_{\sigma(2)},\ \ldots,\ x_{\sigma(...
- 21.3k
10
votes
0
answers
3k
views
Why no Forward Dynamic Programming in stochastic case?
Dynamic programming usually works "backward" - start from the end, and arrive at the start. This works both when there is and when there isn't uncertainty in the problem (e.g. some noise in the state)....
- 1,195
9
votes
4
answers
1k
views
$100$ birds in $21$ cages each with $≤ 10$, with least cages having $≥ 4$ birds?
A bird cage could only fit a maximum of $10$ birds. If a house has $21$ bird cage and $100$ birds. A bird cage is considered overpopulated if it fits $4$ or more birds inside it. How many cages (...
- 333
9
votes
3
answers
1k
views
Find smallest set of natural numbers whose pairwise sums include 0..n
Given a positive integer $n$, how do you find the smallest set of nonnegative integers $S$ such that for each integer $m$, where $0\leq m<n$, there exist two (not necessarily distinct) members of ...
- 695
9
votes
2
answers
318
views
I'm walking towards my car - when should I try the remote, in an optimal sense?
I'm interested to learn about how discrete/'event' based elements are incorporated into optimisation problems. Hopefully this is an interesting problem in its own regard, it's inspired by a daily ...
- 230
9
votes
1
answer
746
views
The locker puzzle - predetermined strategy
The question is related to the famous locker puzzle:
The director of a prison offers 100 prisoners on death row, which are numbered from 1 to 100, a last chance. In a room there is a cupboard with ...
- 25.8k
9
votes
1
answer
102
views
Best way to divide multiple equal groups into known unequal groups. 🎄Christmas Lights🎄
I'm not a math guru, but I do like Christmas lights.
I am helping set up a decent sized lighting display for my work, I have measured all outlines and props to figure out how many lights we are ...
- 93
8
votes
2
answers
140
views
Question about swindler-writer
This question arose from my curiosity.
In one particular publishing house writer's salary depends on the amount of text he produces $-$ $p=20$ dollars for $s=1800$ symbols.
How much money can earn a ...
- 57.3k
8
votes
1
answer
1k
views
Nearest signed permutation matrix to a given matrix $A$
Given $A \in \mathbb{R}^{n \times n}$, let $Q \in O(n)$ be the orthogonal matrix nearest to $A$ in the Frobenius norm, i.e.,
$$Q := \text{arg}\min_{M \in O(n)} \| A - M \|_{F}^2$$
It's well known that ...
- 1,607
8
votes
1
answer
2k
views
Find a permutation of the rows of a matrix that minimizes the sum of squared errors
I'm struggling with the following problem:
Let $A, B \in \mathbb R^{n \times d}$. Denote by $\mathcal{P}$ the set of all possible permutations of the rows of $A$. Find a permutation $\pi \in \...
- 101
8
votes
4
answers
400
views
Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$
Question:
Determine the largest natural number $r$ with the property that among any five subsets with $500$ elements of the set $\{1,2,\ldots,1000\}$ there exist two of them which share at least $r$ ...
- 93.7k
8
votes
3
answers
277
views
Dropping the "Lowest Grade" Problem
Let $A=\{a_1, a_2, ... , a_n\}$ be a set of non-negative real numbers and $B=\{b_1, b_2, ..., b_n\}$ be sets of positive real numbers.
Let $s = \dfrac{ \sum_A a}{\sum_B b} = \dfrac{a_1+a_2+\dots+a_n}...
- 5,029
8
votes
1
answer
3k
views
Minimum number of horizontal and vertical lines, covering $n$ points in the plane
Let there be n points in the plane. I want to know the minimum number of horizontal and vertical lines covering all the points in the plane.
My initial approach started like this,
1) for each point I ...
- 221
7
votes
2
answers
869
views
How can I, as a future mathematician, contribute most to Smart Grid research?
After I've finished my Master's degree in mathematics, I too want to use my powers for good.
One endeavour I consider good is the pursuit of the design and implementation of a Smart Grid which will, ...
- 7,316
7
votes
1
answer
208
views
Different bricks making a cube
We want to build an $n \times n \times n$ cube using bricks that have integer sides and are all different. As a function of $n$, what is the maximum number of bricks we can use? For $n=1$ or $2$ it ...
- 379k
7
votes
2
answers
246
views
Max packing of cars in square parking lot
An $n\times n$ square grid represents a parking lot, each of the $n^2$ squares may be occupied by at most one car. However, each car (not on the boundary) must have a clear path to the boundary of the ...
- 18.5k
7
votes
4
answers
431
views
Optimal rounding a sequence of reals to integers
I'm given positive real numbers $c_1,\dots,c_m \in \mathbb{R}$ and an integer $d \in \mathbb{N}$. My goal is to find non-negative integers $x_1,\dots,x_m \in \mathbb{N}$ that minimize $\sum_i (x_i - ...
- 5,525
7
votes
1
answer
1k
views
A variant of assignment problem (different sizes of sets)
I'm given objects divided into two disjoint sets, $A$ and $B$. There's a cost function defined, so that I know a positive cost (or distance) of any assignment $(a,b)\;|\;a \in A,\; b \in B$. It always ...
- 73
7
votes
3
answers
436
views
if $ \{ a_1 , a_2 , \cdots, a_{10} \} = \{ 1, 2, \cdots , 10 \} $ . Find the maximum value of $I= \sum_{n=1}^{10}(na_n ^2 - n^2 a_n ) $
Let $ \{ a_1 , a_2 , \cdots, a_{10} \} = \{ 1, 2, \cdots , 10 \} $ . Find the maximum value of
$$I= \sum_{n=1}^{10}(na_n ^2 - n^2 a_n ) $$
I try: since $(a-b)^3=a^3-3a^2b+3ab^2-b^3$,and $\sum_{n=1}^{...
- 93.7k
7
votes
2
answers
471
views
Best approximation of sum of unit vectors by a smaller subset
Let $v_1,\ldots,v_N$ be linear independent unit vectors in $\mathbb{R}^N$ and denote their scaled sum by $s_N = \frac{1}{N}\sum_{k=1}^N v_k.$ I would like to find a small subset of size $n$ among ...
- 2,747
7
votes
1
answer
995
views
Is this set of random variables a Hilbert space?
Consider a sequence of i.i.d. random variables $\left\{ {{\varepsilon _t}} \right\}_{t = 1}^\infty $ with $E\left( {{\varepsilon _t}} \right) = 0$
and $E\left( {\varepsilon _t^2} \right) = {\sigma ^2}...
- 117
7
votes
1
answer
270
views
find the least natural number n such that if the set $\{1,2,...,n\}$ is arbitrarily divided into two nonintersecting subsets
Find the least natural number $n$ such that if the set $\{1,2,\dots,n\}$ is arbitrarily divided into two non intersecting subsets then one of the subsets contains three distinct numbers such that the ...
- 121
7
votes
1
answer
136
views
A hat allocation problem
This is an abstraction of a problem that has come up in my research.
Imagine we have $N$ wizards and $N$ hats. The hats have $C$ different colours. There are $n_1>0$ hats with the first colour, $...
- 1,295
7
votes
2
answers
149
views
In a party attended by $2015$ guests among any $5$ guests at most $6$ handshakes had been exchanged. Determine the maximal number of handshakes.
In a party attended by $2015$ guests among any $5$ guests at most $6$ handshakes had been exchanged. Determine the maximal possible number of handshakes.
Turkey EGMO TST 2015 P6
Some findings:
Say ...
- 90.2k
7
votes
1
answer
171
views
Maximal Number of Points in Co-Pareto-Front
Let $n \in \mathbb{N}$ be some big number and $d \in \mathbb{N}_{\geq 1}$ be a number of dimensions. Let furthermore $f : (\{0, \ldots, n\})^d \rightarrow \mathbb{B}$ be some monotone oracle function, ...
- 71
7
votes
1
answer
266
views
Find a generalized path cover of a square graph
Given a directed $n\times n$ square graph as shown in the figure with $n^2$ nodes. Find a set of directed paths $\mathcal P$ from $s$ to $t$ with the minimum cardinality (i.e, minimum number of paths ...
- 101
7
votes
2
answers
773
views
Smallest non-zero eigenvalue of a (0,1) matrix
What's the smallest absolute value possible of a non-zero eigenvalue of an $n$ by $n$ square matrix whose entries are either $0$ or $1$ (all operations are over $\mathbb{R}$)?
user35671
7
votes
2
answers
2k
views
Integer linear programming constraint for maximum number of consecutive ones in a binary sequence
Consider an integer programming problem with binary decision variables $x_1,\ldots,x_n \in \{0,1\}$. Im trying to model the constraint that enforces the maximum number of consecutive ones in ...
- 1,113