Timeline for Covering all except one of the purple intersection points of $n$ red and $m$ blue lines efficiently
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 10, 2017 at 4:59 | vote | accept | Gorka | ||
| Jun 10, 2017 at 4:42 | answer | added | Zach Teitler | timeline score: 3 | |
| Jun 10, 2017 at 3:39 | answer | added | Douglas Zare | timeline score: 4 | |
| Jun 10, 2017 at 3:24 | comment | added | Douglas Zare | It covers the case that the lines in each family are parallel. | |
| Jun 10, 2017 at 3:21 | comment | added | Gorka | @DouglasZare does the solution to that problem pass over to this one? | |
| Jun 10, 2017 at 3:21 | comment | added | Gorka | Here is the copy to the MSE clone. math.stackexchange.com/questions/2315092/… | |
| Jun 9, 2017 at 20:53 | comment | added | Douglas Zare | artofproblemsolving.com/wiki/index.php?title=2007_IMO_Problems/… quora.com/… I think I might have read about this on someone's blog on the Combinatorial Nullstellensatz. | |
| Jun 9, 2017 at 19:56 | comment | added | Gerhard Paseman | Oh, number of lines. Yes, I wrote n+m-1 instead of n+m-2. Gerhard "Mind Is Somewhere Else Today" Paseman, 2017.06.09. | |
| Jun 9, 2017 at 19:45 | comment | added | Gorka | Oh, I'll try for small cases, good suggestion! | |
| Jun 9, 2017 at 19:37 | comment | added | Gerhard Paseman | I am unsure what the correct reasoning is. I meant m, but I could be wrong; I meant just to give the form of part of the argument. Can you prove the result for small values of m? Gerhard "Hoping For Some Inductive Magic" Paseman, 2017.06.09. | |
| Jun 9, 2017 at 19:32 | comment | added | Gorka | yeah thanks, I tried that but I reached an impasse, the bound of no more than $m$ points on a line seems too weak. You mean $n+m-2$ right? | |
| Jun 9, 2017 at 19:30 | comment | added | Gerhard Paseman | There are also the diagonal lines for some regular configurations (I'm thinking of part of a square grid). I suspect an inductive proof may work to show n+m-1 is minimum: if more than m points are on a line, then it must be a red line, and now remove that red line from the set. Gerhard "Follow This Line Of Reasoning" Paseman, 2017.06.09. | |
| Jun 9, 2017 at 19:28 | comment | added | Gorka | It is easy to find examples in which different constructions exist, for example if we consider a $2\times 2$ grid and remove the bottom right corner we can find another construction with $2$ diagonal lines. But I haven't been able to find a construction with less lines. | |
| Jun 9, 2017 at 19:07 | history | asked | Gorka | CC BY-SA 3.0 |