Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

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.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

February 5

Nash equilibrium when blocking each other the way

A corridor is so narrow that only two people can walk along it side by side. Either you are at the left or you are at the right. If I, being on the right, bump into someone, should I step left? Should the other person step to his right? We prefer to walk straight along the corridor, but our main goal is obviously to go through it. Is here a Nash equilibrium?

Have similar problems to this (with the same metaphors) been treated by math? --Llaanngg (talk) 19:03, 5 February 2017 (UTC)

I think you are describing the Nash_equilibrium#Coordination_game. -- SGBailey (talk) 19:47, 5 February 2017 (UTC)

Walking in the middle isn't really an option since neither person gets through, so the choices are walking on the left or on the right. This is the same as the Driving game variation listed in the linked section. According to the article there are actually three Nash equilibria. I think the confusion is from the fact that in a Nash equilibrium each player knows what the other player's strategy is, while in the narrow corridor scenario that's seems unrealistic. For cars, which side of the road you drive on is determined by custom and law, so you can assume what the other player's strategy is and avoid a crash. A similar game occurs when cars meet at a stop sign and one must yield right of way. Drivers are supposed to memorize rules for who is supposed to yield so player's strategies are known and collisions are avoided. But in a corridor it's possible that no such assumption can be made. In that case the consequences of a collision are far less serious though. The strategy would be to pick a side at random and in the 50% of cases you get stuck, pick a new side at random and keep trying until you get through. In real life, players can communicate, even if it's by gestures, to coordinate their moves.

A similar game takes place in the story of Robin Hood and Little John where they meet on a narrow bridge. Each player has the option to yield or stand and fight if necessary. In the story, both players choose to stand and fight, but presumably the payoff matrix is different so it's not clear whether that would be the equilibrium strategy; perhaps yielding would be taken as a sign of cowardice, so it would be preferable to fighting and losing. Also, in that case the fighting abilities of the other player can only be guessed, so the players may have different ideas as to what the actual payoff matrix actually is. --RDBury (talk) 22:02, 5 February 2017 (UTC)

It isn't quite the "coordination game", but the game theory analysis is easy. There are two Nash equilbria: (1) both players stay to their left, (2) both players stay to their right. In the classic coordination game one of these strategies is superior for both players even though both are Nash equilibria, but in this version both strategies yield identical results. Looie496 (talk) 23:00, 5 February 2017 (UTC)

There is a third, mixed, equilibrium. -- Meni Rosenfeld (talk) 21:22, 7 February 2017 (UTC)

February 7

Puzzle degrees of Freedom question

