Wikipedia:Reference desk/Archives/Mathematics/2013 September 4

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.

September 4

Showing equivalence of problems

Show that

$\min _{x\in \mathbb {R} ^{n}}\sup _{u\in \mathbb {R} ^{n}}{\frac {u^{T}(A_{0}+x_{1}A_{1}+\cdots +x_{n}A_{n})u}{(a^{T}x+b)u^{T}u}}$

is equivalent to the complex optimization problem

$\min _{y\in \mathbb {R} ^{n},s\in \mathbb {R} }\sup _{u\in \mathbb {R} ^{n}}{\frac {u^{T}(sA_{0}+y_{1}A_{1}+\cdots +y_{n}A_{n})u}{u^{T}u}}$ subject to $a^{T}y+bs=1$ and $s\geq 0$.

AnalysisAlgebra (talk) 00:59, 4 September 2013 (UTC)

You obviously make the substitution $y={\frac {x}{a^{T}x+b}}$. It follows that $s={\frac {1}{a^{T}x+b}}$ from the constraint and then the two expressions are clearly the same. --Widener (talk) 07:59, 4 September 2013 (UTC)

How many neighboring differences among the 10 digit scrambles of 0123456789

Let A be an ordered list of the 10! ten digit numbers which can be made out of all ten digits (including those starting with zero) so 0123456789, 0123456798, 0123456879, 0123456897, ... 9876543102 ,9876543120, 9876543201, 9876543210. Let B be the list of 10!-1 differences between each neighboring entries (9, 81, 18, ... 18 ,81, 9). How many distinct values are there in B and what is the smallest multiple of 9 that does not occur in B. ( I wouldn't be shocked if someone told me this was problem B-1 on the 1973 Putnam, or something like that, if feels very Putnam A-1/B-1) — Preceding unsigned comment added by Naraht (talk • contribs) 15:04, 4 September 2013 (UTC)

Brute force: there are 500 distinct values in B, and 90 is the smallest multiple of 9 that does not occur in B. Someone else can probably prove this without a computer program. 68.0.135.117 (talk) 19:55, 4 September 2013 (UTC)

It may not be quite as bad as it seems, for example 9 occurs 9! times. In every second difference the permutation changes only in the last two digits, this generates differences 9i for i from 1 to 9. In two out of three of the remaining difference the permutation changes in the last three digits, this generates 9(i+11j) with i+j=9. In three out of four of the remaining differences the permutation changes in the last four digits but now the computation starts to get complicated. In general you need to take all 2¹⁰ possible subsets of {0,...,9}, {2,4,5,7,9} for example, and compute differences like 52479-49752, k-1 differences for a set of size k. Wlog you can assume 0 is in the set so that gives only 2⁹ different sets, still not a hand calculation but more tractable than going through 10! permutations. I guess the next thing to try is computing it for base 2-6 and plugging the results into OEIS. --RDBury (talk) 21:33, 4 September 2013 (UTC)

1, 3, 8, 18, 38, 74, 143, 500..., which is not in OEIS. 68.0.135.117 (talk) 00:41, 5 September 2013 (UTC)

It appears you always interpret the string as a base-10 number. With that interpretation I get your sequence, except you forgot 271 between 143 and 500. If we only use b digits then it seems more natural to interpret it as a base b number. There I get 1, 2, 6, 15, 34, 70, 139, 267, 500. None of the sequences are in OEIS. PrimeHunter (talk) 01:28, 5 September 2013 (UTC)

How did people brute force it and does anyone have a directly calculable way? I agree it makes more sense to consider the 012345 as a base 6 for the sequence. (I'm still thinking it could end up as a Putnam. :) )

Also, the more I consider the question of the smallest multiple of 9 not in B, the clearer it becomes that 90 is correct, for every multiple of 9 below that (say 9*k), you can choose two digits which are k apart and take two numbers with those digits being traded at the end, so if you want a difference of 54, you can choose 1 & 7 so 9865432017 and 986543071 are 54 apart.Naraht (talk) 14:47, 6 September 2013 (UTC)

Right. And I don't see it explicitly stated above, but the reason that 90 is not in B is that the last digit always changes when generating all possible permutations in lexicographic order, so no multiple of 10 is in B. -- ToE 12:06, 7 September 2013 (UTC)