Mathematics desk
< May 31	<< May \| June \| Jul >>	June 2 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an 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 1

Question regarding a 4 x 4 sliding tiles puzzle

When I was young, I had a metal trinket from who knows where. It was a tiles grid, with 16 squares (though one was empty, so you could slide the tiles around.) The squares had the numbers from 1 to 15 on them, and in solved form you would get a grid that looked like this:

1 . 2 . 3 . 4

5 . 6 . 7 . 8

9 .10 11 12

13 14 15 __

Of course, the point was to mix the tiles up and work on getting them back into this solved state.

However I once read something that stated that "if, from the solved state, you switched the 14 and the 15 tiles, the puzzle would become unsolveable."

So, my two questions:

1) Is that true, that such a simple change makes the puzzle unsolveable?

2) Assuming 1 is yes, what if I simplified the puzzle to a 3 x 3 grid, then switched tiles 8 and 9. Would the puzzle then be likewise unsolveable? 169.231.8.137 (talk) 06:28, 1 June 2013 (UTC)[reply]

Yes the puzzle is unsolvable from half the starting positions, and the 3 x 3 can always be solved. See 15 puzzle.--Salix (talk): 06:36, 1 June 2013 (UTC)[reply]

Ooh, thank you! 169.231.8.137 (talk) 06:41, 1 June 2013 (UTC)[reply]

No there's the same rule for 3x3 or any size, if you swap the two tiles it can't be solved. Dmcq (talk) 15:08, 1 June 2013 (UTC)[reply]

Wikipedia has the article "15 puzzle".—Wavelength (talk) 16:27, 1 June 2013 (UTC)[reply]

Permutations

I am attempting to determine the number of possible combinations of a given set. For the sake of simplicity, the 6 items are A,B,C,D,E, and F. Only 3 of these items can be used in a combination at once. Each letter may be repeated in a combination any number of times up to 3. The order of the letters is irrelevant. For instance, ABB is the same as BAB and BBA. How can I determine the number of unique combinations, taking into consideration the irrelevance of the order of the items mentioned previously?Calamus Fortis 07:22, 1 June 2013 (UTC)[reply]

First, let's recast this as an equivalent problem: You have 6 buckets, labeled A, B, C, D, E and F. You have 3 identical balls. How many ways can you distribute the three balls among the 6 buckets? Hopefully, you agree that this is equivalent.

Now let's recast this again: How many different sequences are there using 3 stars (*) and 5 bars (|)? Each sequence codes an assignment of balls into buckets, with stars representing balls and bars representing the boundaries between buckets. Buckets are listed in order. So *|*|*||| means 1 ball in bucket A, 1 ball in bucket B and 1 ball in bucket C. ||*|||** means 1 ball in bucket C and 2 in bucket F. Etc.

This is straightforward to calculate: there are 8! sequences of 8 characters, but permuting the 3 stars doesn't generate a new sequence, so divide by 3!. Similarly, permuting the bars doesn't generate a new sequence, so also divide by 5!. 8!/(3! 5!) = 56.--80.109.106.49 (talk) 13:49, 1 June 2013 (UTC)[reply]

Your problem is treated here: Multiset#Counting_multisets. Bo Jacoby (talk) 06:53, 3 June 2013 (UTC).[reply]

Question regarding a congruence and the multiplicative order

I am investigating the congruence 2ⁿ ≡ 1 (mod (n + 1)²). I try to prove that if $n\in \mathbb {N}$ is a solution to this congruence, then n is a multiple of ord_{(n + 1)²}(2). How could this be done (at least, what strategy could one pursue to do this)? I appreciate any hints. -- Toshio Yamaguchi 11:32, 1 June 2013 (UTC)[reply]

Unless I'm misunderstanding your question, this follows immediately from the definition of order; in general, for any element g of a group if m is the smallest integer so g^m = 1 and gⁿ = 1, then m | n; you can take a look at out article on the order of group elements. So if it has a solution, then the order divides it.Phoenixia1177 (talk) 00:10, 2 June 2013 (UTC)[reply]

Thanks for the reply. So if I understand correctly, for a specific m = (n + 1)², the powers of two modulo m form a cyclic group, because the residues of 2^k (with k = 1, 2, 3, 4, ...) modulo m can only take on a finite number (say x) of values for that m. And a specific residue will "reoccur" with period x for increasing k. -- Toshio Yamaguchi 09:04, 2 June 2013 (UTC)[reply]

If 2 is coprime to m, then yes; in your case, if there is a solution, then (n + 1)² | 2ⁿ - 1, if n + 1 where even this couldn't occur. Hence, n + 1 and 2 are coprime. If you look at our article Bézout's identity, you'll see that if d is the greatest divisor of a and b, then there are x and y so ax + by = d, so ax = d mod b. If d is 1, meaning a and b are coprime, then there is x so ax = 1 mod b, so a is in the group of units mod b. On the other hand, if a is in the group of units mod b, then there is c so ac = 1 mod b and we can write ac = by + 1, for some y. Then, ac - by = 1, from the same article you can see this means a and b are coprime. So, elaborating on what you wrote above, a^x = 1 mod b has a solution x iff a is a unit mod b iff a and b are coprime.Phoenixia1177 (talk) 20:44, 2 June 2013 (UTC)[reply]

