Wikipedia:Reference desk/Archives/Mathematics/2017 August 1

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 1

Powers of 2 are "rude"

In mathematics, polite numbers are exactly the positive integers that are not powers of 2. The powers of 2 are impolite. Could they and have they ever been called "rude" as a pun on the non-mathematical meanings? GeoffreyT2000 ^{(talk, contribs)} 15:34, 1 August 2017 (UTC)

Or if a number isn't Prime, is it Choice or Select? --RDBury (talk) 20:00, 1 August 2017 (UTC)

@GeoffreyT2000: The Google search rude "polite number" sum of consecutive quickly finds examples like Polite and Rude Numbers. PrimeHunter (talk) 23:20, 3 August 2017 (UTC)

Looking for easy way to check for enough at bats...

Often times for things like batting titles, the requirement is the highest average with a minimum number of at bats. What I'm trying to figure out is whether there is any way to tell from the percentage whether the player *must* have had a specific number of at bats. For example, let's say that the requirement is that the player hit .302 and they must have 15 at bats. I *know* given the average that they must have hit at least 15 at bats since no fraction of the form A/B with B less than 15 has a value between .3015 and .3025. So is there an easy way to do this other than trying to calculate all of the values of the closest fractions for denominators between 1 and 14? Normally the number of at bats is 200, so the question is whether any batting average that isn't *very* close to zero of very close to 1 (like .998) guarantees enough at bats?

More generally, given rational numbers p<q, what is the smallest denominator rational a/b so that p≤a/b≤q? One way you might do it is to form the continued fraction representations of p and q, from which is should be easy to find the continue fraction of the smallest denominator faction between them. For example in your case, p=.3015=[.3.3.6.2.1.2.1.2] and q=.3025=[.3.3.3.1.2.3], and the desired fraction will be [.3.3.4] = 13/43. --RDBury (talk) 20:45, 1 August 2017 (UTC)

PS. You might also find the article on Farey sequences useful. --RDBury (talk) 20:47, 1 August 2017 (UTC)

Thanx. I hadn't thought of using continued fractions in that way. and Farey sequences look interesting for thatNaraht (talk) 19:57, 3 August 2017 (UTC)

(Reply to original post). Well, you could use composite numbers to take a short cut. For example, if you know that the denominator can't be 180, then you know it can't be any of the factors, like (2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90), because, for example, if x/180 fits, then (x/3)/60 also fits, and conversely if x/180 doesn't fit for any integer value of x, then (x/3)/60 doesn't fit for any value of x, and, if we imagine x = 3y, this means (3y/3)/60 or y/60 can't fit for any integer value of y.

Not sure if I'd bother to write a program to take advantage of that, though, as brute force is quick enough for numbers like 200, and might even be faster in that range. If I were to write such a program, I'd start at the upper limit, say 200, and once I eliminated that I'd eliminate all the factors of 200, then continue with 199, etc., skipping numbers which have been eliminated. StuRat (talk) 20:48, 1 August 2017 (UTC)

Yes, a computer program would probably faster. But I learned something. :)Naraht (talk) 19:57, 3 August 2017 (UTC)

Strong induction

Can someone please prove Strong induction from the basic induction?

The information in that page isn't clear much. יהודה שמחה ולדמן (talk) 20:56, 1 August 2017 (UTC)

@יהודה שמחה ולדמן:"Strong induction" is not a theorem that can be "proven" so you will need to be more specific.--Jasper Deng (talk) 00:43, 2 August 2017 (UTC)

You might try "Equivalence of Well-Ordering Principle and Induction" on ProofWiki. --RDBury (talk) 03:15, 2 August 2017 (UTC)

The following are equivalent:

1) Strong induction for subsets of N

2) Induction for subsets of N

3) Every nonempty subset of N has a least element.

$1\to 2$ is trivial. For $2\to 3$, suppose for contradiction that X is a nonempty subset with no least element. Let Y be the set of natural numbers a which are strictly below every element of X. 0 is not in X, as otherwise it would be the least element of X, so 0 is in Y. If n is in Y, then were n+1 to be in X, n+1 would be the least element of X, contrary to assumption. So n+1 is not in X and thus is in Y. By induction, every natural number is in Y, contrary to the assumption that X is nonempty.

For $3\to 1$, suppose X is a set such that: for every n, if every b < n is in X, then n is in X. Suppose for contradiction that X is not all of N. Then the complement of X is nonempty, and so by induction has a least element, z. Then for every b < z, b is in X by choice of z. By assumption about X, this means z is in X, a contradiction.--108.52.27.56 (talk) 03:23, 2 August 2017 (UTC)