Is this a skull-buster or ridiculously simple?

[SpaceAce]

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

[repulse]

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.

[AaronBrown]

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.

[SpaceAce]

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