Math Puzzle: Integer Points | Hacker News Reader

Math Puzzle: Integer Points

pratikpoddarcse.blogspot.in

40 pointspratikpoddar42 comments

There are four pairs of values modulo two, so if you have five points some two of them must be the same modulo two. Say these points are A and B. Then A + B = (even, even), and so (A + B) / 2 has integer coordinates.

That was tough to follow, let me restate,

Let the two points be (x1, y1) and (x2, y2) such that x1 % 2 == x2 % 2 and y1 % 2 == y2 % 2, i.e., have the same parity.

Then x1 + x2 = 2 * x3 (is even) and y1 + y2 = 2 * y3 (is even), and (x3, y3) is an integer point.

Given five points, two such points must exist because of the pigeon hole principle.

So that means that there will be at least on line which the center is an integer point.

There are four possible coordinate parities

  (even, even),  (even, odd),  (odd, even),  (odd, odd)

Among five points two must have the same parity.

Between two points of same parity the difference has the parity (even, even).

As (even, even) is divisible by two there's an integer midpoint.

true, you can always make one of the 4 lines have a slope that is even/even. the point composed of x/2,y/2 will lie on this line.

I don't understand. Choose points (0,0) (0,1) (1,0) (1,2) (2,1) (2,2). What line contains three points?

Diagram:

_OO

O_O

OO_

e: oh, not a point in the original set, any integer point. thanks!

I think the question might be better put this way:

Pick 5 random points on an infinite plane. Draw lines between all of them. One of those lines will contain another integer point. Prove this is true for every set of 5 random points.

You chose 6 points, and there are 3 line segments among them containing (1,1).

The line segment described by (0,0) (2,2) goes through the integer point (1,1).

Technically, the problem doesn't specify that the points have to be distinct...

Yeah that bothered me too. If all the points are (0, 0), does that satisfy the conditions? Does the line segment (0, 0) to (0, 0) "contain" an integer point?

This seems rather trivial.

Take two arbitrary points, named A and B, where Ax < Bx (if Ax == Bx, this becomes absurdly simple).

Calculate the delta ∂ between the points, such that ∂x = Bx - Ax and ∂y = By - Ay

Define a third point C such that Cx = Bx + ∂x and Cy = By + ∂y.

C is integral, and is colinear with A and B.

C does not lie on the line segment AB.

Oh my, I didn't notice the word "segment" there. That does change the problem.

While we're all solving puzzles, can anyone help me with this one?

No doubt you've doodled this shape in your graph paper before: http://i.imgur.com/oY29sBc.png

What function does this slope approximate? It almost a circle, but not quite.

This is a quadratic Bézier curve http://en.wikipedia.org/wiki/B%C3%A9zier_curve

Or in other words, it’s a section of a parabola. (As it happens, it’s a parabola tilted 45°, but still.)

It's y=(sqrt(x) - 1)^2

Consider the function l(t) which gives the appropriate line function f(x) for the line going through (t,0). The function we are looking for can then be defined as c(x) := max(l(t)(x), t in (0;1]). Just solve for t and pop it into l(t), et voila.

Sorry, I accidentally down-voted you when I tried to up-vote you. This answer is absolutely correct. Here is my very similar derivation:

All lines go through (t,0) and (0,1-t). Now take two such lines, one with constant t and another with constant s and find their intersection. We have:

    y = 1-t - (1-t)/t * x
    y = 1-s - (1-s)/s * x

So:

    1-t - (1-t)/t * x = 1-s - (1-s)/s
    s-t = (s-t)/(st) * x

So:

    x = st

The points on the curve will be generated by the intersection of two almost adjacent lines (this is easy to see geometrically), so we take s =~ t. Then we have:

    x = t^2
    y = (1-t)^2

So we have:

    y = (1 - sqrt(x))^2

Or, my favorite form:

    sqrt(x) + sqrt(y) = 1

sqrt(x)+sqrt(y)=C

LOL. For any two integer points P(i, j), Q(l, m). We have the equation of a line:

y - j = ((m - j) / (l - i)) * (x - i)

Choose x = k * (l - i) + i y = k*(m - j) + j Since i, j, l, m, k are all integers we obtain another integer point. No need 5 points... I may misunderstand the question. :(

I don't see any obvious problem with this counterexample: (0,5), (3,0), (4,6), (7,1), (9,4)

http://farm9.staticflickr.com/8114/8661127874_f9269f0ee5_b.j...

Is there something I'm missing?

(3,0) ... (6,2) ... (9,4)

So comprehensive testing is what you are missing :-)

Deleted comment

I missed something critical, as you pointed out.

back of the napkin: take the first 4 points to be a unit box with the lower left point at the origin. You can draw any of 4 lines to the 5th point (x,y). These 4 lines will have slopes x:y, x-1:y, x:y-1, x-1,y-1. You can always arrive at a slope ratio that is evenly divisible through some combination of -1 and reducing the ratio to simplest form. An evenly divisible slope ratio will pass through another point.

example: 5th point (11,4). Choose line with slope 10:4. Divisible by 2, this line passes through the point (5,2). A ratio divisible by 3 would pass through 2 additional points etc.

A real proof would work for an arbitrary first four points (with any segment between two not containing a lattice point), but I think nikln already provided this :)

doh, forgot to do the last and most important step, generalizing.

Why would 4 of the points form a square?

If I am remembering correctly, this was on the ARML(American Regions Math League) competition "power question" roughly, say 16-17 years ago. The answers given here from nilkn and the children comments are correct.

choose two integers x and y. These represent the first point on a plain. Only adjacent points can be added i.e. any point can only be 1 integer away from this origin point otherwise there will exist an integer point between the origin point the chosen point. so now we have (x, y), (x+1, y), (x, y+1), and (x+1, y+1). Adding a fifth point anywhere on the graph will make it such that an integer point will exists between two of the selected points.

Deleted comment

(5,2) - (1,0) = (4,2)

(4,2)/2 = (2,1)

(2,1) + (1,0) = (3,1)

3,1 lies midway between 1,0 and 5,2.

It doesn't hold. Pick (0,1), (0,2), (0,3), (0,4), (0,5) on the plane z = 0

Well, you have five integer points on the same line.

"Suppose we arbitrarily choose 5 integer points in a plane.

Show that we can always find 2 among these 5 integer points such that the line segment joining the 2 points contains at least 1 more integer point."

I am not sure what you mean. I have 'arbitrarily' picked 5 integer points on a plane. Yes, they happen to lie on line. All their line segments contain only these integer points.

Perhaps you mean that is line not on "a plane"? In that case (0,0), (0,1), (0,2), (0,3), (0,1) is another counter example.

In the case of {(0,0),(0,2)}, (0,1) counts as "1 more integer point" - the point has to be not one of the two points generating the line, not a point outside the set of 5 points on the plane.

Or is my assumption "more" means an integer point not in the set of five selected wrong?

Yes, it's wrong. It means at least one integer point more than the two integer end points (which of course have to be on the line).

Okay, we have a solution for the plane. The plane is in two dimensions. Now, for any positive integer n, generalize the problem to n dimensions.

So, now the problem is, for any positive integer n, given any 2^n + 1 n-tuples of integers, at least two of these n-tuples if added have all even components.

Reply on news.ycombinator.com