- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Quantifiers
by James Propp 15 Jun '20

15 Jun '20

Math gives us one way to dissect the ambiguity of sentences like “In New York City, someone is attacked by a pigeon every thirty seconds” (is it always the same person? is it always the same pigeon?) by way of quantifiers. Does linguistics have its own way of talking about the different interpretations of such a sentence? Jim

7 6

[math-fun] Program counting Hamiltonian paths
by James Propp 15 Jun '20

15 Jun '20

Does anyone know of a good software for counting Hamiltonian paths in a graph from one specified vertex to another? Jim Propp

3 2

[math-fun] Peg Solitaire question
by James Propp 15 Jun '20

15 Jun '20

Robin Houston asks ( https://twitter.com/robinhouston/status/1272564182098075652?s=21 ) : “The game of Solitaire has an unusual symmetry. If you interchange filled and unfilled places, and *also reverse time*, the game is unchanged. Is it known whether there is a “palindromic” solution, i.e. a solution that is invariant under this symmetry?” There is a known solution that is symmetric in a different sense: https://www.youtube.com/watch?v=z9nkGgxcT-w Jim Propp

1 0

[math-fun] Pen Testing
by Tomas Rokicki 15 Jun '20

15 Jun '20

I encountered this problem during the Google CodeJam competition. I'm paraphrasing it here briefly but the actual link is here: https://codingcompetitions.withgoogle.com/codejam/round/000000000019ff7e/00… The idea is, you have n ballpoint pens, each with between 0 and n-1 units of ink in them. You have exactly one pen of each value, but they are randomly mixed and the only way you can tell which is which is by actually using them until they run out. You want to select two of the pens such that the chance that you have at least n units of ink between the two pens is as high as possible. You can perform any number of tests on any pens, but your only test is to try a pen. When you try a pen, either it is out of ink, or it writes (has ink) but the test itself decreases the amount of ink in that pen by one unit. For a given n (say, n=15), what's a strategy to maximize the chance that the two pens you choose contain at least 15 units of ink between them? if you just choose two pens at random the chance is about 46.7%. The problem was given as a programming problem (as part of a 2 1/2 hour contest) but I think it has sufficient interesting mathematics to be of general interest here. The problem is attributed by Google to Ian Tullis. -tom -- -- http://cube20.org/ -- http://golly.sf.net/ --

2 2

[math-fun] Commas as duplicators
by Éric Angelini 15 Jun '20

15 Jun '20

Hello Math-Fun, Today we want to duplicate only the last digit "d" of a(n): we just make it jump over "d" digits to the right and paste. As usual, we want S to be the lexicographically earliest sequence of distinct positive terms with this property: S = 1, 2, 11, 21, 3, 12, 4, 322, 5, 42, 6, 7, 251, 8, 161, 71, 9, 14, 83, 17, 43, 19, ... Explanation: See the commas of S as "duplicating catapults" to the right; – the last digit of a(1) = 1 is 1; this 1 is duplicated after jumping to the right over 1 digit; – the last digit of a(2) = 2 is 2; this 2 is duplicated after jumping to the right over 2 digits; – the last digit of a(3) = 11 is 1; this 1 is duplicated after jumping to the right over 1 digit; – the last digit of a(4) = 21 is 1; this 1 is duplicated after jumping to the right over 1 digit; etc. How was S built: We start with a(1) = 1: S = 1, . . . The first comma catapults to the right a copy of 1 over 1 free space: S = 1, . 1 . . . What is the smallest available integer obeying the constraints of this pattern? Obviously 2: S = 1, 2, 1 . . . The second comma catapults to the right a copy of 2 over 2 free spaces: S = 1, 2, 1 . 2 . What is the smallest available integer obeying the constraints? Not 1 (already in S), nor 10 as the zero of 10 would jump over 0 digits to the right and bump into the digit 2 already there: S = 1, 2, 10, 2 . As 10 is forbidden, we try 11 – which is alright: S = 1, 2, 11, 2 . The third comma now catapults to the right a copy of 1 over the digit 2 already there: S = 1, 2, 11, 2 1 The digits 2 and 1 at the end of S form 21 – the smallest available integer legally extending S: S = 1, 2, 11, 21, The fourth comma now catapults to the right a copy of 1 over 1 free space: S = 1, 2, 11, 21, . 1 . What is the smallest available integer obeying the constraints of this pattern? Obviously 3: S = 1, 2, 11, 21, 3, 1 . The fifth comma now catapults to the right a copy of 3 over 3 boxes: S = 1, 2, 11, 21, 3, 1 . . 3 . . . What is the smallest available integer obeying the constraints of this pattern? As 10 is for ever banned (like all terms ending in zero), as 11 is already in S, we try 12: S = 1, 2, 11, 21, 3, 12, . 3 . . . The sixth comma now catapults to the right a copy of this 2 over 2 boxes: S = 1, 2, 11, 21, 3, 12, . 3 2 . . What is the smallest available integer obeying the constraints of this pattern? Obviously 4: S = 1, 2, 11, 21, 3, 12, 4, 3 2 . . . The seventh comma now catapults to the right a copy of this 4 over 4 boxes: S = 1, 2, 11, 21, 3, 12, 4, 3 2 . . 4 . . WARNING What is the smallest available integer (after 4) obeying the constraints of this pattern? Not 3 (as 3 is already in S), not 32 (as a comma after 32 would duplicate the 2 on the 4 already there), not 320 (no terms ending in zero), not 321 (as the 1 would be duplicated on the 4) – but 322: S = 1, 2, 11, 21, 3, 12, 4, 322, . 4 . . The eighth comma now catapults smoothly to the right a copy of the last digit 2 over 2 boxes: S = 1, 2, 11, 21, 3, 12, 4, 322, . 4 2 . Etc. Best, É. P.-S. My personal webpage about that (with colors and pix) is below, but please concatenate the 3 parts of the address: htt p://cinquantesignes.blogspot.com/2020/06/commas-as- duplicators.html

1 0

Re: [math-fun] Quantifiers
by Dan Asimov 15 Jun '20

15 Jun '20

I don't fully agree with the example. The word "deceive" *means* to successfully cause someone else to believe something that's not true — not just to "try" to do this. E.g., American Heritage dictionary's definition of "deceive": ----- 1. To cause to believe what is not true; mislead. ----- Agreed that this may or may not be intentional. A couple of other flagrant but different examples of ambiguity in English are these: "I don't believe X" does *not* automatically mean "I believe X is false," and "I don't like X" does *not* automatically mean "I dislike X." But they are usually *used* that way, as if there are only two possibilities: *believing* or *disbelieving* something, and *liking* or *disliking* something. This quirk of English deceives many into thinking there are only two choices, that one must either believe or disbelieve everything, and that one must either like or dislike everything. I'm not sure if this is intentional on the part of English. —Dan Michael Greenwald wrote: ----- "X did not deceive Y" is ambiguous, by itself, as so many other English sentences are, because of different connotations of the word "deceive". It could (at least) mean: "X did not <successfully> deceive Y" or "X did not <intentionally> deceive Y". In the former X could have intended to, but was unsuccessful. In the latter X may have succeeded in deceiving Y, despite having no intention to deceive. -----

3 3

[math-fun] Discrete tori
by Dan Asimov 15 Jun '20

15 Jun '20

Given a finite field F we can define one type of "discrete torus" as F^n, the vector space of dimension n over F. If |F| = p^k, then |F^n| = p^(kn). But there are many different kinds of tori. Equating R^2 with the complex plane C, there are e.g. both T_4 = C / Z[i] and T_6 = C / Z[w] where w = exp(2πi/3), to list my two favorite 2-dimensional ones. Here Z[i] is the Gaussian integers and Z[w] is the Eisenstein integers. (The notation comes from obtaining T_n from identifying the opposite edges of a regular n-gon.) These two 2-tori are not distinct topologically but metrically, since they each inherit a metric from the Euclidean plane R^2 that is the same locally — a surface of Gaussian curvature K = 0 — but which are distinct globally: There is no isometry carrying one to the other, and there is not even any global "similarity" mapping that multiplies all distances by the same factor. So I'm wondering what kinds of *discrete* tori there are, and what is the appropriate structure on them (like a metric) that may be globally distinct. One way to get other kinds of discrete tori is to imitate how T_4 and T_6 are obtained from R^2 (or from C = C^1): Find a discrete subgroup of the vector space and factor out by it. Since F(p^k) is a vector space over the prime field F(p), its additive group is just the direct sum Z_p + ... + Z_p of k copies of Z_p (where Z_p denotes Z/pZ). So we define an d-dimensional torus T over *the base field* F_p to be T = F^n / A where A is any abelian subgroup of the additive group (F,+) of the field. Just as for the real field R, T is an abelian group as the quotient of abelian groups. We'll say the "dimension" of T is d when d = log_p |T|: dim_(F_p)(T) = log_p(p^(kn) / |A|) = kn - log_p(|A|). I'm not sure what "isometric" or a "similarity" might mean *geometrically* for F^n in the absence of an obvious metric on the vector space F^n. But it makes sense to define the corresponding group of matrices over the field F: Definitions: ------------ An "orthogonal" matrix P over F is any invertible n x n matrix with entries in F such that P^t = P^(-1) (where P^t denotes the transpose). A "similarity" matrix S over F is any constant c ≠ 0 in F times an orthogonal n x n matrix P over F: S = c P. Now we can imitate the conditions under which two tori based on the field R are isometric or similar: Say T' = T (isometric) exactly when T' = P T P^(-1) for some orthogonal matrix P. Say T' ~ T (similar) exactly when T' = S T S^(-1) for some similarity matrix S. —Dan

1 0

Re: [math-fun] Quantifiers
by Henry Baker 15 Jun '20

15 Jun '20

There's also an ambiguity in the word 'attacked': Suppose we define 'attack' as 'physical battery by some part of the pigeon'; then receiving pigeon droppings on one's head qualifies one as the recipient of an 'attack'. So the newspaper headline reads: "In New York City, someone is attacked by a pigeon every thirty seconds", but buried deep in the story is the acknowledgment that 99.9999% of these 'attacks' are in the form of pigeon poop, so pigeon battery via direct contact with a pigeon's beak, for example, might occur only once a year. This form of 'definition inflation' is a media epidemic far more prevalent and far worse than COVID19. At 05:28 AM 6/15/2020, James Propp wrote: >Math gives us one way to dissect the ambiguity of sentences like "In New York City, someone is attacked by a pigeon every thirty seconds" (is it always the same person? is it always the same pigeon?) by way of quantifiers. > >Does linguistics have its own way of talking about the different interpretations of such a sentence? > >Jim

1 0

Re: [math-fun] Quantifiers
by Dan Asimov 15 Jun '20

15 Jun '20

There are also the interesting sentences "I love her cooking" and "Colorless green ideas sleep furiously" among others. —Dan Veit Elser wrote: ----- ... two fine examples showing how even parts of speech can be ambiguous: “Time flies like an arrow” “Fruit flies like a banana” -----

3 2

Re: [math-fun] [EXTERNAL] Re: Much ado about nothing (was Re: Proof that 0^0 = 1)
by Dan Asimov 15 Jun '20

15 Jun '20

Among statisticians there is total agreement on how to define median for a finite multiset of numbers: Order the numbers, repeating them according to multiplicity. If there's a unique middle number, then that's it. If there are two middle numbers, then it's the halfway point between them. —Dan William Cordwell wrote: ----- If we have a finite set of discrete real numbers, {x_i}, then we can ask: What values of a,b,c minimize, respectively \sum_i | xi - a |^2 \sum_i | xi - b |^1 \sum_i | xi - c |^0 a = mean b = median c = mode, if we define 0^0 = 0 (or 0.0^0 = 0) I find this useful when discussing mean, median, and mode with middle-school students, as a way of looking at the values in a more abstract way. I note that there does not seem to be agreement on how to define median. -----

1 0