Welcome to the mathematics section
of the Wikipedia reference desk.

Select a section:

WP:RD/MA

Want a faster answer?

Main page: Help searching Wikipedia

How can I get my question answered?

Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
Post your question to only one section, providing a short header that gives the topic of your question.
Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
Don't post personal contact information – it will be removed. Any answers will be provided here.
Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
Note:
- We don't answer (and may remove) questions that require medical diagnosis or legal advice.
- We don't answer requests for opinions, predictions or debate.
- We don't do your homework for you, though we'll help you past the stuck point.
- We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

May 26

P!=NP based on its own proof difficulty?

Scott Aaronson has said that P versus NP is itself in NP and would probably be easy to prove if P=NP. Our article P versus NP problem#Results about difficulty of proof indicates that several methods of proof have been shown not to be possible. This suggests that if that list were expanded, a proof of the following form might be possible: "If P=NP, then the proof that P=NP is NP-easy; therefore, it can be proven using one of these methods; but previous theorems show it can't be decided using any of those methods, therefore P!=NP." Has this approach been investigated? Neon Merlin 19:54, 26 May 2013 (UTC)[reply]

I'm skeptical that this approach can be made to work (there are a lot of obvious gaps, as I'm sure you've noticed yourself — that doesn't mean they can't be closed, but I'm skeptical). ~~But really this isn't the right place to discuss it. Maybe ask at WP:RD/Math and see if anyone can provide more insight? --Trovatore (talk)~~ 20:31, 26 May 2013 (UTC) Oops, sorry, this was dumb — this is the refdesk. Sorry about that. I thought this was the P=NP page. --Trovatore (talk) 20:53, 26 May 2013 (UTC)[reply]

Green's relations

I am about to write a Bachlor thesis on Green's relations for semigroups.

Unfortunately, Wikipedia and my books only tell me that they are important, but not why. Can somebody help me? I can not see why Green's relations are so useful (like it is stated in the Wikipedia article in the introduction). Don't get me wrong: I do not need any applications "in the real world", but I would like to know why they are so useful. Could someone give me "simple consequences"? And, since my books only tell me something like "If the semigroup has a certain form, then Green's relations do this and this" (and not the other way round): How can Green's relations tell me something about the semigroup, if I need to know the semigroup's properties before? — Preceding unsigned comment added by 83.64.56.34 (talk) 22:00, 26 May 2013 (UTC)[reply]

May 27

Resumed Discussion of Reprised Confusion over Wikipedia Definitions of Sigma Additivity

I have added the following reply to the thread discussing my reprised confusion over Wikipedia definitions of sigma additivity:

Hey, guys; I'm sorry that I haven't replied to this thread even though I know that I should have done so due to the fact that I'm the person who started it, but I've sort of been mulling over exactly how to continue this discussion. I've been having a little trouble figuring out exactly what you said, Straightontillmorning, even though it was easy to understand at first glance. I think that the problem is that I couldn't exactly bring myself to formulate the questions that I wanted to ask you (they were on the tip of my tongue&thinsp–or rather, my fingers, I guess….) Regardless, however, of the trouble that I temporarily had in communicating with you, I think that I'm ready to discuss your comments. First of all, I comprehend that you're trying to tell me that I phrased my statement that 'the definition of sigma additivity can apply to either a probability measure $P$ or a generic measure $μ$ ' incorrectly and should instead have made clear that I then understood that the definition of sigma additivity applies to both probability measures $P$ and general measures $μ$ because the former are defined in terms of the latter, albeit with the extra condition that a probability measure must output a result between 0 and 1. As such, the definitions are, as you said, almost identical. Second of all, are the 'hypotheses' that you list as bullet points below your first paragraphs simply summaries of the conditions applied respectively to each of the definitions that I took from the articles that I referenced? If so, then could you please explain to me what exactly the difference is between a sequence, collection, a set of pairwise disjoint sets, a multiset such as the kind that one must derive from such groups of elements if some of these elements are identical but must not be allowed to collapse into a single, merged element, or an indexed family of sets. Thirdly, I understand that when you mention a 'countable sequence' that you mean that one would use a finite index set to index the sequence in question. Fifth, I get that one may use either any capital letter $A,B,\dots ,Z$ or any subscript attached to the letter 'E' – as in $E_{1},E_{2},E_{3},\dots ,E_{n}$ – to denote an event and either the Greek letter Sigma $Σ$ or a calligraphic letter such as ${\mathcal {A}},{\mathcal {B}},{\mathcal {C}},$ et cetera, to denote a sigma algebra. And, sixth and finally, I find it preposterous that one could equate the arbitrary, but still finite, union used in the first two definitions with the infinite union used in the last definition. I hope that that helps you understand why I'm still a little confused.

