mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2010-08-04, 16:47   #1
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

2×197 Posts
Default Stacking boxes - combinatorics?

Here's a puzzle I'm working on right now. I promise it's not a homework problem. It's a problem for a program I'm considering. And I'm not sure if there's any easy solution without writing a program to solve it. It seems like combinatorics to me; but I never really studied combinatorics, so I'm hoping someone here knows an easy answer.

Suppose you have 16 cubic boxes and 16 different places to stack them. They can be in any arrangement - for example they can be laid out one in each place, or all 16 can be stacked in one place. Order doesn't matter, and orientation doesn't matter.

Now define the "maximum height" of any arrangement to be the height of the tallest stack in that arrangement. Question: What is the average "maximum height" for all possible arrangements of these boxes?

Question 2: Can you guess what problem I'm trying to solve here?
Ken_g6 is offline   Reply With Quote
Old 2010-08-04, 17:14   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

11·13·41 Posts
Default

For 1, I get 19/3. I'm using inefficient code based on Sloane's A008284 (my code has trouble even getting to n = 60).

For 2, I have no idea.
CRGreathouse is offline   Reply With Quote
Old 2010-08-04, 17:17   #3
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

Question: When you take an "average", it matters how many times you count each possible combination of stack sizes. So, do you consider 8-7-1 and 8-1-7 to be the same? Or are you trying to determine the expected value of the maximum number of objects that would fall in the same hash bucket - given that there is a total of 16 objects and the hash function provides a perfectly uniform hash into 16 buckets?
Wacky is offline   Reply With Quote
Old 2010-08-04, 17:22   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

11×13×41 Posts
Default

Quote:
Originally Posted by Wacky View Post
Question: When you take an "average", it matters how many times you count each possible combination of stack sizes.
The OP said that orientation and order don't matter, so that's what I assumed in my answer. Obviously if a different weighting was intended then the answer will be different.
CRGreathouse is offline   Reply With Quote
Old 2010-08-04, 17:42   #5
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

18A16 Posts
Default

That's a good question. I'm not quite sure what terminology to use.

Let me give an example where N=2, not 16. There are three possibilities:

X
X_

_X
_X

and just

XX

Technically, the boxes do have numbers, but I imagine what their number is doesn't matter.

Let me explain #2: In nVIDIA's CUDA system, there's a user-managed cache of memory called "shared memory". Threads access it 16 at a time. nVIDIA rather assumed that the user would access it linearly, so they set up 16 banks of memory, where the bank accessed is the address mod 16. If two threads access the same bank, it takes two accesses instead of one; three takes three accesses and so on.

Well, for my application, I would need a random-access lookup table. If CRGreathouse is correct, that's over 6 accesses on average - not good.

But thanks for solving that for me; it would have taken me hours writing an optimized recursive program.
Ken_g6 is offline   Reply With Quote
Old 2010-08-04, 17:58   #6
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

32·173 Posts
Default

Quote:
Originally Posted by Ken_g6 View Post
Question 2: Can you guess what problem I'm trying to solve here?
I'd guess you're trying to solve problem 12-3 in CLR (though that only gives you an upper bound on the expected maximum, not an exact value).
jyb is offline   Reply With Quote
Old 2010-08-04, 18:05   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

133478 Posts
Default

Quote:
Originally Posted by Ken_g6 View Post
If CRGreathouse is correct, that's over 6 accesses on average - not good.
You described a different weighting scheme in your last post than I used, so my result (while correct for what it was) does not directly apply to you.
CRGreathouse is offline   Reply With Quote
Old 2010-08-04, 18:25   #8
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

2×197 Posts
Default

What's CLR? Common Language Runtime? My Google-fu is weak.

Edit: Found it. I may have that book; let me look.

Edit2: Hm, hash chains, that's a good way to look at it, where n=m.

Last fiddled with by Ken_g6 on 2010-08-04 at 18:29
Ken_g6 is offline   Reply With Quote
Old 2010-08-04, 19:03   #9
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

2×197 Posts
Default

OK, having looked over 12-3, that seems like the right problem, but I don't believe the solution (M=lg(16)/lg(lg(16) == 2 in this case). It seems to me that there's only one way to get M=1, and several ways to get M>=3.

Edit: Oh, I see, there's a constant. Anyone know what the constant is?

Last fiddled with by Ken_g6 on 2010-08-04 at 19:04
Ken_g6 is offline   Reply With Quote
Old 2010-08-04, 19:21   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

11×13×41 Posts
Default

Maybe what you want is Sloane's A019575? Look at that and tell me what you think.
CRGreathouse is offline   Reply With Quote
Old 2010-08-04, 20:26   #11
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

2·197 Posts
Default

That's darn close. What I'm looking for is based on that:

sum(k=1 to n, T(n,k)*k)/sum(k=1 to n, T(n,k))

Now how's that T(n,k) calculated? The "Formula" section is unclear to me.

Edit: I'm also confused; shouldn't T(n,n) = 1 or n or something? But maybe I'm wrong about that?

Last fiddled with by Ken_g6 on 2010-08-04 at 20:28
Ken_g6 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Combinatorics news Nick Combinatorics & Combinatorial Number Theory 7 2019-12-14 15:25
Finding primes using modular stacking goatboy Math 1 2007-12-07 12:30
Weight of boxes victor Puzzles 1 2007-06-04 16:26
Combinatorics Kees Puzzles 6 2006-05-13 06:58
Switching Boxes Numbers Hardware 7 2005-09-12 19:10

All times are UTC. The time now is 00:40.

Fri Aug 7 00:40:07 UTC 2020 up 20 days, 20:26, 1 user, load averages: 1.50, 1.56, 1.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.