December 23 Information

In The Settlers of Catan, the board consists of 19 hex tiles in the obvious symmetrical array; these tiles are of six kinds, abstractly AAAA BBBB CCCC DDD EEE F. I'm wondering how many ways the tiles can be arranged so that no two tiles of the same kind are adjacent. — Tamfang ( talk) 07:54, 23 December 2012 (UTC) reply

I would think there would have to be 7 kinds of tiles, for this ever to be possible. This is because any given tile is surrounded by 6 others in a hexagonal array. StuRat ( talk) 00:01, 24 December 2012 (UTC) reply

I don't think that this is quite so: the Four color theorem suggests otherwise. — Quondum 06:32, 24 December 2012 (UTC) reply

Correct, I misread the Q as "...so no two tiles adjacent to a tile are the same kind". StuRat ( talk) 07:05, 24 December 2012 (UTC) reply

Somewhat less than 19!. There are 2+3+4+3+2=14 set of adjacent-pair tiles in each direction so 3*14=42 posible pairs. For a legal arrangement no pair can have the same letters. Taking a rough probabilistic approach. Consider one pair of tiles with the two tiles chosen at random, we have p(AA)=4/19*3/18=2/57, p(BB)=2/57 p(CC)=2/57 p(DD)=3/19*2/18=1/57 p(EE)=1/57. So there is a 8/57 chance the pair will contain matching tiles and a 49/57 chance they will not match. Incorrectly assume all these events are independent chance of a legal arrangement = (49/57)^42 = 482562011/821843467 ≈ 0.002. Multiply this by 19! gives approximately 4*10¹⁴ legal arrangement out of 2*10¹⁷ total.-- Salix ( talk): 08:37, 24 December 2012 (UTC) reply

You could get a more precise guess by taking a large random sample of all the 19! arrangements and checking what ratio of them has adjacent tiles of the same color. I'm too lazy to do that now though. – b_jonas 18:31, 27 December 2012 (UTC) reply

Is it true that the square of any prime number (like 2² = 4, 3² = 9, 5² = 25, etc) has exactly three divisors? In other words, if p is a prime number, is it always true that the only divisors of p² are 1, p and p²? -- Toshio Yamaguchi 12:13, 23 December 2012 (UTC) reply

Yes. This follows from the fundamental theorem of arithmetic.

More generally, if ${\displaystyle n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}}$ where the ${\displaystyle p_{i}}$ are prime and distinct, then the number of divisors of n is ${\displaystyle \sigma _{0}(n)=\prod _{i=1}^{k}(\alpha _{i}+1)}$. In your case ${\displaystyle k=1}$ and ${\displaystyle \alpha _{1}=2}$. -- Meni Rosenfeld ( talk) 12:23, 23 December 2012 (UTC) reply

Ah, okay I see. I also see now that if this where not the case, then if p² had another prime factor, then, since p x p already yields p², p² would be expressible as a product of primes in more than one way, which contradicts FTA. Thank you. -- Toshio Yamaguchi 12:33, 23 December 2012 (UTC) reply