Circle

[cinelli]

An array of two million points is completely enclosed by a circle having a diameter of one inch. Does there exist a straight line having exactly one million points on each side of the line? If so, why, and how?

Merry puzzling.

Cinelli

[Gengulphus]

Just to say that I knew the answer to this one as soon as I read it - I've encountered similar types of problem many times before - and so I'll leave it for others to puzzle over!

I will however suggest that the first question should be "Does there necessarily exist a straight line having exactly one million points on each side of the line?", as clearly there does exist such a straight line for some arrangements of the two million points...

Merry Christmas!

Gengulphus

[ReformedCharacter]

There are an infinite number of ways that a line can cross a circle, therefore it must always be possible to draw a line that leaves half the points on one side and half the points on the other, assuming that an even number of points exist within the circle.

RC

[Gengulphus]

There are an infinite number of ways that a line can cross a circle, therefore it must always be possible to draw a line that leaves half the points on one side and half the points on the other, assuming that an even number of points exist within the circle.

Not an adequate argument, I'm afraid. If it were, then the following similar argument would work: there are an infinite number of ways to express a whole number as the sum of two whole numbers (allowing negative numbers), therefore it must always be possible to express it as the sum of two even whole numbers.

Just saying that you need to tighten up your argument, by the way, not that it's wrong in the way that that argument that any whole number can be expressed as the sum of two even whole numbers is wrong. In particular, I'd suggest a reply to "If so, why, and how?" might give specific instructions about how to identify a suitable line (or at least how to identify it in principle - in practice, it would not be easy for two million points!).

Gengulphus

[jfgw]

There are an infinite number of ways that a line can cross a circle, therefore it must always be possible to draw a line that leaves half the points on one side and half the points on the other, assuming that an even number of points exist within the circle.

RC

That in itself isn't proof.

If you restrict the line to one specific angle, there are still an infinite number of ways of dividing the circle. However, it would not be possible to divide the circle with 1000000 points each side if two points lie on a line of that angle such that there are 999999 points each side.

There are an infinite number of angles, however, and only a finite number of angles where a line could pass through two (or more) points. If you restrict the line to any angle which cannot pass through more than one point at once, you can always divide the circle such that there are 1000000 points each side.

Julian F. G. W.

[UncleEbenezer]

The size and shape of the circle are of course a red herring, but we can use associated terminology.

The simple argument: there are a finite number of points. Therefore the number of straight lines joining any two (or more) points is also finite. Therefore the number of directions of such lines is also finite. We can express those directions as angles to an arbitrarily-selected diameter (hereafter the baseline) of the circle.

