The Naked Scientists

The Naked Scientists Forum

Author Topic: Dividing dots with lines  (Read 4857 times)

Offline DoctorBeaver

  • Naked Science Forum GOD!
  • *******
  • Posts: 12656
  • Thanked: 3 times
  • A stitch in time would have confused Einstein.
    • View Profile
Dividing dots with lines
« on: 26/11/2008 10:47:10 »
I think we've all seen those problems where there are a number of dots on a page and you have to separate them using the least number of straight lines. Is there a way of proving mathematically what the least number would be?

(If a mod can think of how to phrase the topic title as a question, please feel free to change it)


 

Offline Chemistry4me

  • Neilep Level Member
  • ******
  • Posts: 7709
    • View Profile
Dividing dots with lines
« Reply #1 on: 26/11/2008 10:57:00 »
What do you mean by separating them? ??? Do you mean the least number of straight lines which crosses all of the dots. Anyway, I never have any luck with those :-\, it usually takes a while... I definetly don't have any gigantic mathematical formula, but what I have discovered is that the lines seem to always extend beyond the dots, if anyone knows what I mean..... [:I]
 

Offline LeeE

  • Neilep Level Member
  • ******
  • Posts: 3382
    • View Profile
    • Spatial
Dividing dots with lines
« Reply #2 on: 26/11/2008 11:03:10 »
Dunno off hand, but whether you use geometrical points, or dots with a non-zero area will have a bearing on the answer.  If you just consider three dots that are widely separated you can easily separate them with straight lines but if the dots were enlarged so that they are all nearly, but not quite, touching each other you wouldn't be able to draw a straight line between any of them.  Any solution for non-zero sized dots would need to take the dot size in to consideration, whereas a solution for points obviously wouldn't as the lines can be arbitrarily close to the points.
 

Offline Chemistry4me

  • Neilep Level Member
  • ******
  • Posts: 7709
    • View Profile
Dividing dots with lines
« Reply #3 on: 26/11/2008 11:14:18 »
OH, I see what you mean.
 

Offline DoctorBeaver

  • Naked Science Forum GOD!
  • *******
  • Posts: 12656
  • Thanked: 3 times
  • A stitch in time would have confused Einstein.
    • View Profile
Dividing dots with lines
« Reply #4 on: 26/11/2008 11:33:36 »
Stop complicating the matter! I'm talking about the problems you get in puzzle books where there are a number of dots and you have to separate them using the least number of lines. You get them on those Brain Training things on the PSP too.
 

Offline neilep

  • Withdrawnmist
  • Naked Science Forum GOD!
  • *******
  • Posts: 20602
  • Thanked: 8 times
    • View Profile
Dividing dots with lines
« Reply #5 on: 26/11/2008 12:22:59 »


(If a mod can think of how to phrase the topic title as a question, please feel free to change it)

This might be silly..but I find the use of a question mark can help occasionally..ie: " Dividing dots with lines ? "
 

Offline DoctorBeaver

  • Naked Science Forum GOD!
  • *******
  • Posts: 12656
  • Thanked: 3 times
  • A stitch in time would have confused Einstein.
    • View Profile
Dividing dots with lines
« Reply #6 on: 26/11/2008 16:00:21 »


(If a mod can think of how to phrase the topic title as a question, please feel free to change it)

This might be silly..but I find the use of a question mark can help occasionally..ie: " Dividing dots with lines ? "

Yes, that's silly.
 

lyner

  • Guest
Dividing dots with lines
« Reply #7 on: 26/11/2008 16:48:34 »
Dr B
I'm afraid that you have to make it complicated if you want to get a machine to solve the problem. The thickness of the lines and the diameter of the spots is not irrelevant. You have to make assumptions about that - estimating sizes from the printed puzzle - and that will allow you to quantise the problem.
You can't deal with 'infinitely thin lines and dots if you want to solve the problem numerically and I don't think there can be an analytical solution.
 

Offline DoctorBeaver

  • Naked Science Forum GOD!
  • *******
  • Posts: 12656
  • Thanked: 3 times
  • A stitch in time would have confused Einstein.
    • View Profile
Dividing dots with lines
« Reply #8 on: 26/11/2008 17:20:04 »
Oh Gawd! Assume you've made the dots with a sharpened, standard size pencil and are using the same pencil to draw the lines.

All I want to know is if there is any way to prove that the solution given in the book is in fact correct and that it cannot be done with fewer lines.
 

lyner

  • Guest
Dividing dots with lines
« Reply #9 on: 26/11/2008 19:41:15 »
I think it would involve solving equations of lines and introducing  limits. Not totally trivial. Maths too hard for me but I bet it's been done already.
Try some hard Googling DrB.
 

Offline RD

  • Neilep Level Member
  • ******
  • Posts: 8132
  • Thanked: 53 times
    • View Profile
Dividing dots with lines
« Reply #10 on: 26/11/2008 19:56:25 »
Initially I though of the four colour map theorem, but that does not require straight lines.

The 9 nine dot "thinking-outside-the-box" puzzle next came to mind,
 but that involves connecting dots with straight lines, not separating them.
 

lyner

  • Guest
Dividing dots with lines
« Reply #11 on: 26/11/2008 20:30:14 »
I think the nine dot problem is easier. You could do it with simultaneous equations, I think. That is unless you want to use your innate intelligence.
 

The Naked Scientists Forum

Dividing dots with lines
« Reply #11 on: 26/11/2008 20:30:14 »

 

SMF 2.0.10 | SMF © 2015, Simple Machines
SMFAds for Free Forums