Sincerely,

RandomDSdevel (talk) 19:28, 27 May 2013 (UTC)
— RandomDSdevel (talk) 19:34, 27 May 2013 (UTC), Archived post concerning my Reprised Confusion over Wikipedia Definitions of Sigma Additivity

Please respond to it over at the respective archives page.
Thanks in advance,
RandomDSdevel (talk) 19:34, 27 May 2013 (UTC)[reply]

TLDR. May I suggest that your confusion might be more easily resolved by a visit to your local library instead of repeatedly trying to get answers from a reference desk. A standard reference for measure theory is Halmos "Measure theory". A more readable account is Royden "Real analysis". Sławomir Biały (talk) 21:44, 27 May 2013 (UTC)[reply]

May 28

A Number With All Digits Equal Can Never Be A Perfect Square

Why ? :-) I'm not just looking for a solution, but for the simplest possible solution... — 79.113.211.75 (talk) 07:26, 28 May 2013 (UTC)[reply]

hatting removed, OP said "Correct but undesired approach"

Suppose n is an integer such that all the digits of n² are the same, and (obviously) are not all 0. Look at what the final digits of n can be. Examining the last two digits of all the squares from 1^2 to 99^2 shows that n must end in 12, 38, 62 or 88 - the squares of these numbers all end in 44. Now examine the last three digits of the squares of 3-digit numbers that end in 12, 38, 62 or 88. You will find that only four of these numbers have squares whose last 3 digits are the same. So there are only four possibilities for the last 3 digits of n. Next examine the last four digits of the squares of 4-digit numbers that end in any of these four 3-digit possibilities. You will find that none of these squares have their last 4 digits all the same. Since you have eliminated all the possibilities for the last 4 digits of n, you have shown that n does not exist. Gandalf61 (talk) 08:54, 28 May 2013 (UTC)[reply]

This was precisely the approach I was trying to avoid... :-) — 79.113.211.75 (talk) 11:52, 28 May 2013 (UTC)[reply]

Something like Gandalf61's solution is perhaps unavoidable, as the result depends on the number base used. For example, 11111 is a square in base 3. The result is true in base 2, where 11...1 = 2ⁿ - 1 is never a square (excluding the trivial cases) because odd squares are of the form 4k + 1. AndrewWTaylor (talk) 12:18, 28 May 2013 (UTC)[reply]

Indeed - I was just about to point out that the result is base dependent, but you beat me to it ! My example was 1111 and 4444 are both squares in base 7. Gandalf61 (talk) 12:32, 28 May 2013 (UTC)[reply]

I never said that it doesn't depend on the base... Since it's fairly obvious that 11 is a perfect square in all bases of the form b = n² - 1. — 79.113.211.75 (talk) 13:52, 28 May 2013 (UTC)[reply]

A slight simplification (or variant) of Gandalf's proof: if n = 4...44 is a square (the only possibility) then so is n/4 = 1...11 - a contradiction, because no square ends in 11. AndrewWTaylor (talk) 16:09, 28 May 2013 (UTC)[reply]

Simplest solution besides 0 is 1. It is a square with all its digits equal ;-) Dmcq (talk) 09:48, 28 May 2013 (UTC)[reply]

0 and 1 do not have "digits", but "digit". :-) — 79.113.211.75 (talk) 11:52, 28 May 2013 (UTC)[reply]

Well you might like the argument that All horses are the same color whatever about the horses in the Emerald City in Oz. As to this problem what do you think is the first odd number base for which one can't find such a number? Dmcq (talk) 13:31, 28 May 2013 (UTC)[reply]

Probably 5. — 79.113.211.75 (talk) 14:10, 28 May 2013 (UTC)[reply]