So pick an angle that is none of those (there's an uncountably infinite number of choices), and take a tangent at that angle. The tangent is a special case of a chord: it divides the points into two sets: one of two million points, the other of none.

Now move that tangent smoothly across the circle, preserving its angle to the baseline. Since we picked its angle never to pass through two points simultaneously, it crosses exactly one point at a time. So for any division (N, 2million - N) of the points, it creates that division somewhere as it crosses the circle.

Trivial corollary: at some point it solves the puzzle.

[UncleEbenezer]

Just to say that I knew the answer to this one as soon as I read it - I've encountered similar types of problem many times before - and so I'll leave it for others to puzzle over!

I probably have too, but it's so long ago I first thought Induction.

Merry Christmas!

Bah, Humbug.

There are an infinite number of angles, however, and only a finite number of angles where a line could pass through two (or more) points. If you restrict the line to any angle which cannot pass through more than one point at once, you can always divide the circle such that there are 1000000 points each side.

Damn, looks like you said it first.

Followup puzzle. What does the puzzle look like with an arbitrarily-selected countably infinite number of points? We could for example construct a set using any formula producing rational coordinates - and if we mix different formulae such as cartesian and polar coordinates, we can generate points that bear no rational relationship to each other. What about an uncountably-infinite set?

[Gengulphus]

... (there's an uncountably infinite number of choices) ...

As a quick observation, you can leave the word "uncountably" out of that and leave your argument intact and valid - which is a good thing because the difference between "countably infinite" and "uncountably infinite" is a far more technical mathematical distinction than the difference between "finite" and "infinite". In particular, I'd expect far more puzzlers to be reasonably happy that they understood the latter.

Followup puzzle. What does the puzzle look like with an arbitrarily-selected countably infinite number of points? We could for example construct a set using any formula producing rational coordinates - and if we mix different formulae such as cartesian and polar coordinates, we can generate points that bear no rational relationship to each other. What about an uncountably-infinite set?

If anyone wants an explanation of the terms, I'm happy to provide one. For those who are happy with them, spoiler:

In either case, it's distinctly questionable what "half" means with regard to infinity! But in the countably-infinite case, it's always possible to find a line with countably-infinitely many points on each side, and in the uncountably-infinite case, it's always possible to find a line with uncountably-infinitely many points on each side. So the answer is "yes" unless you have a more stringent definition of "half" in mind.

Gengulphus

[UncleEbenezer]

I'm seriously surprised at Gengulphus! I shall put that answer down to presumed seasonal excess!

In the countably-infinite case, we can trivially construct a counterexample, where any line has only a finite set on one side. Placing all our points on a single radius from 0 at the centre to 1 on the circumference, we take any sequence that converges asymptotically to zero. For example, 1/2, 1/4, 1/8, ...

p.s. on terminology, the ancient Greeks understood countable infinity and Xeno gave us my example above (and once you understand Xeno's Paradox - a.k.a. Achilles and the Tortoise - you've basically grasped Newtonian Calculus). 'Twas much later Cantor gave us a mindblowing hierarchy of infinities.

[Gengulphus]

I'm seriously surprised at Gengulphus! ...

Hmm... I'm seriously surprised at myself, especially as I can't really claim the excuse you suggest! But possibly I was more tired than I thought I was...

p.s. on terminology, the ancient Greeks understood countable infinity ...

But did they understand that uncountable infinities (or even just one of them) also exist? That's needed to understand the distinction between the two, and I'm not aware of anything indicating that they did...

Gengulphus

[UncleEbenezer]

p.s. on terminology, the ancient Greeks understood countable infinity ...

But did they understand that uncountable infinities (or even just one of them) also exist? That's needed to understand the distinction between the two, and I'm not aware of anything indicating that they did...

A fine point. At what point do you need the distinction? Measure theory and probability, perhaps?

p.s. apologies for jumping with such glee. I reflected after posting, I should've left time like Cinelli does for yours and others thoughts to run their course.

[jfgw]

For an uncountably infinite set, I feel that the question needs clarification.

Construct a circle anywhere within the circle in question and place a point anywhere on the circumference of that circle. Let the angle from the centre of your circle to that point be 0 radians. Place additional points on the circumference at angles from the centre equal (in radians) to all real numbers between 0 and 2pi (exclusive).

Any line which passes through this circle must pass through two points.

Whether or not this is a counter-example depends upon the exact question. There may still be an infinite number of points each side of the line but two points will be neither side.

Julian F. G. W.

[UncleEbenezer]

Whether or not this is a counter-example depends upon the exact question. There may still be an infinite number of points each side of the line but two points will be neither side.

Julian F. G. W.

I don't regard that as a counterexample, rather it's an aspect of formulation the question, and you'll notice that what I actually asked was how the question would look. I'd say you have correctly identified one aspect of it: that we have to allow a line to pass through some points (an uncountably infinite number if we fill your inner circle), and consider merely cardinality[1] either side of it for the conjecture[2] to hold.

The actual question to which it might be considered a counterexample seems to me of interest only if you're following Russell into fundamentals, and reviewing at length such questions as 1+1=2. That is to say, the intuitive answer is right, and for entirely the intuitive reason.

[1] Or perhaps Lebesgue measure. Or such other metric as might be of interest.
[2] I haven't thought it through for aleph 1, so the existence of a line dividing any such set into equal cardinality subsets is conjecture. A Cantor set doesn't produce a counterexample, but in my mind it kind-of cautions against assuming there is none!

[Gengulphus]

A fine point. At what point do you need the distinction? ...

The point at which you wrote the following!

Followup puzzle. What does the puzzle look like with an arbitrarily-selected countably infinite number of points? We could for example construct a set using any formula producing rational coordinates - and if we mix different formulae such as cartesian and polar coordinates, we can generate points that bear no rational relationship to each other. What about an uncountably-infinite set?

One can't understand that without the distinction between countable and uncountable infinities... ;-)

Gengulphus

[cinelli]

p.s. apologies for jumping with such glee. I reflected after posting, I should've left time like Cinelli does for yours and others thoughts to run their course.

UncleEbenezer is quite right – I do usually wait a day or two for the dust to settle before re-posting. His post on Christmas day at 6.39pm not only states that the problem is soluble but gives a very elegant method for an actual solution. Things have moved on since then. As a belated Christmas present for those who would like an entertaining and thought-provoking explanation of countable and uncountable infinities, I give you Eddie Woo:

https://www.youtube.com/watch?v=cgpDVOZpyrI

If you haven’t come across Mr Woo, he is a high school teacher in Sydney who puts his lessons on YouTube. Many times have people said, “I wish I had had a maths teacher like him.”

Cinelli

[UncleEbenezer]

A fine point. At what point do you need the distinction? ...

The point at which you wrote the following!

We could go round in circles here. I intended my point quoted there to refer to where in the history of mathematics anyone needed a distinction. Xeno grasped Infinity in his paradox; Eratosthenes grasped finiteness when he measured the curvature of Earth. But did any pre-19th-century mathematician consider concepts that rely on differing infinities?

For the purposes of this thread, I'm sure some regulars here understand the distinction, and others have no need to.

As a belated Christmas present for those who would like an entertaining and thought-provoking explanation of countable and uncountable infinities,

My "I wish I'd had a maths teacher like ..." moment came when I read G H Hardy's Mathematician's Apology. He brings it to life - including questions of infinity - using nothing more than simple concepts going back to Euclid. I don't think I've seen anyone remotely as inspiring without relying on much harder concepts. Happily for my own maths career, I read it some time before I had to make university choices, and it was one of the main influences that led me to maths as my degree subject.

Without pretensions to rival Hardy or Woo or other inspirational presenters, perhaps I should mention in passing that my method presented above constructs an uncountable infinity of uncountable infinities of solutions. That is to say, there is an uncountably infinite choice of directions for our line (reason: all possible directions in a plane minus a finite set), and then an uncountably infinite number of lines in each of those directions (reason: the space for it between points is an open set in Euclidean space). For the benefit of anyone who has read this far without knowing the concepts, this paragraph is true but not meaningful: being an infinity of infinities doesn't actually make it any bigger!

[jfgw]

Whether or not this is a counter-example depends upon the exact question. There may still be an infinite number of points each side of the line but two points will be neither side.

Julian F. G. W.

I don't regard that as a counterexample, rather it's an aspect of formulation the question, and you'll notice that what I actually asked was how the question would look. I'd say you have correctly identified one aspect of it: that we have to allow a line to pass through some points (an uncountably infinite number if we fill your inner circle), and consider merely cardinality[1] either side of it for the conjecture[2] to hold.

I am not so certain that we have to allow the line to pass through some points since the answer to the question "is it possible" could be "no".

My first thoughts when looking at this follow-up question were similar to the following:

Consider a circle containing a countably infinite number of points distributed in a way that allows a line of any angle to be defined such that there are an infinite number of points each side. Is it always possible for such a line (for which there are an uncountably infinite number of angles and positions) to exist which does not intersect at least one point?

Julian F. G. W.

[forlesen]

I think we can deal with the uncountably infinite case as well with an elaboration of UncleEbenezer's counter-example for the countably infinite case.

As before, consider the sequence of points 1/2, 1/4, 1/8, ... 1/2^i, ...

Consider a window of length 1/(2^(i+2)) around the i'th point, for all i (this value chosen so that the windows don't overlap).

Populate the i'th window with all the decimals of length i from 0 to 1, scaled and shifted to fit the window. So the first window would contain points corresponding to 0.1, 0.2, ..., 0.9, the second window would contain points corresponding to 0.01, 0.02,..., 0.99, and so on.

Now consider any point x such that 0 < x <= 1. Since x>0, there is some n such that 1/2^n < x. Thus there are only a finite number of points to the right of x (the points in the windows surrounding 1/(2^(n-1), ..., 1/2, each of whose windows only contain a finite number of points, specifically 10^i for the i'th window). However, to the left of x, we have decimals of unbounded length, and there will be an uncountable number of these.

[Gengulphus]

I think we can deal with the uncountably infinite case as well with an elaboration of UncleEbenezer's counter-example for the countably infinite case.

As before, consider the sequence of points 1/2, 1/4, 1/8, ... 1/2^i, ...

Consider a window of length 1/(2^(i+2)) around the i'th point, for all i (this value chosen so that the windows don't overlap).

Populate the i'th window with all the decimals of length i from 0 to 1, scaled and shifted to fit the window. So the first window would contain points corresponding to 0.1, 0.2, ..., 0.9, the second window would contain points corresponding to 0.01, 0.02,..., 0.99, and so on.

Now consider any point x such that 0 < x <= 1. Since x>0, there is some n such that 1/2^n < x. Thus there are only a finite number of points to the right of x (the points in the windows surrounding 1/(2^(n-1), ..., 1/2, each of whose windows only contain a finite number of points, specifically 10^i for the i'th window). However, to the left of x, we have decimals of unbounded length, and there will be an uncountable number of these.

No, I'm afraid your example only has a countably infinite number of points in it: I can easily put all of them into 1-1 correspondence with the positive integers, by putting 1-9 to correspondence with the points in the first window, 10-108 with the points in the second window, 109-1107 with the points in the third window, 1108-11106 with the points in the fourth window, etc.

The flaw in your argument is that there are only a countably infinite number of decimals of finite-but-unbounded length, just as there are only a countably infinite number of integers of finite-but-unbounded length. There are an uncountably infinite number of decimals of infinite length, but that's a different question - for example, sqrt(2) and pi are both in the set of decimals of infinite length, but not in the set of decimals of finite-but-unbounded length...

Gengulphus

[forlesen]

No, I'm afraid your example only has a countably infinite number of points in it

D'oh! Yes, it's obviously countable! I think an extension of your argument probably rules out any generalization of my idea too.

Suppose we have a set X of positive reals such that for all w in X, the subset Xw of all y in X such that y>w is countable, and X-Xw is uncountable. This is basically a less ambitious version of what I was aiming for with my specific construction, only asking for countable to the right, not necessarily finite.

I think we can count all of X, by considering the sequence w1, w2, w3, ... = 1/2, 1/4, 1/8, ... as before. For each of these wi, the set of points to the right is countable, and by taking the wi's far enough, for any X in X, there will be some wi less than x, so that x is in Xwi, and is hence counted, so X must (I think) be countable.

Assuming nobody shoots this down in flames, can the argument be extended to subsets X of R*R? We might consider whether for any family of parallel lines, for any line in the family, there is a countable number of points in X on one side of the line ("above" it, say), and apply a similar argument to count all of X.

If this is correct, we would seem to end up with for any uncountable subset X of R*R, there is a line that partitions X into two uncountable halves (plus some points on the line).