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$
  • $\begingroup$ What exactly does "on top of each other" mean? $\endgroup$ – Paul Panzer Aug 10 at 23:19
  • $\begingroup$ It means "Two points cannot have exactly the same location." I've fixed this. $\endgroup$ – Dmitry Kamenetsky Aug 10 at 23:21
  • $\begingroup$ How could they as the sums of coords are all distinct? $\endgroup$ – Paul Panzer Aug 10 at 23:21
  • $\begingroup$ Good point. I will remove that condition. $\endgroup$ – Dmitry Kamenetsky Aug 10 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 at 3:04
11
$\begingroup$

1

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

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ A work of art ;-) $\endgroup$ – Paul Panzer Aug 11 at 5:05
  • 1
    $\begingroup$ Wow that's truly beautiful and deserves the tick! $\endgroup$ – Dmitry Kamenetsky Aug 11 at 6:45
  • $\begingroup$ NIce. How long did it take you to draw all of them by hand? :) $\endgroup$ – Marius Aug 11 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 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 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

| improve this answer | |
$\endgroup$
  • $\begingroup$ You got it. Well done! $\endgroup$ – Dmitry Kamenetsky Aug 11 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 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 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}

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you Rob. It is always great to get a confirmation from you. $\endgroup$ – Dmitry Kamenetsky Aug 11 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

| improve this answer | |
$\endgroup$
  • $\begingroup$ That one is certainly more interesting than my various "L"s'n'squares $\endgroup$ – Paul Panzer Aug 11 at 1:03
  • $\begingroup$ This was similar to the solution I had in mind, but not identical to it. $\endgroup$ – Dmitry Kamenetsky Aug 11 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.