Wikipedia:Reference desk/Archives/Mathematics/2018 August 26

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 26

Sandwich sequence

I don't know if this is the right name, but can't find anything else to describe what is meant - a sequence containing pairs of successive integers from 1 up to n, such that between the 1s there is one value, between the 2s two values, etc. For example, 3 1 2 1 3 2 for n=3. It's easy to show that n must be of the form 4m-1 or 4m by considering the odd/even parity of the 2n positions within the sequence, but I can't see a good way to either generate sequences, or to determine how many are possible, for arbitrary n. There may be something in OEIS, but I'm handicapped by not knowing what to look for.←2A00:23C6:590:300:842C:A689:E6B:F109 (talk) 12:00, 26 August 2018 (UTC)

You seem to want OEIS sequence A176127. There's also a brief article at Langford pairing, but after looking at the ref (the one listed at OEIS, not the one here), I'm unsure about the naming. –Deacon Vorbis (carbon • videos) 13:03, 26 August 2018 (UTC)

Thanks. Langford's problem is 60+ years old, but I'd not come across the name - knowing that it is the one I'm looking at would have made all the difference. It's odd how some problems are named after their discoverer and others more descriptively, e.g. TSP.←2A00:23C6:590:300:E503:6679:6394:CBD (talk) 16:15, 26 August 2018 (UTC)

And by the way, the only way I was able to find this was to write a short program to just count the number of solutions (I ran it up to n = 8), and then search OEIS, which gave me the name. –Deacon Vorbis (carbon • videos) 16:27, 26 August 2018 (UTC)

That's a good way to do it. Bubba73 ^{You talkin' to me?} 00:34, 27 August 2018 (UTC)

0-1 Equations

Is the following statement true?

Given the equation $Ax=b$ where $A$ is a 0-1 matrix, and $b$ is a 0-1 vector (that is, $A\in \{0,1\}^{m\times n},b\in \{0,1\}^{n}$), and we want to find its 0-1 solutions (i.e., solutions with $x\in \{0,1\}^{n}$; over $\mathbb {R}$, not over $\mathbb {Z} _{2}$). We shall refer to this matrix equation as a system of equations (every row in this matrix is an equation). Let P denote the polytope defined by the intersection of the set of solutions of this system of equations with the unit cube (i.e, with $[0,1]^{n}$). We do the following process: for every variable, $x_{i}$, if P is in the half space $\{x|x_{i}\leq {\frac {1}{2}}\}$, than we add the equation $x_{i}=0$ to our system of equations, and we update A, b and P (as we changed our equations). This process continues as long as there are more variables that satisfy this condition.

The new system of equations has the same 0-1 solutions as the original one. The 0-1 solutions are P's vertices. In particular, every vertex of P is also a 0-1 solution.

עברית (talk) 16:48, 26 August 2018 (UTC)

The problem you're describing is called zero-one programming, which is a variation on Integer programming. This is known to be NP-complete so it's unlikely there is an easy solution. I'm not sure I follow your explanation of your solution process completely, but it sounds like the start of branch and bound. This is quite a bit of literature on this subject so I'll refer you to the bibliography at the then of the Integer programming article. The short answer to your question is yes, but this type of reasoning rarely gets you to an actual solution; you might be able to eliminate some variables, but if you start with 100 and are able to eliminate 10 you're still a long way from the end. --RDBury (talk) 01:52, 27 August 2018 (UTC)

Umm I took a look at the article about branch and bound, but it looks too general. Could you point out a lack in the above process? Is something unclear in my explanation? עברית (talk) 18:20, 27 August 2018 (UTC)

First, the problem you describe isn't exactly a zero-one programming problem as I said. Notice that if any b_i is 0 then you have a constraint of the form x_j + x_k + ... x_p = 0, where each of x_j, x_k, ... x_p is either 0 or 1. This clearly implies that x_j, x_k, ... x_p are all 0 and can be eliminated. So b can be taken to be the column vector of all 1's. In this form the problem is actually known as the Exact cover problem, which is a bit more restricted than zero-one programming but is still known to be NP-Complete.