End of hatting removed

Would it be easier to rephrase the question as there are no solutions to $10^{n}={\frac {(3k)^{2}}{d}}+1,$ with $n,k\in \mathbb {N} ^{*}$ and $d\in \{1,2,...,9\}$ ? Or would it only complicate things even further ? — 79.113.221.225 (talk) 17:54, 28 May 2013 (UTC)[reply]

How about 4? Or 9? Not to mention 1.—PaulTanenbaum (talk) 18:39, 28 May 2013 (UTC)[reply]

You can fairly easily rule out all d except 3 and 7. For both of these, it's easy to see that 111 divides 10^n-1. This suggests (since 111=3*37) that the modulus 37 might be important (or possibly 37^2). I don't really have anything concrete to say though. Sławomir Biały (talk) 01:09, 29 May 2013 (UTC) (Sorry about the formatting. I'm traveling and so on a mobile.)[reply]

d = 1 → (3k)² + 1 = 10ⁿ → 9 k² = 999...999 → k² = 111...111 → k mod 10 = {1,9}

a) k = 10 m + 1 → k² = 100 m² + 20 m + 1 → The next-to-last digit has to be even. But 1 is not an even number. → Absurd.

b) k = 10 m + 9 = 10 p - 1, where p = m + 1 → k² = 100 p² - 20 p + 1 → The next-to-last digit has to be even. But 1 is not an even number. → Absurd.

d = 2 →

{\tfrac {1}{2}}

(3k)² + 1 = 10ⁿ → 2|k² → 4|k² → 18 k₀² = 999...999 → 2 k₀² = 111...111 → Absurd, since the last digit has to be even, but 1 is not an even number.

d = 3 →

{\tfrac {1}{3}}

(3k)² + 1 = 10ⁿ → 3 k² = 999...999 → k² = 333...333 → 3|k² → 9|k² → 9 k₀² = 333...333 → k₀² =

{\tfrac {111...111}{3}}

→ 3|n → k₀² = 037...037 → Absurd, since no perfect square ends in 7. Perfect squares can end only in 0,1,4,5,6,9.

d = 4 →

{\tfrac {1}{4}}

(3k)² + 1 = 10ⁿ → 2|k → 9 k₀² = 999...999 → k₀² = 111...111 → Absurd, see the case d = 1.

d = 5 →

{\tfrac {1}{5}}

(3k)² + 1 = 10ⁿ → 5|k² → 25|k² → 45 k₀² = 999...999 → 5 k₀² = 111...111 → Absurd, since the last digit has to be either 0 or 5, and 1 is neither.

d = 6 →

{\tfrac {1}{6}}

(3k)² + 1 = 10ⁿ → 2|k² → 4|k² → 6 k₀² = 999...999 → 2 k₀² = 333...333 → Absurd, since the last digit has to be even, but 3 is not an even number.

d = 7 →

{\tfrac {1}{7}}

(3k)² + 1 = 10ⁿ → 7|k² → 49|k² → 63 k₀² = 999...999 → 7 k₀² = 111...111 → Absurd, since it would imply a perfect square ending in 3, see the case d = 3.

d = 8 →

{\tfrac {1}{8}}

(3k)² + 1 = 10ⁿ → 8|k² → 16|k² → 18 k₀² = 999...999 → 2 k₀² = 111...111 → Absurd, since the last digit has to be even, but 1 is not an even number.

d = 9 →

{\tfrac {1}{9}}

(3k)² + 1 = 10ⁿ → k² = 999...999 → 3|k → k₀² = 111...111 → Absurd, see the case d = 1.

79.113.229.253 (talk) 14:43, 29 May 2013 (UTC)[reply]

Resolved

~~Where did the 3 of the 3k in the numerator come from?~~ Sorry yes that's reasonable. Dmcq (talk) 15:12, 29 May 2013 (UTC)[reply]

Where do the k₀ come from?Naraht (talk) 17:42, 29 May 2013 (UTC)[reply]

If x|k then k = x k_o. — 79.113.242.37 (talk) 18:02, 29 May 2013 (UTC)[reply]

