Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
X/O Grid
Replies:
2
Last Post:
Dec 23, 2012 3:16 AM




Re: X/O Grid
Posted:
Dec 23, 2012 3:16 AM


On Fri, 21 Dec 2012, James Waldby wrote: > On Tue, 18 Dec 2012 22:32:43 0800, William Elliot wrote: > > > Consider an n by m grid of x's and o's.
n is width, m is height.
> > An xpath from the bottom squares of the grid to the top squares of > > the grid constitutes a sequence of horizontally or vertically adjacent > > xsquares from some bottom xsquare to some top xsquare. Similar > > with opaths. > > > > An exit is a top square that is connected to a bottom square by > > either an xpath or an opath. For example, in the 8 by 3, x/o grid > > > > x x o o x x o o x > > x o o x o x x x x > > o o x x x o x o x > > > > has two oexits and three xexits for a total of five exits. > > > > In an n by m, x/o grid, what is the expected number of exits? > > <http://pat7.com/jw/pathcounts/sampleresults> for more lines). > > m,n: 3 2 Total: 54 Avg.: 0.84375 > m,n: 3 3 Total: 1194 Avg.: 2.33203125 > m,n: 3 4 Total: 18306 Avg.: 4.46923828125 > m,n: 3 5 Total: 231634 Avg.: 7.06890869141 > m,n: 3 6 Total: 2614194 Avg.: 9.97235870361 > Yes, as the width n increases, the expected number of exits will incease.
> The other program, expCount.py, computes data like the following > via a few milliseconds of work. > > p= 0.5 > m n= 2 3 4 5 6 7 8 > 3 0.8438 2.3320 4.4692 7.0689 9.9724 13.0664 16.2766 > 4 0.6328 2.1489 4.6596 7.9910 11.9236 16.2681 20.8833 > 5 0.4746 1.9803 4.8587 9.0363 14.2647 20.2720 26.8264 > 6 0.3560 1.8249 5.0666 10.2193 17.0690 25.2702 34.4792 > 7 0.2670 1.6817 5.2834 11.5575 20.4259 31.5051 44.3256 > 8 0.2002 1.5498 5.5094 13.0711 24.4436 39.2805 56.9899 > I don't see why as the height m increases, that the expected number of exists would increase. In fact, I'd expect just the opposite.
> Note that the paths considered by the two programs only continue > (from a given square) by going left, right, or upward to a > notyettraversed square. That is, they count the following grid > as having no paths of either kind: > > 0 0 0 0 1 > 1 1 1 0 1 > 1 0 1 1 1 > 1 0 0 0 0
Oh oh. That grid has one exit. Note that the grid
1 1 1 0 1 1 0 1 1 1 1 0 0 0 0
has four exits.



