|
||
|
Title: Parallelogram for sure with enough checkers Post by ecoist on Mar 1st, 2006, 7:14pm Show that if 16 checkers are on an 8 by 8 checkerboard, at most one per square, then some four of the checkers occupy four squares whose centers are the vertices of a parallelogram with positive area. |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by Icarus on Mar 2nd, 2006, 7:38pm Number the rows and columns with (0-7) to identify each location with a coordinate pair (x, y). For any two checkers at locations (a, b) and (c, d), define their "displacement vector" = (c - a, d - b) if c >= a, and to be (a - c, b - d) otherwise. The x-value of displacement vectors can be anything from 0 to +7, but the y-value can range from -7 to +7. However, the vector (0,0) will not occur. Hence there are 119 possible displacement vectors. Two pairs of checkers form opposite sides of a parallelogram if and only if the displacement vectors of the pairs are the same. For 16 checkers, there are C(16,2) = 120 pairs. Since there are only 119 possible values for displacement vectors, at least two pairs must have the same vector. Note also that 15 checkers is not enough, as filling the left column and bottom row does not create any parallelograms. |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by ecoist on Mar 2nd, 2006, 8:51pm Very nice! Very different from my proof, and equally short. Your proof explains better why 16 checkers is the minimum. My proof shows the existence of both a parallelogram with one pair of opposite sides vertical and one with one pair of opposite sides horizontal (which two could be the same parallelogram), suggesting that one might be able to get away with fewer checkers than 16. Both proofs show some "Calendar Magic". Given any 16 elements from {1,...,64}, there exist four of the given numbers with the property that the sum of two of these four equals the sum of the other two of the four. Of course, for this problem maybe one can get away with fewer than 16 elements, since the "parallelogram" need not have positive area for this problem. |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by Barukh on Mar 3rd, 2006, 12:45am I had the same idea as Icarus's, but then somehow realized that it won't work: the argument presented does not rule out the parallelograms with 0-area. Consider the Icarus example with 15 checkers: although there is no parallelogram satisfying the conditions of the problem, there are many pairs with the same displacement vector, e.g. (0,1), (0,2) and (0,4), (0,5). |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by ecoist on Mar 3rd, 2006, 6:01am You are so right, barukh! But Icarus's solution works beautifully for the "Calendar Magic" problem, while my proof fails utterly on it. Does Icarus's solution generalize to calendars with m rows and n columns, i.e., the set {1,...,m*n}? |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by ecoist on Mar 3rd, 2006, 8:13am Drat! I am wrong again! Icarus's solution does not work for the "Calendar Magic" problem. Checkers at (0,0), (0,1), and (0,2) determine two checker pairs producing the same displacement vector. However, this is only 3 checkers, not 4. |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by ecoist on Jul 4th, 2006, 3:06pm Since there is as yet no correct solution to this problem, I presume that my erroneous comments are the cause. Is it time for a hint? If you can seperate the wheat from my chaff, you already have a hint. |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by ecoist on Jul 13th, 2006, 11:04am [hideb]I prove the more general result: If m+n checkers are placed on an m by n checkerboard, at most one checker per square, then some four of the checkers occupy four squares whose centers are the vertices of a parallelogram with positive area. Proof. If there are x>0 checkers in a column (containing m squares), then there are at least x-1 distinct "differences", i.e., the number of pawn moves for one checker to move in that column to the other checker; because each checker below the "top" checker most move a different number of squares to reach that top checker. For each column i, from 1 to n, let ai be the number of selected checkers in that column. Choose ai-1 pairs of checkers in that column with distinct differences, for each i. Then a1-1 + ... + an-1=m+n-n=m. Since a column has exactly m checkers, there can be at most m-1 distinct differences for two checkers in one column. Hence some difference is repeated in the above sum. Since, in addition, we have chosen no checker pairs with repeated differences within a column, some two distinct columns have checker pairs with the same difference. Therefore, the centers of the squares these four checkers occupy form the vertices of a parallelogram with positive area.[/hideb] |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by Icarus on Jul 25th, 2006, 2:15pm Nice! |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by Barukh on Jul 29th, 2006, 5:55am I second Icarus. Nice demonstration! :D In fact, ecoist, you have shown a bit more: that under the stated conditions, there exists a parallelogram with at least one side parallel to the side of the board. |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by ecoist on Jul 29th, 2006, 10:07am Thanks, Icarus and Barukh. Regarding sides parallel to the sides of the board, I have another problem I hesitate to post, fearing it may be a special case of a theorem (about 0,1-matrices?). Given 58 checkers on a 14x14 checkerboard, at most one checker per square, there exist four of the given checkers which lie on squares whose centers form the vertices of a nondegenerate rectangle with all sides parallel to a side of the checkerboard. |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by Deedlit on Aug 1st, 2006, 5:23pm [hideb] There are C(14,2) possible pairs of rows; if column i has ni checkers on it, there are C(ni,2) pairs of rows both containing checkers on column i. No two columns can share the same row pairs, so the ni satisfy Sum ni = 58 Sum C(ni,2) <= C(14,2) = 91 If nj >= nk + 2, we can decrease the second sum while keeping the first constant by increasing nk by 1 and decreasing nj by 1. So we need only check whether there are ni satisfying the conditions where the values are at most one apart. This requires 12 values of 4 and 2 values of 5; but then the second sum is 92. Generalizing to arbtrary side length n, we get an upper bound asymptotic to n3/2. [/hideb] |
||
|
Title: Re: Parallelogram for sure with enough checkers Post by ecoist on Aug 1st, 2006, 6:40pm Right on, Deedlit! Corollary to what you did: Let G be an undirected graph with no loops or multiple edges, with 14 nodes and at least 29 edges. Then G has a 4-cycle. |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |