Factorally growing data storage

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
undecim
Posts: 289
Joined: Tue Jan 19, 2010 7:09 pm UTC
Contact:

Factorally growing data storage

Postby undecim » Fri Dec 11, 2015 2:04 pm UTC

If you have a stack of n cards, there are n! ways to arrange them. You can use this stack to store log2(n!) bits of data.

It's easy to see that the number of bits stored per card grows without bound. For example, notice that once you have a stack of 256 cards, each additional card allows you to store an additional 8 bits, because it adds a number greater than 256 to the factoral product. When you get to 512 cards, you're getting 9 bits per additional card. It will take a really big stack, but eventully you'll get terabytes of storage by adding a single card to the stack. At first glace, it would seem that this method of storage would allow you to outpace ANY method of storage that stores a bit in a fixed number of molecules, once you have a large enough pile.

Even assuming that storing, processing, and producing matter for creating the stack is a non-issue (future tech is pretty sweet), this method of data storage won't be more effecient than conventional methods. Why?
Blue, blue, blue

douglasm
Posts: 630
Joined: Mon Apr 21, 2008 4:53 am UTC

Re: Factorally growing data storage

Postby douglasm » Sat Dec 12, 2015 3:03 am UTC

The storage capacity of the stack of cards depends on the fact that each card is uniquely distinguishable from all the other cards. The information content added by a new card is actually capped by how many distinguishable cards you can make, and for any possible scheme of producing such distinct cards you could simply store that capped amount of information in the card itself with conventional methods.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Factorally growing data storage

Postby Cradarc » Sat Dec 12, 2015 9:10 am UTC

Why is this in Logic Puzzles?

It makes no sense to talk about bits when you are storing information as cards. As douglasm pointed out, you are still bit constrained if you want to create these cards abstractly. Physical "cards" are way too big to compete with the data density of modern electronics. You can't distinguish or stack molecules very easily.

The card system you are describing is kind of like how neurons work. Given n neurons, there are n!/(2!(n-2)!) = n(n-1)/2 possible connections. Since each connection can either exist or not exist, you effectively have n2 bits of capacity per n distinct neurons. The problem is we need a way to control the forming of connections without assigning an on/off switch to each of them.
This is a block of text that can be added to posts you make. There is a 300 character limit.

mward
Posts: 121
Joined: Wed Jun 22, 2011 12:48 pm UTC

Re: Factorally growing data storage

Postby mward » Wed Dec 16, 2015 11:41 am UTC

Cradarc wrote:Why is this in Logic Puzzles?

Because it is a logic puzzle! It may not be a very difficult one, but easy puzzles also have their place. For example, if you were giving an "Introduction to Information Theory" course, then this puzzle would make a good exercise.

With computer memory, flash drives or hard disks (ignoring Moore's Law for the moment), each additional unit of hardware, such as another memory chip or another disk drive, adds another unit of storage. So the storage grows linearly with the amount of hardware added. With the "card sorting" system the amount of information added increases superlinearly as each new card is added to the system. In theory, the card system will therefore become more space efficient than even the most efficient computer storage system available today! This is the puzzle.

Solution:
Spoiler:
The solution to the puzzle, as already pointed out, is that each card has to be distinct. Suppose the cards are distinguished by a serial number printed on the card. As the number of cards grows, the number of bits needed for the serial number increases: and the number will eventually become too big to fit on the card. So the cards will have to get bigger. So the amount of hardware added as each card is added is not constant but increasing.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 10 guests