Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site ulysses.UUCP
Path: utzoo!linus!philabs!cmcl2!floyd!vax135!ariel!hou5f!hou5e!hou5d!hou5a!hou5h!eagle!mhuxi!mhuxj!mhuxl!achilles!ulysses!egs
From: egs@ulysses.UUCP
Newsgroups: net.math
Subject: Re: Yet Another Probability Problem (YAPP) - spoiler
Message-ID: <617@ulysses.UUCP>
Date: Mon, 26-Sep-83 02:58:45 EDT
Article-I.D.: ulysses.617
Posted: Mon Sep 26 02:58:45 1983
Date-Received: Thu, 29-Sep-83 02:36:30 EDT
Organization: Bell Labs, Murray Hill
Lines: 44


	It would seem that most of Jim's puzzles can be solved by brute force.
The exception is the chessboard puzzle which depends on noticing that it is not
possible to have more than one square whose number is max in its row and min
in its column. For example, if both w and x in this picture:

         .   .
         .   .
      ...w...y...
         .   .
         .   .
      ...z...x...
         .   .
         .   .

satisfy the max-min requirement, then we must have w>y, w<z, x>z, and x<y. In
other words, w>y>x and w<z<x, which are contradictory. Having noticed this,
we need merely count the ways in which each number can satisfy the max-min
requirement without having to worry about double counting. First, replace each
number with its rank order (i.e. 1, 2, 3, ..., N on an nxn board with N=n^2).
For a number m from this set, we must multiply the following numbers:

	C(m-1,n-1)*(n-1)!	number of ways in which we can select n-1
				numbers from the set numbers 1,...,m-1
				and arrange them on the same column as m
	
	C(N-m,n-1)*(n-1)!	number of ways the numbers larger than m can
				be put on the same row as m

	(N-2n+1)!		number of ways the remaining numbers can be
				arranged on the remaining squares
	
	N			number of squares on which the number m can rest

which gives:

	(n!)^2 * ((n-1)^2)! * C(m-1,n-1) * C(N-m,n-1).

Summing these terms over legitimate values of m (from n to N-n+1) and dividing
by N! will give the answer. For n=2, I get 2/3. For n=3, the answer is .3. For a
regular chessboard (n=8), I get .001243 or there abouts.

							Ed Sheppard
							BTL @ MH