Ah, good. There's an easier argument for most of the other cases besides d=3,7. You can rule out 4, 8, and 9, just by dividing k by 2 or 3. d=1, 5 are impossible because 11...1and 55...5 are 3 mod 4. Similarly with 2, 6. Sławomir Biały (talk) 17:51, 29 May 2013 (UTC)[reply]

Is there anything that can be said about the bases where there exists a rep-digit which is a perfect square? Right now we've got 11111 base 3, 1111 base 7, 4444 base 7, and in general 11 base (n^2 -1). Are there bases other than 7 and n^2 -1?Naraht (talk) 19:22, 28 May 2013 (UTC)[reply]

A computer search finds lots of other bases where the repdigit has 2, 3 or 4 digits. For more than 4 digits I have only found 11111 base 3. PrimeHunter (talk) 23:25, 28 May 2013 (UTC)[reply]

I don't think 111 can be a square in any base. The next square after b² = 100_b will be (b + 1)² = 121_b, and 100 < 111 < 121 (... treat base 2 separately ...), so 111 cannot be a square. Gandalf61 (talk) 10:30, 29 May 2013 (UTC)[reply]

Elaborating on that: a string of m+1 1's cannot be an mth power in any base, and there can be only finitely many bases for which a string m+1 k's can be an mth power if k < m. To see this, let t(m, k, b) be a string of m k's in base b. Then if t(m+1,1,b) is an mth power, (b+1) ** m <= t(m+1, 1, b) = b ** m + t(m, 1, b). (b+1) ** m - b ** m = m(b ** (m-1)) + poly(deg = m-2)>(b ** m - 1) / (b - 1) = t(m, 1, b), hence t(m+1, 1, b) is not an mth power. For the case of all digits being k; t(m+1, k, b) = k * t(m+1, 1, b); looking at the prior inequality, for large enough b, the m-1 degree term dominates, hence t(m+1, k, b) cannot be an mth power unless b is small enough.Phoenixia1177 (talk) 16:27, 29 May 2013 (UTC)[reply]

21 21 21 21 is a square base 41, you can get more 4 digit ones like that using Pells equation for

b^{2}+1=2y^{2}

when

{b+1} \over 2

is the digit. Dmcq (talk) 11:41, 29 May 2013 (UTC)[reply]

Right, 111 cannot be a square. Many other digits can produce 3-digit squares. Below are (base, digit) pairs for all 3-digit repdigit squares where the base is below 10000 and the digit is square-free (other solutions can be generated from the listed by multiplying the digit by a square).

(18, 7), (22, 3), (30, 19), (68, 13), (146, 127), (292, 237), (313, 3), (423, 97), (439, 201), (499, 21), (521, 283), (581, 247), (653, 7), (699, 109), (710, 19), (787, 453), (1047, 457), (1353, 763), (1425, 1099), (1660, 741), (1714, 471), (2060, 1141), (2174, 571), (2198, 907), (2272, 57), (2819, 61), (3019, 1101), (3130, 1839), (3445, 1119), (3789, 3199), (4366, 3), (4526, 67), (4611, 13), (4620, 2269), (4624, 1209), (4701, 7), (4788, 2437), (4972, 1533), (5261, 3343), (5421, 367), (5656, 417), (6057, 547), (6106, 4503), (6158, 1963), (6205, 111), (6895, 1929), (6927, 2713), (7163, 4837), (7527, 217), (7627, 2037), (7733, 2623), (9317, 1423), (9353, 523)

The corresponding (base, digit) list for 4-digit squares is far shorter:

(7, 1), (41, 21), (99, 58), (239, 30), (1393, 697), (2943, 943), (8119, 1015)

There are no 5-digit solutions for bases below 10000. PrimeHunter (talk) 23:15, 29 May 2013 (UTC)[reply]

Probably because 111_b =

{\tfrac {b^{3}-1}{b-1}}

= b² + b + 1 is inbetween two consecutive squares: b² and (b + 1)² = b² + 2 b + 1.— 79.113.242.37 (talk) 23:28, 29 May 2013 (UTC)[reply]

May 29

Irrotational points of a vector field

Is there any general technique, in $\mathbb {R} ^{n}$ space, for finding irrotational points of a vector field? I should add that, in the case of my vector field, not all such points need be isolated.--Leon (talk) 07:02, 29 May 2013 (UTC)[reply]

There is a lot of work about detecting singularities of vector fields, a search will yield plenty of papers. You might be able to modify these algorithms for your purpose.--Salix (talk): 15:16, 29 May 2013 (UTC)[reply]

May 30

Generalized totient function

Is there such a thing as a generalized totient function? Specifically, a function φ_i(n) that is the count of positive integers less than n with exactly i prime divisors. This means that Euler's totient function φ(n) is φ₁(n) in the more general form (i.e., it is the number of positive integers less than n with only one prime divisor). Likewise, φ₂(n) is the number of positive composite integers less than n with only two prime divisors, e.g., numbers from the set {4,6,9,10,14,15,21,22,25,...,n}, which includes all the squares of primes. φ₃(n) includes {8,12,18,27,28,30,...,n}, and so forth. I dimly recall seeing something about Ramanujan studying something similar to this(?). Perhaps such a thing might also be related to the Riemann hypothesis? — Loadmaster (talk) 17:24, 30 May 2013 (UTC)[reply]

Do you mean prime counting function rather than totient function? Otherwise I'm very confused. Sławomir Biały (talk) 17:29, 30 May 2013 (UTC)[reply]

Yes, that's what I meant. So (replacing φ above with π): Is there such a thing as a generalized prime counting function? Specifically, a function π_i(n) that is the count of positive integers less than n with exactly i prime divisors. — Loadmaster (talk) 18:48, 30 May 2013 (UTC)[reply]

Yes, but these can be expressed in terms of the functions pi[n^(1/i)] using Mobius inversion. Count Iblis (talk) 19:54, 30 May 2013 (UTC)[reply]

Elliptic integrals and Gaussian integrals

With your help, I would like to find out a mathematical relationship between complete elliptic integrals of the first kind

K(n)\ =\ \int _{0}^{\pi  \over 2}{\frac {d\theta }{\sqrt {1-n^{2}\sin ^{2}\theta }}}\ =\ \int _{0}^{1}{\frac {dt}{\sqrt {(1-t^{2})(1-n^{2}t^{2})}}}

and gaussian integrals

G(n)\ =\ \int _{0}^{\infty }{e^{-x^{n}}}dx

all of which are known to possess the following property

{\frac {G(m)\cdot G(n)}{G({m\ \cdot \ n \over m\ +\ n})}}\ =\ \int _{0}^{1}{\sqrt[{m}]{1-x^{n}}}dx\ =\ \int _{0}^{1}{\sqrt[{n}]{1-x^{m}}}dx

where

{\tfrac {m\ n}{m+n}}

is half of the harmonic mean between m and n, and the entire above expression is equal to the product between 1 +

{\tfrac {1}{m}}

+

{\tfrac {1}{n}}

and the beta function of arguments 1 +

{\tfrac {1}{m}}

and 1 +

{\tfrac {1}{n}}

.

It also goes on without saying that the factorial of every positive number is the gaussian integral of its reciprocal or multiplicative inverse

n!\ =\ G({\tfrac {1}{n}})\ =\ \int _{0}^{\infty }{e^{-{\sqrt[{n}]{x}}}}dx

— 79.118.171.165 (talk) 18:33, 30 May 2013 (UTC)[reply]

May 31

Linear independence of partial derivatives

Consider the general solution y(x,c₁,c₂) of a 2nd-order linear homogeneous ODE, where c₁ and c₂ are two parameters, and y is assumed smooth in x, c₁, and c₂. Consider the partial derivatives

{\frac {\partial y}{\partial c_{1}}}(x,c_{1},c_{2}),\quad {\frac {\partial y}{\partial c_{2}}}(x,c_{1},c_{2})

Now fix some (c₁,c₂) = (k₁,k₂). Is is true that the functions of x defined by

u_{1}(x)={\frac {\partial y}{\partial c_{1}}}(x,k_{1},k_{2}),\quad u_{2}(x)={\frac {\partial y}{\partial c_{2}}}(x,k_{1},k_{2})

are linearly independent? If not, what extra assumptions are necessary? Does it depend on the choice of (k₁,k₂), and if so, in what way? Thanks for any help. —Anonymous Dissident^Talk 00:40, 31 May 2013 (UTC)[reply]

