April 2016 - mathfun@mailman.xmission.com

[math-fun] A problem about finite sets
by Victor Miller 10 Sep '16

10 Sep '16

Say that a finite set of integers, A, has *property P* is there are two non-empty disjoint subsets S and T of A, such that sum(S) = sum(T) (where sum(X) is the sum of the elements of X). 1) Show that every 10 element subset of {1,...,100} has property P (this is fairly easy). 2) Is it true that every 9 element subset of {1,...,100} has property P? Victor

8 9

Re: [math-fun] Raghavendra's algorithm for solving linear systems over finite fields
by Henry Baker 06 Jun '16

06 Jun '16

I can see applications in distributed/parallel implementations. You can do most of the checking & probably a lot of the randomization in parallel. At 09:02 AM 8/15/2012, Warren Smith wrote: >>Preliminary draft: >> http://www.eecs.berkeley.edu/~prasad/linsystems.pdf > >--I don't understand why anybody would want to use this algorithm >for any purpose. It's slower than everything else I can think of and also >randomized i.e. can fail. > >However... perhaps it might be useful if changed to be about finite >RINGS not fields. In rings, you cannot divide, hence gaussian elimination is >not usable. Hence this algorithm then has less competition. >(Even then I'm dubious, but then it'd have at least a hope.)

8 9

[math-fun] 473-gene "artificial bactierium"
by Warren D Smith 12 May '16

12 May '16

Venter et al made their long-awaited "artificial bacterium" (actually synthetic DNA that they managed to get inside a bacterium to "boot up" a wholy artificial design for living being, which of course was based on 473 known natural genes). They think or hope that 473 is near minimum possible. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

6 9

[math-fun] 5 and 7 outcome fair dice
by Bill Gosper 06 May '16

06 May '16

Odd barrel dice have the problem that two faces are always uppermost, so how do you label them? Alternative to face-transitivity, there are fair dice which cannot rest on any face, and yet have one face uppermost. Spoiler: gosper.org/5&7dice.png --rwg I assume these are old ideas. Check out Wikipedia if you haven't seen spherical, 6 outcome dice.

4 3

Re: [math-fun] Lasker
by Bill Gosper 06 May '16

06 May '16

On 2016-04-08 14:39, Warren D Smith wrote: > Macaulay's book gave a star role to the amazing theorem of Lasker, > also mentioned here > > https://en.wikipedia.org/wiki/Primary_decomposition > > It is due to Emanuel Lasker, world chess champion 1894-1921, > which I think made him the longest-reigning world champ. > So, I had not realized this, but Lasker also made a lasting contribution > to mathematics. > >From http://exeterchessclub.org.uk/content/chess-stories Lasker incognitoLasker often used to play without letting on who he was: he had fun at the expense of one poor chap who managed always to win against his mystery opponent when he gave knight odds, but lost when he had the extra knight! Probably apocryphal (Hans?), but the story I heard was that, en route to his 1921 Havana defeat, a fellow passenger found him analyzing a position and, unsuspecting, introduced himself as president of his local chess club. And then beat Lasker in game. "This piece here, how do you call it?" "The queen." "Do you mind if I play without it? It is impairing my mobility." [You can guess the rest.] --rwg

5 6

Re: [math-fun] Rot13 and other substitution ciphers (was Re: Quickies)
by Jim Gillogly 06 May '16

06 May '16

Keith F. Lynch writes: > The longest words that remain words after being rot13'd are > Chechen <-> Purpura. Checking my unabridged, I see another cromulent pair at 7: nowhere <-> abjurer They also have the advantage of being usable for Scrabble. -- Jim Gillogly

5 4

[math-fun] Yet another irritating elementary geometry puzzle
by Fred Lunnon 04 May '16

04 May '16

I finally wrote up properly all the stuff I've been doing about inspheres and exspheres of a simplex. Finished. Done & dusted. Off my plate. But as I sat down again to start writing up P*nc*l*t's perishin' p*r*sm, an obnoxious inspiration intruded. Why shouldn't a simplex in Euclidean space also sport an ` m-fold' exsphere, tangent to m facets on their exterior side, and to n-m+1 on their interior side, where perhaps m > 1 ? In particular, show (A) That m = 2 is impossible when n = 2 (for a triangle); (B) That m = 2 is impossible when n = 3 (for a tetrahedron); (C) What happens for m = 2 and n = 4 (for a pentatope); (D) What happens for general 0 <= m <= n+1 ? Fred Lunnon

4 10

[math-fun] recognizing an even permutation
by Warren D Smith 02 May '16

02 May '16

Yes, Arndt & Miller both had the same "cycle chasing" idea although Miller made the nice point the extra array of bits can be stored in the sign bits of the f(n) integer array, then reset to "+" afterwards. That runs in O(n) time and O(n) extra bits worth of storage. Also, it can be done in O(n^2) time and O(1) words storage by for(i=1 to n){ find cycle size for i, f(i), f(f(i))... } and then the sum of the cycle (cardinality-1) values, summed over all non-last elements in all cycles, has the same parity as the permutation. (You are the "last" cycle element if the maximum over all elements in your cycle. Keep track of running max.) Also, it can be done in T time and S words storage for any T with n<T<n^2 with T*S=n^2. ["Word" means order log(n) bits.] You find the first S elements of cycles longer than S. Then alter the permutation to shorten that cycle to length S, storing the alteration so can later undo it. In this way in storage<=n/S and time O(n) we shorten all cycles to lengths<=S. Then we do the above algorithm, with runtime<=n*S. Then we unalter the alterations. [There are also other ways to rethink that same algorithm involving use of hash tables for "memoization" instead of perm-alterations, etc; for example in the Arndt/Miller method, do not mark with a bit every guy; instead just mark every Kth guy round a cycle, then you can use K times less storage but each bit-lookup costs K times more. If we pre-choose a random-like function that is 1 a fraction 1/K of the time, and 0 the rest, and only mark bits where magicfunction(n)=1 we can avoid the log(n) storage factor and perhaps still get runtime n*K in some randomized expected sense.] It seems to me it is not possible to determine permutation parity if examine only n-2 entries of the f() array, since the other 2 entries could be crux. So linear time is best possible. However, that lower bound argument may have been too facile. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 2

[math-fun] recognizing an even permutation
by Warren D Smith 29 Apr '16

29 Apr '16

Given a permutation of {1,2,3,...,N}, how iton -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 3

[math-fun] Distributive law without +? (6th Grade)
by Bill Gosper 27 Apr '16

27 Apr '16

The simplification 6(9) = 6×9 is an example of (choose one) a) associativity b) commutativity c) distributivity. "Answer": c. Has anybody ever seen this usage of "the distributive law"? This is from the same Common Core idiots who outlaw "improper" fractions. They also insist that parens enclosing parens be changed to square brackets. --rwg

11 12