Assume an octahedral puzzle. It has two modes. In one mode, the two halves of the puzzle may be rotated by each other on any of the three planes that connect four points through the center. They can rotate either 1/4, 1/2 or 3/4 turns relative to each other. (Sort of like a Rubix cube with rotational axes through the points.) In the other mode, each of the faces of the Octahedron rotate, with each face rotating in the opposite direction from the faces that it borders on an edge. This can rotate either 1/3 turn clockwise or counterclockwise. If the puzzle is taken apart and reassembled, the number of possible positions that it can have (for this purpose, orienting face A and its corners in the same position as the start is 7!*3^7 (the 7 possible positions for the other triangular faces times the orientations of those faces). Of those positions, how many can actually be achieved simply using the proper moves of the toy?Naraht (talk) 02:57, 7 February 2017 (UTC)

I don't think the turning of all the faces by 1/3 gives any extra moves, if so the puzzle is completely equivalent to the Pocket Cube with the corners mapped to the center of the sides,, so 7!*3^6 possibilities. Dmcq (talk) 11:57, 7 February 2017 (UTC)

Agreed, without the face rotation, it would be equivalent to the Pocket Cube, but I don't understand why the exponent is 6 in the 3^6. All of the other 7 should be independent, right?Naraht (talk) 17:43, 7 February 2017 (UTC)

Even with the gear type face rotation it is equivalent to the Pocket Cube. That move can be generated using a sequence of the first type of rotations. The rotations of the faces are not completely independent, the eight is determined by the other seven. Dmcq (talk) 18:14, 7 February 2017 (UTC)

What is the series of mode 1 moves equivalent to a mode 2 rotation? And how do you show that the 8th is determined by the other 7?Naraht (talk) 21:13, 8 February 2017 (UTC)

If you could twist all the faces in the same direction you'd get another factor of three. Dmcq (talk) 12:09, 7 February 2017 (UTC)

Yes, but that's not one of the modes. In mode 2, 4 faces turn clockwise and 4 faces turn counterclockwise. (think replacing the sides with gears)Naraht (talk) 17:43, 7 February 2017 (UTC)

February 9

Question 11

How do I go about proving (11) here? The problem says:

If a is a constant and A an n×n square matrix, then

|aA| = aⁿ |A|

I wrote the general matrix out like so:

$\mathbf {A} ={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{bmatrix}}$

However, I wasn't sure how to proceed from here. I already wrote out the 2×2 and 3×3 cases, I just wasn't sure how to prove the general case shown above. 147.126.10.21 (talk) 04:00, 8 February 2017 (UTC)

There are several approaches, depending on what properties of the determinant you can assume. Here are three possibilities:

1. Start with the Leibniz formula for determinants and note that the determinant of a nxn matrix is a polynomial in which each term is the product of n matrix elements.
2. Start from the property that the determinant of a nxn matrix is the product of its n eigenvalues. How are the eigenvalues of aA related to the eigenvalues of A ?
3. Start from the Laplace expansion which expresses the determinant of a nxn matrix as the weighted sum of the determinants of certain n-1 x n-1 sub-matrices. This allows a proof by induction.

Gandalf61 (talk) 09:31, 8 February 2017 (UTC)

Also, the questioner should be aware that his explicit statement of the matrix A shows it to be m×n, but the determinant is only defined if m=n. Loraof (talk) 18:28, 8 February 2017 (UTC)

Is the last line a typo?

[1] Isn't this a scalar function even when applied to a vector field? Thank you. 69.22.242.15 (talk) 04:19, 9 February 2017 (UTC)

No. $\nabla ^{2}P$, $\nabla ^{2}Q$, and $\nabla ^{2}R$ are individually scalar functions of $(x,y,z)$. $\nabla ^{2}\,{\mathbf {F} }=\nabla ^{2}P\,{\mathbf {i} }+\nabla ^{2}Q\,{\mathbf {j} }+\nabla ^{2}R\,{\mathbf {k} }$ is a vector-valued function. --100.34.204.4 (talk) 05:54, 9 February 2017 (UTC)

In that case the result of div can be either scalar or vector, so we can't say that it produces a scalar or vector field without specifying its input? Also, div <P,Q,R> = Px +Qy + Rz so how is that a vector? 69.22.242.15 (talk) 13:01, 9 February 2017 (UTC)

Divergence is defined on a vector field. I don't think it's meaningful to talk about the divergence of a scalar field.

As an operator, $\nabla ={\frac {\partial }{\partial x}}{\mathbf {i} }+{\frac {\partial }{\partial y}}{\mathbf {j} }+{\frac {\partial }{\partial z}}{\mathbf {k} }$, so $\nabla ^{2}=({\frac {\partial ^{2}}{\partial x^{2}}},{\frac {\partial ^{2}}{\partial y^{2}}},{\frac {\partial ^{2}}{\partial z^{2}}})$, which is a vector-valued function.

Applying the latter to ${\mathbf {F} }$, where ${\mathbf {F} }=P\,{\mathbf {i} }+Q\,{\mathbf {j} }+R\,{\mathbf {k} }$ and $P$, $Q$, $R$ are scalar functions of $(x,y,z)$, we have $\nabla ^{2}{\mathbf {F} }={\frac {\partial ^{2}P}{\partial x^{2}}}{\mathbf {i} }+{\frac {\partial ^{2}Q}{\partial y^{2}}}{\mathbf {j} }+{\frac {\partial ^{2}R}{\partial z^{2}}}{\mathbf {k} }$, which is quite obviously vector-valued.

$\operatorname {div} {\mathbf {F} }$ is indeed a scalar field, but $\operatorname {div} {\mathbf {F} }$ is not the same as $\nabla ^{2}\,{\mathbf {F} }$. --100.34.204.4 (talk) 22:44, 9 February 2017 (UTC)

n⁴ divides Central binomial coefficient

What is the smallest non-trivial solution (i.e., n > 1) to n⁴ dividing Binomial (2n, n) ? All I know is that n > 10⁷. This is related to these three integer sequences. — 86.125.207.71 (talk) 08:20, 9 February 2017 (UTC)

I suspect there is none. Someone may have a more rigorous proof, but, first you need only consider primes, as if n composite is a solution then its prime factors are. And for any prime p I can’t see how you can have four (or more) of them on top of the fraction ${\frac {(2n)!}{(n!)^{2}}}.$. You can write out the factors on the top and bottom and in each case it’s just lists of numbers. (1 × 2 × 3 ... 2n) / ((1 × 2 × 3 ... n) × (1 × 2 × 3 ... n)). Any prime appears about as often in the numerator and denominator.--JohnBlackburne^words_deeds 09:00, 9 February 2017 (UTC)

I'm not convinced. If valid, why would that argument not work for n³ | Binomial (2n, n)? There seems to be an infinite number of solutions in that case. (See the first linked oeis sequence.) The programs listed to generate the oeis sequences just use a brute force search, but you could probably find an upper bound on the highest prime factor of n that might narrow the search a bit. --RDBury (talk) 09:17, 9 February 2017 (UTC)

PS. If you look at the graphs of the other sequences they seem fairly linear. So heuristically you could argue that the probability of an integer being in the sequence is constant. For n | Binomial (2n, n) the probability seems to be about 1/9, For n² | Binomial (2n, n) about 1/600, and for n³ | Binomial (2n, n) about 1/200000. Assuming that n⁴ | Binomial (2n, n) keeps to the same pattern then its probability would be very low, say 1 in a billion, but still >0. So you wouldn't expect searching up would 10⁷ produce any solutions, but searching up to 10¹⁰ might. --RDBury (talk) 09:51, 9 February 2017 (UTC)

As can be quite easily glimpsed from the linked articles, the first non-trivial solutions to Binomial(2n,n) being divisible by n^k (for k = 1, 2, 3) are 2, 924, 154836. Therefore, I deem it rather reasonable to expect a first solution for k = 4 somewhere in between n = 10⁷ and n = 10⁸. — 86.125.207.71 (talk) 10:56, 9 February 2017 (UTC)

• if n composite is a solution then its prime factors are - hmm, no. Actually, you have written the reason: it is fairly simple to see that no prime number verifies the OP's property: for prime p>2, p never divides ${2p \choose p}$, much less to the power 4; but it is not the case for composite numbers (e.g. 6^2=36 divides ${12 \choose 6}=252$ because there are enough 2s and 3s in the list). Tigraan^{Click here to contact me} 12:10, 9 February 2017 (UTC)

Make that "for prime $p>2$". $p=2$ is special because $2p$ happens to be $p^{2}$. -- Meni Rosenfeld (talk) 12:36, 9 February 2017 (UTC)

• Here's a thought. Using the p-adic valuation theory, in particular Legendre's formula, $v_{p}\left({2N \choose N}\right)=v_{p}((2N)!)-2v_{p}(N!)=\sum _{i=1}^{\infty }\left\lfloor {\frac {2N}{p^{i}}}\right\rfloor -2\left\lfloor {\frac {N}{p^{i}}}\right\rfloor \leq \log _{p}(N)+1$ (the inequality comes from counting the number of nonzero terms in the sum). On the other hand, $v_{p}\left(N^{k}\right)=kv_{p}(N)$.

Now, this does not give possible solutions, because $\sum \left\lfloor {\frac {2N}{p^{i}}}\right\rfloor -2\left\lfloor {\frac {N}{p^{i}}}\right\rfloor$ may well be 0 even for large N. However, it proves that some numbers are not solutions: for instance, p^m (with p prime) will never work, because the p-adic order of the binomial coefficient will be at most m+1 whereas that of n^k will be km (>m+1 for k>1, m>1). (The OP's case is k=4)

Moreover, if you want to run a computer test, it is certainly waaay faster to test it this way than actually computing the binomial coefficients. Decompose N in prime factors, compute the p-adic valuation of the binomial coefficient for all prime factors (from simple division / rounding operations of the formula above), compare. I have the feeling that the best candidates are numbers of the form 2*3*5*7*... but I cannot prove it. Tigraan^{Click here to contact me} 12:41, 9 February 2017 (UTC)

Uncomputable numbers and randomized algorithms

I think(!) that I dimly understand all the component terms of the headline. My question: is it possible for a number to be uncomputable (no algorithm can find the nth digit of its decimal, or otherwise, expansion) but for there to be a randomized algorithm that converges to said number almost surely?--Leon (talk) 22:44, 9 February 2017 (UTC)