On the subject of your problem, n can never be the order unless n + 1 is prime, it must be strictly larger. Write phi(k) for the totient function, by a quick generalization of Fermat's Little Theorem a^phi(k) = 1 mod k for all k and a coprime k. Then, if n is the order of 2 mod (n + 1)², n | phi((n + 1)²). Let n + 1 have prime factorization
p₁^a₁...p_s^a_s; phi((n + 1)²) = ((n + 1)² /p₁...p_s) * (-1 + p₁)...(-1 + p_s). Since n and n + 1 are coprime, n | t = (-1 + p₁)...(-1 + p_s), but n = p₁^a₁...p_s^a_s - 1; however, unless s = 1 and a₁ = 1, then t < n implying not n | t.Phoenixia1177 (talk) 23:21, 2 June 2013 (UTC)[reply]

Have you found any such n? I didn't see any for n < 18 (then I stopped checking), so I'm guessing this isn't an accidental pattern you noticed given that 2 ** n get's pretty big at that point. Have you found any solutions? For some reason, I get the feeling they don't exist or are rare, but haven't really looked into it.Phoenixia1177 (talk) 09:56, 3 June 2013 (UTC)[reply]

Indeed. If 2ⁿ ≡ 1 mod (n + 1)² then n+1 is a Wieferich prime. Only two Wieferich primes are known: 1093 and 3511. Gandalf61 (talk) 10:51, 3 June 2013 (UTC)[reply]

There are no solutions for n < 1000, as Gandalf says. The first solution is 1092, which is due to the fact that 1093 is a Wieferich prime. It is easy to see that if an odd prime p is a Wieferich prime (i.e. satisfies 2^p-1 ≡ 1 (mod p²)), then the exponent p-1 (1092 in this case) is a solution to the congruence 2ⁿ ≡ 1 (mod (n + 1)²). These are exactly the cases where n is a solution such that n + 1 is prime, and according to the latest result from the ongoing Wieferich prime search here, there are no others up to approximately 10¹⁷. However, I suspect that there might be cases where n + 1 is composite. If such cases exist, they should be EXTREMELY rare, because in that case, m = n + 1 must be a Fermat pseudoprime to base 2 having two additional properties:

m must satisfy 2^m-1 ≡ 1 (mod m²) and
all prime factors of m must be Wieferich primes

One could download the file annotated-psps-below-2-to-64.txt.bz2 from here and check, whether there are entries whose only prime factors are 1093 or 3511. The only such numbers I am aware of are 1093² and 3511², but it seems extremely unlikely to me that either (1093² - 1) or (3511² - 1) satisfies 2ⁿ ≡ 1 (mod (n + 1)²). Suppose that were the case: It means we have (for (1093² - 1)) 2^1093²-1 ≡ 1 (mod (1093²)²), ie. 2^1093²-1 ≡ 1 (mod (1093⁴)). According to theorem 5 of [1], 2^p²-1 ≡ 1 (mod p²) if and only if 2^p-1 ≡ 1 (mod p²), so if say (1093² - 1) satisfied 2ⁿ ≡ 1 (mod (n + 1)²), 1093 would have to satisfy 2^p-1 ≡ 1 (mod p⁴). So I guess the only numbers that could reasonably be expected to be solutions such that n + 1 is composite would be ~~base 2 pseudprimes~~ numbers n such that n + 1 is a base 2 pseudoprime all of whose prime factors are distinct Wieferich primes. No such number seems to exist below 10¹⁵. -- Toshio Yamaguchi 11:07, 3 June 2013 (UTC)[reply]

Indeed, in PARI

Mod(2,1194648)^(1194649^2%eulerphi(1194648))

gives Mod(298664, 1194648) and

Mod(2,12327120)^(12327121^2%eulerphi(12327120))

gives Mod(3106352, 12327120)

confirming that neither (1093² - 1), nor (3511² - 1) satisfy 2ⁿ ≡ 1 (mod (n + 1)²). -- Toshio Yamaguchi 12:03, 3 June 2013 (UTC)[reply]

Circulation

I have been looking into hyper-operators and indeterminate forms and have found several references in PDF's and such to something known as circulation. Circulation, by several articles I have come across is defined as;

$a\uparrow ^{\infty }b$

But I cannot seem to find any real information on the subject. Does anyone know anything about circulation? Who came up with the concept? Has any work been done on the convergence of circulated functions? — Preceding unsigned comment added by 109.153.168.240 (talk) 17:18, 1 June 2013 (UTC)[reply]

Note: I have attempted to fix your broken syntax -- Wikipedia's "math" system does not allow special characters such as "∞" to be mixed in with math code. Hopefully the thing I changed it to is what you intended. Looie496 (talk) 22:42, 2 June 2013 (UTC)[reply]

Are you asking about what that notation means, or about what this circulation is? I don't know about the latter, but you might get a sense of the operation at Knuth's up-arrow notation. SemanticMantis (talk) 17:13, 3 June 2013 (UTC)[reply]

I can't find any definitions like that at a glance. If you give us the reference to at least one paper that has this usage, we could probably help you track down the origin and other work. SemanticMantis (talk) 17:17, 3 June 2013 (UTC)[reply]

Well thats the problem. I found several inconsistent references but I couldn't find any of them elsewhere. I understand the notation but I can't find any actual information on it. Also cheers for fixing it! I tried several times but just gave up in the end!