Wikipedia:Reference desk/Archives/Mathematics/2014 October 25

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.

October 25

Number of possible positions of X-puzzle

In the article 15 puzzle it's said that : The number of possible positions of the 24-puzzle is 25!/2 ≈ 7.76×10²⁴. I don't understand why we divided 25! (the number of the possible combinations) by two. Thanks. — Preceding unsigned comment added by Hunsu (talk • contribs) 14:00, 25 October 2014 (UTC)

It mentions earlier that half of the positions cannot be resolved, thus the puzzle cannot be in any of those states, hence, the division by 2.Phoenixia1177 (talk) 15:11, 25 October 2014 (UTC)

At Phoenixia1177 (talk · contribs): Why the puzzle can't be in any of those states? I can imagine that there's a way from A (initial state) that arrive at B (state that can't be resolved). So how to prove that there's not a such way? Hunsu (talk) 19:53, 25 October 2014 (UTC)

But you can't imagine that, or, at least, not consistently - "can be resolved is transitive" so if state A can be resolved, then any sequence of moves from A leads to another state that can be resolved. The reason for this is, as follows, suppose A can be resolved and B cannot, then if there is a sequence of moves A -> B, that means that we cannot solve the puzzle from B; however, by reversing the moves we have B -> A, from which it can be solved. It cannot be that we can solve and not solve the puzzle from B, thus there can be no A -> B using valid moves. Thus, since we can never reach an unresolvable state, exactly half the states cannot be reached.Phoenixia1177 (talk) 05:19, 26 October 2014 (UTC)

As for how we prove it, there's an invariant. Take the parity of the empty tile's L1-norm and add the parity of the permutation. If you're familiar with these concepts, it's easy to check that this is an invariant. Since half the states have 0 and half have 1, only half be achieved.--80.109.80.31 (talk) 09:00, 26 October 2014 (UTC)

DIY: prove or disprove, that the 3-tile 2×2-puzzle's position

1	3
2

can be transformed into

1	2
3

You can do that simply by inspection of all possible tile shifts. --CiaPan (talk) 12:18, 28 October 2014 (UTC)

Is the following proof of the Collatz Conjecture correct?

Introduction: The Collatz Conjecture (also known as the 3n+1 Conjecture or the Ulam’s Problem) states that if we start with any positive integer, n, and compute n/2 if n is even, or 3n+1 if n is odd, and processing the new number the same way, the process will eventually generate one. For example, we observe the result of the Collatz process in the following sequence, S’. S7 = {7, 22,11, 34, 17, 52, 26, 13, 40 ,20, 10, 5, 16, 8, 4, 2, 1}.

Proof of the Collatz Conjecture: Suppose there exists a sequence, S’={n0, n1, n2, …} that does not converge to one, or nk ≠ 1 or nsub(k-r) ≠ 2^µ over S’ for all kϵ ℕ where r <k, and r, k, and µ are nonnegative integers, according to the Collatz process.

The Algorithmic Process: From a given positive integer, n, we obtain the maximum positive odd integer, n0 > 7, by repeated division of n by 2. Let n1 = 3n0 + 1 which is a multiple of 2. Therefore, Probability(n1 is a multiple of 2) =1; Probability(n1 is a multiple of 2^2 | n1 is a multiple of 2 ) = 1/2; Probability(n1 is a multiple of 2^3 | n1 is a multiple of 2^2 ) = 1/2; … ; Probability(n1 is a multiple of 2^l1 | n1 is a multiple of 2^(l1-1) ) = 1/2 where l1 = Floor[ln(n1)/ln(2)].

Note: Probability(n1 is a multiple of 2^3)= Probability(n1 is a multiple of 2^3 | n1 is a multiple of 2^2) * Probability(n1 is a multiple of 2^2)= (1/2)*(1/2)=(1/2)^2

Therefore, we have the Probability(n1 is at least a multiple of 2^2) = Sum[i=0 to l1 – 1, of (1/2)i+1].

Note: Sum[i =0 to ∞, of (1/2)^(i+1)] = 1.

Note: nk = 2^d * odd integer, where odd integer is greater than one for some nonnegative integer, d. Thus, the size of the odd integer varies inversely to size of 2^d. So, if d approaches infinity, the odd integer approaches one. This is forbidden, and thus, the elements of S’ are not allowed to grow without bound.

Next, we compute the partial sequence from n1 to nsub(2+l1) given n0 of S’: n0, n1 = 3n0 + 1, , n2 = n1/2, n3= n1/2^2, …, nsub(1+l1) = n1/2^l1, nsub(2+l1) = 3*(n1/2^l1) + 1 = 3*((3n0 + 1)/2^l1) + 1 = (3^2*n0 + 3)/2^l1 + 1…

Therefore, the Probability(S’ does converge to 1) = 1 - Probability(S’ does not converge to 1) → 1 where

Probability(S’ does not converge to 1) = Product[m=1 to ∞ of Sum(i=0 to lm - 1, of (1/2)^(i+1)] → 0 where lm = Floor[ ln(nsub(m + l1 + l2 + … + lm-1))/ln(2) ] < ∞ and where

Note: nsub(m + l1 + l2 + … + lm-1)= (3^m*n0 + 3^(m-1))/2^(l1 + l2 + … + lm-1) + 1.

Note: l0 = lsub(0) = 0;

So, the expected value S’ converging to 1 from n0 is E[S’ converging to 1 from n0] = n0 * Probability(S’ does converge to 1) → n0.

Note: 'sub' indicates an index of a variable.

Thus, the Collatz Conjecture is true. Thank God! Praise God!

Primesdegold (talk) 18:24, 25 October 2014 (UTC)--David Cole, primesdor@gmail.com

Are you actually here to contribute to this encyclopedia, or is your goal simply to repeatedly flood this reference desk and article talk pages with your ill-conceived original research? --Kinu ^t/_c 18:38, 25 October 2014 (UTC)

To be perfectly blunt, you cannot keep posting bad proofs here - and, at any rate, this is not the venue for proofs, or for their checking. Being an amateur mathematician, myself, I always enjoy helping out another (and I've spent a little time on each of the conjectures you've posted on), if you'd be willing to write in a slightly cleaner, more readable, fashion, you can feel free to post these on my talk page (or I can give you my email - the one listed on my account is one I don't remember). I'd be happy to go through as many as you want and give you what suggestions I can, though my schedule is a little hectic at times. Elsewise, best of luck in your endeavours:-)Phoenixia1177 (talk) 05:29, 26 October 2014 (UTC)

If you continue posting bad proofs to the Reference Desk (and your bad proofs have been your only posts except for an equally out-of-place theory on a talk page), you are likely to be blocked from editing. You appear to be either a troll or a crank. Altering the text of your alleged proofs after posting them is not appropriate either. At the Reference Desk, we are very tolerant of eccentric posting compared to elsewhere in Wikipedia, but there are limits to our patience. Do you really want to be banned? Robert McClenon (talk) 19:14, 26 October 2014 (UTC)

Based on the commentary at all of the threads started by this user, there appears to be consensus that allowing this editor to continue to post on Wikipedia is of no benefit to this project; he appears to be abusing this reference desk (as well as Talk:Artificial intelligence) as his own soapbox for his original research. For what it's worth, it appears that he's done it before on other sites. I have therefore blocked indefinitely. --Kinu ^t/_c 19:37, 26 October 2014 (UTC)

probability/expected value question

Suppose a car buyer goes to a dealer and rejects an offer with probability P (or accepts it with probability 1-P). Suppose the likelihood of rejection is multiplied by a factor of Z percent each time. So, at the next dealer he rejects it with probability PZ (or accepts it with probability 1-PZ). At the third dealer, he rejects it with probability PZ^2, and so on such that he rejects the offer at dealer N with probability PZ^(N-1)

What's the expected value of how many dealers the buyer visits before buying a car?

I got a series that looks like this:

call x=1-p

S_n = (1-xZ^n)*sum(S_n,0,n-1)

but I have no idea how to take the expected value of that. — Preceding unsigned comment added by 66.108.239.137 (talk) 21:12, 25 October 2014 (UTC)

Let's write the expected value out, just for clarity. I'm going to use r for the initial rejection probability.

The probability of going to (at least) a first dealer is 1

The probability of going to (at least) a second dealer is r

The probability of going to (at least) a third dealer is r × rz

The probability of going to (at least) a fourth dealer is (r × rz) × rz²

... etc

So the expected value = 1 + r + r²z + r³z³ + r⁴z⁶ + r⁵z¹⁰ ...

which also equals 1 + r { 1 + rz + (rz)²z + (rz)³z³ + (rz)⁴z⁶ + (rz)⁵z¹⁰ ... }

so we can write that s(r, z) = 1 + r s(rz, z)

And now I'll hand over to wiser heads to see if they know of a way that that can be summed. Jheald (talk) 07:56, 26 October 2014 (UTC)