#1
|
|||
|
|||
Is this a skull-buster or ridiculously simple?
This is actually a two-parter. The obvious answer to part one is that all numbers are equally likely to show up but I don't think it can be quite that simple because of the "3"s (see description).
Part 1: Take an X by Y grid. Let's put X and Y at 15 and 15. You have tiles numbered 1-9 to fill the board with. You pick the tiles blind and every tile has an equal chance of coming up. You fill the 15x15 grid with tiles in this manner. You then add the value of the tiles following these rules: - The individual tiles mean nothing. Only groups of tiles added together count for anything in this scenario. - The tiles are taken at face value. A tile labeled "9" is worth nine and so on. - You only add the values of non-diagonal neighbors. So, the maximum number of neighbors a tile can have is four (top, bottom, left, right) and tiles that are along any edge of the board have only three neighbors. The four corner tiles have only two neighbors each. In this manner, the minimum number a group of tiles can add up to is three (a corner tile worth one with two neighbors also worth one each). The most a group of tiles can add up to is 45 (a nine with four neighbors of nine each). My question is, if you randomly fill this board with the tiles numbered 1-9, is there any number that is the most likely to show up in the groups? It seems that I should expect to see less threes than anything else because there are only four possible places to make a three, but what about the other numbers? Part 2: If the numbers will not be evenly distributed, how do you calculate the likelyhood of a given number, or the number of times you can expect to see it in any given grid? Thanks, SpaceAce |
#2
|
|||
|
|||
Re: Is this a skull-buster or ridiculously simple?
I'll give it a shot, or at least get it started...
In the general n x n grid: 4 corners 4(n-2) edges (n-2)^2 interior So if you select a square at random, we have the following probabilities for the location of the square: P(corner) = 4/(n^2) P(edge) = 4(n-2)/(n^2) P(interior) = (n-2)^2/(n^2) For each different location, we can compute the probability of each sum of neighbors occuring in that spot. Starting with the corner: The lowest possible number is 3, only possible with 1,1,1 (one way) 4 is possible as 1,1,2 or 1,2,1 or 2,1,1 (three ways) and so forth.. so the number of ways to get each number k is the same as the number of ways to distribute k objects among 3 baskets with each basket getting at least 1 and at most 9 objects. I'm not seeing a clean way to express this for general k, there probably is one (k is a sum of identically-distributed discrete RVs, probably a simpler approach), and it would probably be simple to code for a program designed to solve this problem by brute force. Similar for edges (3 replaced with 4) and interior (3 replaced with 5). So then we have the probability of a randomly selected square being in a certain location and then conditional probabilities for each sum of neighbors given those, so we'd be done. |
#3
|
|||
|
|||
Re: Is this a skull-buster or ridiculously simple?
The table below shows the expected numbers of each total for a 15x15 grid. repulse's method is correct, all you have to do is add up the distribution of sums of three, four and five nines in the correct proportion. The most likely number is 24. 25 is the most common for the 13x13 = 169 squares with five tiles, but 24 is more common in the full square because it is more likely with 4 and 3 tiles than 25 is.
3 0.0055 4 0.0244 5 0.0675 6 0.1484 7 0.2837 8 0.4928 9 0.7978 10 1.2239 11 1.7990 12 2.5375 13 3.4414 14 4.5012 15 5.6959 16 6.9933 17 8.3496 18 9.7093 19 11.0059 20 12.1613 21 13.1021 22 13.7750 23 14.1437 24 14.1889 25 13.9087 26 13.3183 27 12.4500 28 11.3535 29 10.0953 30 8.7538 31 7.3986 32 6.0873 33 4.8666 34 3.7713 35 2.8250 36 2.0400 37 1.4167 38 0.9445 39 0.6010 40 0.3606 41 0.2003 42 0.1002 43 0.0429 44 0.0143 45 0.0029 To compute the distribution of the sum of n digits from 1 to 9, you start with n = 1, which is just 1/9 on the numbers 1 to 9. For n = 2, you just add this distribution to itself shifted down by 1, 2, 3 up to 9 spaces. You can keep doing this to get the distributions for n = 3, 4 and 5. It's easy to do in a spreadsheet. |
#4
|
|||
|
|||
Re: Is this a skull-buster or ridiculously simple?
Wow, thanks for the explanations, guys; I appreciate it. I am working on a game where the user drags tiles onto a grid, trying to make the tile and its neighbors add up to a certain value, and I was thinking of basing scoring on the difficulty of achieving the value. This is very helpful.
Edit: Heh, 24.25... purely guessing, I figured it'd be about 25. SpaceAce |
|
|