A condition is clearly needed to ensure that c1 and c2 are independendent parameters (they could otherwise be the same parameter, for instance). Then the answer would presumably be yes, just by definition of independence of the parameters. Sławomir Biały (talk) 13:22, 31 May 2013 (UTC)[reply]

Two questions related to sphere packing...

These are both questions just to start getting my head around sphere packing.

Let A and B both be n dimensional balls. Color any point on the surface of A if it is between the center of A and any point of B. For dimension n, What fraction of the surface of A is colored. (The answer for 2 dimensions is exactly 1/6.
Let A be an n dimensional ball and let B₁, B₂, ...B_n additional n dimensional balls with the centers making an n-dimensional simplex. Mark the n points (p_n on the surface of A where the lines from the center of A to B_i touch the surface of A. Now connect all p_n the "short way" round to get a n-1 dimensional simplex on the surface of A. Color the surface inside A if it is between the center of A and any point in any of the B_i. For each dimension n, what fraction of the area of the triangle is *uncolored*.

For the three dimensional version of this, the first question is what percentage of the surface area of the sphere is "covered" by a touching sphere. The second question is if you have three spheres all touching each other and the main sphere, how much of a "hole" is there between them.Naraht (talk) 00:41, 31 May 2013 (UTC)[reply]

Borsuk's question

In recent edits two anonymous users added an information about new bound for the Borsuk's problem [1]. However it is not clear from the linked abstract, that the claimed bound is true: is says 'We found a two-distance set consisting of 416 points on the unit sphere in the dimension 65 which cannot be partitioned into 83 parts of smaller diameter. This also reduces the smallest dimension in which Borsuk's conjecture is known to be false.', however the Borsuk's question concerns dividing sets in d–space into $(d+1)$ parts. Bondarenko says his set can not be partitioned into 83 subsets, but that does not obviously imply it can't be partitioned into 66 subsets of required size.

Additionally he says 'This reduces the smallest dimension...', but it's not clear in what manner it reduces that dimension (possibly the two dimensions mentioned are related somehow, but not necessarily equal). Anybody has access to the full text, and can verify the 65 is an actual new limit for Borsuk's question, please? --CiaPan (talk) 06:24, 31 May 2013 (UTC)[reply]

Is it correct to equate the 2nd equation?

Consider the following two equations-
A) 2^x * 2^y = 2² * 2⁴ From this equation, we can simply write x = 2 and y = 4.
B) 2^x + 2^y = 2² + 2⁴ From this equation, can I write x = 2 and y = 4?
I know, I am right for my 1st equation, here, I just equated LHS to RHS. In the second case also I did the same thing, but I am not sure whether I am right or wrong. So, correct me if I am wrong. Scientist456 (talk) 15:57, 31 May 2013 (UTC)[reply]

x=2 and y=4 are *one* solution to the second equation, but they are by no means the only ones. An additional answer to both equations is x=4 and y=2. For the first you can also have x=3 and y=3 (and x=1, y=5, etc.). The second is harder to come up with alternative integer solutions to, but there are plenty of non-integer solutions, e.g. x=3 and ~~y=ln(2.5)/ln(2)~~ y=ln(12)/ln(2) (correct thinko). To be equal, the two sides have to be the same, either before or after algebraic manipulation. If you substitute x=2 and y=4 in both equations, you'll end up with a true statement (both sides are the same), but that can also happen with a number of other values for x and y. -- 71.35.97.37 (talk) 16:13, 31 May 2013 (UTC)[reply]

Actually, I was confused in this problem- 3^x + 7^y = 3² + 7⁴
I had to find the value of x and y. Here, can I write x = 2 and y = 4 by equating LHS to RHS. Scientist456 (talk) 17:04, 31 May 2013 (UTC)[reply]

Did you make up this problem or does it come from some source? If it comes from some source, there is a high probability that you have left out important information. Looie496 (talk) 17:14, 31 May 2013 (UTC)[reply]

There are an infinite number of possible solutions to both equations, unless perhaps you are restricted to integers only, but even so, there's likely no single solution. For example, if x=0 in the second equation, then y=log₇2409.--Jasper Deng (talk) 17:18, 31 May 2013 (UTC)[reply]

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]

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]