2
$\begingroup$

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!

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

1

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

$\endgroup$
5
  • 2
    $\begingroup$ A work of art ;-) $\endgroup$ – Paul Panzer Aug 11 '20 at 5:05
  • 1
    $\begingroup$ Wow that's truly beautiful and deserves the tick! $\endgroup$ – Dmitry Kamenetsky Aug 11 '20 at 6:45
  • $\begingroup$ NIce. How long did it take you to draw all of them by hand? :) $\endgroup$ – Marius Aug 11 '20 at 10:59
  • 1
    $\begingroup$ @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. $\endgroup$ – Alexey Burdin Aug 11 '20 at 14:53
  • $\begingroup$ 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? $\endgroup$ – Ross Presser Aug 11 '20 at 16:13
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ You got it. Well done! $\endgroup$ – Dmitry Kamenetsky Aug 11 '20 at 0:45
  • $\begingroup$ @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... $\endgroup$ – Paul Panzer Aug 11 '20 at 0:51
  • $\begingroup$ 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. $\endgroup$ – Dmitry Kamenetsky Aug 11 '20 at 2:08
4
$\begingroup$

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}

$\endgroup$
1
  • $\begingroup$ Thank you Rob. It is always great to get a confirmation from you. $\endgroup$ – Dmitry Kamenetsky Aug 11 '20 at 3:44
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.