Re: combinatorics

*To*: mathgroup at smc.vnet.net*Subject*: [mg15189] Re: combinatorics*From*: Daniel Lichtblau <danl>*Date*: Fri, 18 Dec 1998 02:11:05 -0500*Organization*: Wolfram Research, Inc.*References*: <75a4og$sbg@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

mcp wrote: > > problem:a grid with (m+1) row and [m*C(m+1,2)+1] column,to fill the grid > with m kind of colors, one little grille with one kind color. In the > grid ,there must be a rectangle of which four corner grilles have same > color. Why? There are m+1 rows but only m colors. This means every column will have at least one color repeated. There are C(m+1,2) ways to choose a pair of distinct rows, hence m*C(m+1,2) ways to choose a distinct pair of rows and a color. Now list, for each column, a pair of rows that have the same color, along with that color. As per above, there can be at most m*C(m+1,2) distinct elements in that list. But you have one column more than that, so there must be a repetition; this gives your rectangle. I've no idea how this is related to Mathematica. If this is your homework then I want a part of the grade. Daniel Lichtblau Wolfram Research