Wikipedia:Reference desk/Archives/Mathematics/2021 June 8

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 8

Wang tiles

Hello!

Suppose I have a set of 24 edge matching Wang tiles, 1 for every possible arrangement of 4 colours on each tile. I am trying to convince myself that I cannot arrange them on a 6x4 grid with all internal edges matching. I know that it be done if the tiles are permitted any rotation but not if they are non-rotatable tiles. I am trying to use symmetry operations on the tile set to argue that it is not possible. For example, if I arrange 6 tiles with colour #1 on the top, I can then place above them all the tiles with #1 at the bottom. But from there any symmetry operation or combination of operations leads to duplicate tiles.

Am I on the right track?

Duomillia (talk) 03:13, 8 June 2021 (UTC)

Edit: If I go at it with pen and paper I think there might be away. Stay tuned I’ll post if I find something. Duomillia (talk) 04:01, 8 June 2021 (UTC)

A brute force search found 24 × 1248 solutions (1248 after fixing a corner tile).  --Lambiam 07:50, 8 June 2021 (UTC)

I find 328 basic solutions, from which all can be obtained by flipping an arrangement and recolouring its tiles.  --Lambiam 09:54, 8 June 2021 (UTC)

I'm curious as to whether there are any solutions where opposite edges have matching colors, thus creating a periodic tiling of the plane. If not, is there any periodic tiling where the unit cell uses all 24 tiles exactly once? --RDBury (talk) 20:12, 8 June 2021 (UTC)

Quite a few. Of the 328 basic solutions, 54 have matching opposite edges. Each rectangular reptile can be rotated horizontally and vertically and so each should be in a nest of 24 (4 × 6) sibling reptiles, but some of these siblings are the same modulo recolouring. There are four nests, one of 24 siblings, one of 12 siblings, and two of 9 siblings. I don't see how 9 is possible; a bug? To be continued.  --Lambiam 22:07, 8 June 2021 (UTC)

Thanks. I agree that 9 sounds suspicious since it's not a divisor of 24. --RDBury (talk) 05:39, 9 June 2021 (UTC)

The problem was that I only looked for siblings among canonical representatives of the basic solutions. Some (in fact, most) siblings of a basic solution are not themselves such canonical representatives, also not after recolouring. After fixing that, all nests have size 12 or 24.  --Lambiam 22:51, 9 June 2021 (UTC)

There are 10 reptile nests, 6 nests of 24 siblings and 4 nests of 12 siblings, together 6×24+4×12 = 192 reptiles (modulo recolouring, but not modulo flipping). If one randomly puts the 24 tiles in the 24 slots, the probability of having a solution (i.e., touching sides have matching colours) equals (24×1248)/24!. Given that it is a solution, the probability that it will have matching colours on opposite sides equals 192/1248 = 2/13 ≈ 15%.  --Lambiam 08:22, 10 June 2021 (UTC)

Follow up question: Is it possible to arrange my 24 tiles so that not a one edge is adjacent to the same colour? Duomillia (talk) 02:00, 14 June 2021 (UTC)

Yes; I found a solution.  --Lambiam 09:41, 14 June 2021 (UTC)

I expect that if you randomly assign the 24 tiles to the 24 slots, the probability of having no equally coloured adjacent edges is about (3/4)³⁸. That would mean there are on the order of 10¹⁹ solutions.  --Lambiam 15:31, 14 June 2021 (UTC)

Of 10⁹ random assignments, 12335 turned out to be solutions. That is a significantly less than (3/4)³⁸·10⁹, which evaluates to 17878⁺. It is in the ballpark, though: (12335/10⁹)^1/38 = 0.7427... < 3/4.  --Lambiam 21:10, 15 June 2021 (UTC)

Injective function definition

The definition (per Injective function) is stated as $\forall a,b\in X,\;\;f(a)=f(b)\Rightarrow a=b$. Isn't it an if and only if, since if a=b, then f(a) must equal f(b) or else f is not a function? Could someone clarify please?Nikolaih^☎️📖 21:47, 8 June 2021 (UTC)

These are equivalent statements. It is a matter of taste which of several equivalent definitions one prefers.  --Lambiam 22:18, 8 June 2021 (UTC)

Actually the other implication, "$\forall a,b\in X,\;\;a=b\Rightarrow f(a)=f(b)$", that is "$\forall a\in X,\;\;f(a)=f(a)$", would not add much information. pma 05:57, 9 June 2021 (UTC)

Thank you for your clarificationsNikolaih^☎️📖 07:13, 9 June 2021 (UTC)

This is also standard math writing. For example, MOS:MATH#TONE advises that "When defining a term, do not use the phrase "if and only if". For example, instead of A function f is even if and only if f(−x) = f(x) for all x, write A function f is even if f(−x) = f(x) for all x." --JBL (talk) 13:49, 9 June 2021 (UTC)

Correct, but I don't think that's the bit Nikolaih was talking about. A function is said to be injective if blah, rather than if and only if blah, but Nikolaih's point was about the implication inside blah itself. --Trovatore (talk) 17:31, 9 June 2021 (UTC)

Yes, I agree, thanks. --JBL (talk) 19:52, 9 June 2021 (UTC)