Reconstructing points based on the sum of their coordinates version 2

10 points are drawn on a piece of paper with the following rules:

• Each point has integer coordinates (𝑥,𝑦) that are between 1 and 10 inclusive.
• For each point there is exactly one other point with the same x-coordinate and exactly one other point with the same y-coordinate.

The sum of the coordinates of each point (ie., x+y) is provided: 2, 4, 5, 6, 7, 8, 10, 11, 12, 13. Can you reconstruct the location of each point? Bonus question: can you find multiple solutions? Good luck!

• What exactly does "on top of each other" mean? Aug 10 '20 at 23:19
• It means "Two points cannot have exactly the same location." I've fixed this. Aug 10 '20 at 23:21
• How could they as the sums of coords are all distinct? Aug 10 '20 at 23:21
• Good point. I will remove that condition. Aug 10 '20 at 23:22
• There are exactly $470$ solutions out of $16329600$ possible, python script here and I'm working on the visual representation. Aug 11 '20 at 3:04

$${}{}{}{}{}{}{}{}{}{}{}{}{}{}$$

• A work of art ;-) Aug 11 '20 at 5:05
• Wow that's truly beautiful and deserves the tick! Aug 11 '20 at 6:45
• NIce. How long did it take you to draw all of them by hand? :) Aug 11 '20 at 10:59
• @Marius python source code here, took a couple of hours. The most indirect part was selecting the colors. Btw, can anyone suggest better colors? Maybe from XOY color space, not from RGB. Aug 11 '20 at 14:53
• TBH, the color doesn't add very much to the diagram, at least for this (red/green color-blind) viewer. The components are just too small. Maybe if you shaded entire strips instead of just lines? Aug 11 '20 at 16:13

Doesn't look anywhere near unique to me:

For example,

you can make an "L" shape from the first 6 points $$(1,1),(2,2),(1,4),(2,4),(6,1),(6,2)$$ and a rectangle from the remaining 4 $$(7,3),(8,3),(7,5),(8,5)$$ or $$(4,6),(5,6),(4,8),(5,8)$$ or $$(3,7),(5,7),(3,8),(5,8)$$ or $$(3,7),(4,7),(3,9),(4,9)$$

or

a "fat L" $$(1,1),(3,1),(1,4),(3,3),(4,3),(4,4)$$ and a rectangle $$(5,5),(5,6),(7,5),(7,6)$$ or $$(5,5),(6,5),(5,7),(6,7)$$

or

another disfigured L $$(1,1),(3,1),(1,6),(2,6),(2,3),(3,3)$$ and a rectangle $$(5,5),(6,5),(5,7),(6,7)$$ or $$(6,4),(6,5),(8,4),(8,5)$$ or $$(8,2),(8,4),(9,2),(9,4)$$ or etc.

or for a slightly different class of solution

with the $$(1,1)$$ piece participating in a rectangle instead of an L: $$(1,1),(1,4),(9,1),(9,4)$$ and $$(2,2),(2,5),(4,2),(3,5),(4,8),(3,8)$$

and probably more

• You got it. Well done! Aug 11 '20 at 0:45
• @DmitryKamenetsky Out of interest: do we know these are essentially all? Or do we not know and not care? Or do we know they aren't all and still don't care? Because so far I didn't do anything systematic, just throwing stuff against the wall and see what sticks... Aug 11 '20 at 0:51
• The solution I had was a single component (similar to tehtmi answer, but not the same). I was not aware of other solutions, but assumed that they are possible, like you have demonstrated. Aug 11 '20 at 2:08

I confirm @AlexeyBurdin's count of 470 solutions, which I obtained via integer linear programming as follows. Let $$S=\{2, 4, 5, 6, 7, 8, 10, 11, 12, 13\}$$ be the set of desired sums. Let binary decision variable $$p_{x,y}$$ indicate whether there is a point with coordinates $$(x,y)$$, let binary decision variable $$r_x$$ indicate whether row $$x$$ contains any points, and let binary decision decision variable $$c_y$$ indicate whether column $$y$$ contains any points. The constraints are:

\begin{align} \sum_{x,y} p_{x,y} &= 10 \\ \sum_{y} p_{x,y} &= 2 r_x &&\text{for all x}\\ \sum_{x} p_{x,y} &= 2 c_y &&\text{for all y}\\ \sum_{\substack{x,y:\\ x + y = s}} p_{x,y} &= 1 &&\text{for all s\in S} \\ \end{align}

• Thank you Rob. It is always great to get a confirmation from you. Aug 11 '20 at 3:44

Here is a solution with "one component":

(1,1) 2
(1,9) 10
(2,9) 11
(2,4) 6
(4,4) 8
(4,8) 12
(5,8) 13
(5,2) 7
(3,2) 5
(3,1) 4

• That one is certainly more interesting than my various "L"s'n'squares Aug 11 '20 at 1:03
• This was similar to the solution I had in mind, but not identical to it. Aug 11 '20 at 2:09