# Tag Info

## Hot answers tagged discrete-optimization

104

Let's work with the lowest four numbers instead of the other suggestions. Supposing there is a counterexample, then the lowest four must add to at least $51$ (else the highest three add to $50$ or more). Since $14+13+12+11=50$ the lowest four numbers would have to include one number at least equal to $15$ to get a total as big as $51$. Then the greatest ...

26

If the maximum number of fish caught is $m$, then the total number of fish caught is no more than $m+(m-1)+...+(m-6)$. So there is one fisherman that caught at least 18 fish. Repeat this process for the second and third highest number of fish caught and you should be good. I should add that this is a common proof technique in combinatorics and graph theory. ...

13

UTU = Universally throughput unlimited There exist UTU balancers for 3, 4, and 5 belts, and likely for any number of belts. Examples are given in this Jupyter notebook, along with a Python implementation of an iterative algorithm for computing the flow for any set of belts and splitters. I will quote some of the notebook here for those who don't wish to ...

10

Say we have $n$ cages each with $3$ birds, then we must fill the other $21-n$ cages with $100-3n$ birds. So $$100-3n\leq (21-n)\cdot 10\implies n\leq 15$$ $n= 15$ is achiavable: $15\cdot 3+5\cdot 10+1\cdot 5 =100$. So you must have at least $6$ overpopulated cages.

8

I think I have a solution. First note that if $r_4 \geq 15$ then we have: $r_5 \geq 16$ $r_6 \geq 17$ $r_8 \geq 18$ so $r_5 + r_6 + r_7 \geq 16 + 17 +18 = 51$ which is impossible. Therefore $r_4 < 15$ Also note that if $r_4 \leq 14$ then: $r_3 \leq 13$ $r_2 \leq 12$ $r_1 \leq 11$ thus $r_1 + r_2 + r_3 + r_4 \leq 50$ which implies that $r_5 + ... 8 Start putting$3$birds in each cage... so in total$3 \cdot 21= 63$. Then you have$100-63=37$birds to put and every cage now can contain only$7$birds, so you need at least$6$cages (since$5 \cdot 7 < 37 < 6 \cdot 7$) 8 This problem contains http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html which is hard. This is an interesting 1-parameter extension (see below). The number of matrices with entries drawn from$\{a_1, \ldots, a_p\}$is finite, so the maximum is attained. Suppose$A$is a matrix attaining it. I claim that every entry in$A$is either$m=\...

7

This is a integer linear programming problem. Let $c_{ab}$ be the cost for the assignment$(a,b)$ and let $x_{ab}$ be 0 or 1 depending on whether this assignment is made or not. The goal is to minimize $$\sum_{a,b} c_{ab} x_{ab}$$ subject to the constraints $x_{ab} \in \{0,1\}$ and $\sum_a x_{ab} = 1$ for all $b$, $\sum_b x_{ab} \le 1$ for all $a$. A ...

7

I'm a graduate student in power systems, so while I'm not in industry, I figure I could give you my perspective on Smart Grid research as a student who's asking similar "applications" questions to those in my field. I would first say that, from my perspective, mathematics is quite useful for the S.G.; for such a large-scale system modernization/...

7

${\textbf{ I keep this answer because there are some detailed proofs}}$ ${\textbf{(that are not needed in the streamlined approach in my other answer)}}$. ${\textbf{This is also a register of the history of the answer which was found in several steps.}}$ This is only a partial answer. We have three results, and in the first two the lower bound given by (1) ...

7

Each of the $4N$ exterior edges is a side of exactly one face and every other of at most two. So the sum of the sizes of faces is equal to at most $2N^2+4N$. Now, each face has to be at least quadrilateral except corner faces which can be triangles but there are at most $4$ of them taking at most $12$ from $2N^2+4N$. So altogether there can be at most: $$\... 6 There are perhaps many ways to approach these "smart grid" problems, and one way is to approach it from a "networking theory" point of view. But, and this is a big but, hot topics like these smart grids, well, they come and go. The way they are advertised is cool, "it is going to solve all of our problems, yay," but it does not work this way. So, unless you ... 6 The problem is known as the Maximum Coverage Problem. It is NP-hard. Thus we cannot solve it in polynomial time (≈efficiently) unless P=NP. A greedy algorithm gives a 1-1/e approximation and there is a matching hardness of approximation result [Hochbaum '97, Feige '98]. The problem is closely related to the Set Cover Problem: we are given a set of ... 6 It turns out that for 40 button presses the maximum number of characters is 300 (worth about 3.33), which can be achieved a number of different ways. The recursion is$$f(n)= \max \{\,f(n-1)+1, \max_j \{j \times f(n-4-2j)\}\,\}$$starting with f(0)=0 since you can type an extra character or do Ctrl-A, Ctrl-C and then Ctrl-V j times. For n=40, ... 6 The expression can be viewed as the probaility of having exactly a heads in a+b fair coin tosses, so intuitively, this should be maximized if a=b. Moreover, the more coin tosses we make, the less likely it will become to obtain exactly (rounded) half of them heads. Formally, with f(a,b)={a+b\choose a}2^{-a-b} we have$$ \frac{f(a+1,b-1)}{f(a,b)}=\...

6

