MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: combinatorics

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

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

  • Prev by Date: Re: Making Change, once more
  • Next by Date: Re: Time Series package w v 3.0
  • Previous by thread: combinatorics
  • Next by thread: Systems Reliability Calculation