7 ms·
Math Puzzle: Integer Points
- Scaevolus 13y agoI 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!
- deleted 13y ago[deleted]
- aeflash 13y agoThe line segment described by (0,0) (2,2) goes through the integer point (1,1).
- anonymoushn 13y agoYou chose 6 points, and there are 3 line segments among them containing (1,1).
- shib71 13y agoI 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.
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- Apes 13y agoI missed something critical, as you pointed out.
- nilkn 13y agoThere 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.
- tantalor 13y agoThat 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.
- olivier1664 13y agoSo that means that there will be at least on line which the center is an integer point.
- jonsen 13y agoThere 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.
- nazgulnarsil 13y agotrue, 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.
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- nazgulnarsil 13y agoback 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.
- anonymoushn 13y agoA 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 :)
- nazgulnarsil 13y agodoh, forgot to do the last and most important step, generalizing.
- cjg 13y agoWhy would 4 of the points form a square?
- eridius 13y agoThis 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.
- nemo1618 13y agoTechnically, the problem doesn't specify that the points have to be distinct...
- tantalor 13y agoYeah 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?
- deleted 13y ago[deleted]
- jonsen 13y ago(5,2) - (1,0) = (4,2) (4,2)/2 = (2,1) (2,1) + (1,0) = (3,1)
- nazgulnarsil 13y ago3,1 lies midway between 1,0 and 5,2.
- nemo1618 13y agoWhile 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 http://i.imgur.com/oY29sBc.png What function does this slope approximate? It almost a circle, but not quite.
- anonymoushn 13y agoThis is a quadratic Bézier curve http://en.wikipedia.org/wiki/B%C3%A9zier_curve http://en.wikipedia.org/wiki/B%C3%A9zier_curve
- jacobolus 13y agoOr in other words, it’s a section of a parabola. (As it happens, it’s a parabola tilted 45°, but still.)
- fahadkhan 13y agosqrt(x)+sqrt(y)=C
- chnuschper 13y agoIt'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.
- jules 13y agoSorry, 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
- deleted 13y ago[deleted]
- nimnam 13y agochoose 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.
- fahadkhan 13y agoIt doesn't hold. Pick (0,1), (0,2), (0,3), (0,4), (0,5) on the plane z = 0
- jonsen 13y agoWell, you have five integer points on the same line.
- fahadkhan 13y ago"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.
- vbuterin 13y agoIn 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.
- fahadkhan 13y agoOr is my assumption "more" means an integer point not in the set of five selected wrong?
- jonsen 13y agoYes, 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).
- thejteam 13y agoIf 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.
- deleted 13y ago[deleted]
- graycat 13y agoOkay, 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.
- mycsc 13y agoLOL. 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. :(
- counterexample 13y agoI 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.jpg http://farm9.staticflickr.com/8114/8661127874_f9269f0ee5_b.j... Is there something I'm missing?
- jonsen 13y ago(3,0) ... (6,2) ... (9,4) So comprehensive testing is what you are missing :-)