Your question is equivalent to the following: What is the greatest number of parts a cake (cylinder/cube/any other convex shape) can be divided into with n straight cuts? Appropriately these are called the cake numbers $C(n)$, and are indexed as A000125 in Sloane's OEIS. The proof of this starts from two dimensions with the lazy caterer's sequence (...

6

Here are results for $n$ up to $80$, where $\min$ is the lower bound you derive from the binomial coefficient, $\max$ is the upper bound that Fabio Lucchini derived in his answer, and $L=|S|$ is the size of a minimal generating set. Actual subsets $S$ are only shown for the last entry for any given $L$, since this subset also works for all smaller $n$. \...

6

I commend to you the Hungarian method. It's an algorithm that I'm not up to writing out here, but it's available in many combinatorics, discrete math, and graph theory textbooks, also many places on the web: Wikipedia in particular will get you started.

6

Note that $$Y:=\sum_{i=1}^{n-1}\,\left|X_i-X_{i+1}\right|=\sum_{i=1}^{n-1}\,X_{S(i)}-\sum_{i=1}^{n-1}\,X_{T(i)}\,,$$ where $\big\{S(i),T(i)\big\}=\{i,i+1\}$ and $X_{S(i)}>X_{T(i)}$ for each $i=1,2,\ldots,n-1$. Observe that each integer in $\{1,2,\ldots,n\}$ must appear at least once but at most twice amongst $$X_{S(1)},X_{S(2)},\ldots,X_{S(n-1)},X_{T(1)},... 6 The question admits two interpretations from well-studied topics, see the references. The first is combinatorial, concerning A(n, d, w), which is the maximal possible number of binary vectors of length n, (Hamming) distance at least d apart, and constant weight (that is, the number of 1’s) w. It is also related with A(n, d), the maximal ... 6 If n=1 then this can be done in zero attempts because we know the radio won't work. If n=2 I don't see a way of going below 5 (or 6) attempts. If n\ge 3 then the number of attempts can be reduced to n+2\space (or n+3) First two sets of three are tested$$\{B_1,B_2\}, \{B_2,B_3\}, \{B_3,B_1\} \{B_4,B_5\},\{B_5,B_6\}, \{B_6,B_4\}Then ... 6 Hint: Consider the ratio of successive terms \dfrac{f(n)}{f(n-1)}, for n\ge 1. (This ratio here equals \dfrac{(n+1)^2}{2n^2}.) Try and find for which values of n we have \color{blue}{\dfrac{f(n)}{f(n-1)} \ge 1}. Can you see how to use this information to find which n maximises f(n)? 6 Conjectures: In d dimensional space, the points with coordinates taken from the set are contained in a hypercube between the limits a_{\min} and a_{\max}. The determinant is proportional to the volume of the hyperpyramid formed by the origin and d points from the network. If I am right (but this needs to be confirmed), the largest volume is ... 5 Let E = \{e, f, g, h\} and consider the following two collections of subsets of E \begin{align*} \mathcal{I} &= \{\varnothing, \{e\},\{f\},\{g\},\{h\}, \{e,f\}, \{e,g\}, \{f,h\}, \{g,h\}\} ,\mbox{ and}\\ \mathcal{K} &= \{\varnothing, \{e\},\{f\},\{g\},\{h\}, \{e,f\}, \{e,h\}, \{f,g\}, \{g,h\}\}. \end{align*} Then, M_1=(E,\mathcal{I}) and M_2=(... 5 Concepts like vertex transitivity and the automorphism group of a graph seem to address a slightly different problem. Suppose that Alice, from where she's standing, sees the entire structure of G, but can't tell the vertices apart in absolute terms: she can only describe them relative to her current position. (I guess we'd still want Alice to need to be ... 5 I assume that you have to actually place two working batteries in, not just find them. Any algorithm to solve this problem is of the following form: Test some pair E_1=\{v_1,w_1\} of batteries. If that does not work, test a different pair E_2=\{v_2,w_2\}. \vdots Finally, test E_k=\{v_k,w_k\}. Furthermore, the order of the pairs E_i does not ... 5 Hint: Prove that\frac{(n+1)^2}{2^n}\le \frac{9}{4}$$The equal sign holds if$$n=2$$This is equivalent to$$(n+1)^2\le 9\cdot 2^{n-2}. You can prove this by induction.

5

No. Why would developers work on all these MIP solvers if there is an easy LP formulation? We can write $x (1-x)=0$. But that does not really help. This is non-linear (quadratic) and non-convex, and you would need a global NLP solver (which often use Branch-and-bound). Of course, using some Lagrange multiplier technique as suggested elsewhere, is ...

4

Given the restrictions, one can make the following observations: The only reason to select the text is to copy it, therefore one can assume that each Ctrl-A is immediately followed by a Ctrl-C. Moreover, Ctrl-C without preceding Ctrl-A is pointless. After Ctrl-C, the only sensible thing to do is Ctrl-V, because all other keys in that situation either change ...

4

König's theorem says that two (normally different) problems--min vertex cover and max matching--become the same on bipartite graphs. The wikipedia page for König's theorem gives an example of the conversion. The other two problems are equivalent to these two. Min vertex cover is trivially the same as max independent set (a set of vertices forms a min cover ...

Only top voted, non community-wiki answers of a minimum length are eligible