# Tag Info

Accepted

### Splitting the integers from $1$ to $2n$ into two sets with products as close as possible

Original question Is this sequence strictly increasing? No. ...
• 6,431

### Splitting the integers from $1$ to $2n$ into two sets with products as close as possible

Here are optimal solutions for $n \le 10$, and the two sets happen to be equicardinal even if you don't enforce that: \begin{matrix} n & a_n & \text{solution} \\ \hline 1 & 1 & \{2\},\{...
• 5,149
Accepted

### Stable marriage with contracts: is it known?

There is a humongous literature on "matching with contracts", starting with: Hatfield, John William, and Paul R. Milgrom. "Matching with contracts." The American Economic Review 95.4 (2005): 913-...
• 12.4k
Accepted

### Spreading $n$ points in $\{0,1\}^n$ as far as possible

If I understood the question correctly, what you're asking is related to the maximum distance of binary codes with large minimum distance $d\geq s$. In coding theory, $A_q(n,d)$ is defined as the ...
• 10k

• 31.4k
Accepted

### Menger's theorem with restrictions on where the paths can begin and end

There is no known necessary and sufficient condition like in Menger's theorem. However, there is a polynomial-time algorithm that decides if the paths exist. This is one of the main results of the ...
• 31.4k
Accepted

### Desargues ten point configuration $D_{10}$ in LaTeX

This example shows that $s\le 2$ and for this $s$, $c\le 3$. Note that we are lucky with the latter, because there is a configuration for which every combinatorially equivalent realization has at ...
• 4,027

### Optimal Talmudic Zigzag

This is a special case of finding the longest path in a directed acyclic graph. Namely, the vertices of our graph are $1$, $2$, ..., $n$, there is an edge $i \to j$ for each $i<j$ and the length of ...
• 150k

### n sets, each is large, the intersection of every three is small, what is the size of the union?

It can be $O(n^{\frac32})$ for $a\ge 1$ if the sets $A_i$ correspond to the $p^2$ points of a smooth surface in an appropriate surface in a 3-dimensional space over $\mathbb F_p$ and your points are ...
• 18.2k
Accepted

### Smallest relation in complement of partial order that prohibits its extension

I claim that the relation $R$ is in fact unique. The uniqueness follows from the one pair extension property of finite partially ordered sets. Proposition: Suppose that $X$ is a finite set with ...
• 27.8k

### Splitting the integers from $1$ to $2n$ into two sets with products as close as possible

$\newcommand{\sub}[1]{_{\substack{m\in[1,2n] \\ #1}}}$ $\newcommand{\td}{{\widetilde d}}$ $\renewcommand{\cP}{{\mathcal P}}$ For the growth rate, we have the upper bound $a_n\le 2^nn!$ and, ...
• 22.8k
Accepted

• 9,411

### Snake algorithm that minimizes straight lines

This problem is a special case of the quadratic traveling salesman problem in which the cost for traversing three consecutive nodes that have no turn is $1$ and the cost is $0$ otherwise. Because ...
• 5,149
Accepted

### On a certain norm of the identity operator on $\mathbb R^2$

Simply observe that $$\|x\|_{a,b}=\|x_1a+x_2b\|_1\,.$$ Thus, by orthogonality of $a,b$ and the easily-derived inequality $\|y\|_2\le\|y\|_1\le\sqrt{n}\|y\|_2$ for any $y\in\mathbb{R}^n$, we have \...
• 1,423

### Metric TSP with integer edge cost

No polynomial-time algorithm exists, unless P=NP. Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and ...
• 31.4k
Accepted

### Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

You can solve this as a minimum-weight perfect matching problem in a graph with a node for each point and an edge for each pair of points. Because the distances satisfy the triangle inequality, an ...
• 5,149

Accepted

### n sets, each is large, the intersection of every three is small, what is the size of the union?

Let $m$ be chosen later, and let $A_1, A_2, \dots, A_n$ be independently chosen random subsets of $\{1,2,\dots m\}$, each having size $n$. For a fixed $a+1$-tuple $(x_1, x_2, \dots, x_{a+1})$ of ...
• 5,711