The lack in the process is that it will generally terminate quickly without getting you much closer to a solution. What happens with this linear programming approach to integer programs is you consider the constraints as hyperplanes in Rⁿ. First you determine if the intersection of the hyperplanes is empty, which can be done using the simplex algorithm (or whatever your favorite LP algorithm is). The next step is to find the maximum value of each variable withing the intersection, again straightforward with LP. If the maximum value of variable is <1 and the variable is constrained to be an integer, then that variable must 0 and can be eliminated, which is basically the process you describe above. In the majority of cases though, you discover that the variable has a maximum value of 1 on the polytope, but the vertex you found where it is 1 has factional values for the other variables. So you've neither found a solution nor eliminated a variable. So you might run through 100 variables and eliminate 9 to get a somewhat reduced problem. When you repeat the process for the remaining 91 variables you might eliminate 1 more, but eventually you're left with a polytope which is known to intersect all the faces of the n-cube but whether it contains a vertex of the cube is still unknown. An example of how this might happen in 3 dimensions is the intersection of the plane x+y+z=3/2 with the cube [0, 1]³. So basically you've given a condition under which a variable can be eliminated, but in practice this condition rarely occurs and after eliminating what variables you can you're left with a problem where the condition doesn't occur at all but you still don't have a solution. At that point LP alone doesn't get you much and you have to start using integer programming techniques, of which there are many. --RDBury (talk) 23:08, 27 August 2018 (UTC)

@RDBury: you claim that the modified P can still have a fractional vertex. Can you provide a specific counterexample? It doesn't seem possible to end up with the x+y+z=3/2 polytope for this particular type of LP. C0617470r (talk) 22:55, 28 August 2018 (UTC)

I doubt there's one with a small number of variables, but a nice one with 10 variables and 5 equations is;

X₁₂+X₁₃+X₁₄+X₁₅=1

X₁₂+X₂₃+X₂₄+X₂₅=1

X₁₃+X₂₃+X₃₄+X₃₅=1

X₁₄+X₂₄+X₃₄+X₄₅=1

X₁₅+X₂₅+X₃₅+X₄₅=1

This amounts to finding a perfect matching of K₅. This has no solutions with X_ij ∈ {0, 1} because 5 is not even, but the polytope defined by these equations and the inequalities x_ij ≥ 0 is nonempty. One vertex is (X₁₂, X₁₃, X₁₄, X₁₅, X₂₃, X₂₄, X₂₅, X₃₄, X₃₅, X₄₅) = (1, 0, 0, 0, 0, 0, 0, 1/2, 1/2, 1/2) in which X₁₂ is 1. By symmetry of K₅ there are vertices where the other 9 variables take the value 1, so the polytope touches all 10 faces of [0, 1]¹⁰ but doesn't hit any of its vertices. (There may be other vertices as well, I'd have to do some computation to be sure.) In this particular case there is a lot of symmetry and using parity it's easy to show there is no solution in integers, but more generally this is not the case. One way to think of it is that if such techniques worked in general then this NP-complete problem could be solved in polynomial time, which is not exactly a contradiction since P=NP is unsolved, but a larger number of highly intelligent people have been working on it for a long time and they have certainly tried this idea and many variations on it already. --RDBury (talk) 09:37, 29 August 2018 (UTC)

PS. In case anyone is interested, there are in fact 12 other vertices bringing the total to 22. One such vertex is (X₁₂, X₁₃, X₁₄, X₁₅, X₂₃, X₂₄, X₂₅, X₃₄, X₃₅, X₄₅) = (1/2, 0, 0, 1/2, 1/2, 0, 0, 1/2, 0, 1/2). --RDBury (talk) 11:29, 29 August 2018 (UTC)

@RDBury, it's a quite good counterexample! Thank you! עברית (talk) 13:51, 1 September 2018 (UTC)