# 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. ...
• 4,627

### 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\},\{...
• 3,820
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-...
• 11.3k
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 ...
• 8,721

• 53k
Accepted

### Eigenvalues of adjacency matrix of a k-regular graph

If $G$ is regular, then $J$ and $A_G$ are simultaneously diagonalizable (i.e. they have a common set of eigenvectors). That is, the eigenvalues of $xA_G$ and $J$ (to the same eigenvectors) just add ...
• 10k
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 ...
• 23.3k
Accepted

• 103

### 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 ...
• 28.7k
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 ...
• 3,820
Accepted

### "Most Similar Vector Problem" on an Integer Lattice?

Writing up the comment: You just need to "pixelate" the line by finding all lattice boxes that it crosses: Then the answer vector $v$ must connect to one of the corners of the shaded boxes. Instead ...
• 4,822
Accepted

### How to roll a $p$

Here is an optimal method that I think is equivalent to your greedy method. We start with a constant random variable, say $0$. Inductively, after $n$ steps we have a random element uniformly ...
• 27.5k

• 72.3k
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,571
Accepted

• 89.5k