Let's discuss Mathematics

[Mise]

I fell asleep once in a Maths lecture, leaning over the desk in front of me. There was a really cute girl behind me; her pen rolled off the end of her desk, and down the back of my seat. Luckily, it didn't go down my boxer-covered ass crack, as it was obstructed by the seat back. It woke me up, so I fumbled round to get it, only to dislodge it from its obstructed position. It inevitably fell down into my ass crack. She stifled a giggle and said thank you as I gave it back to her.

That's the only cute-maths-girl anecdote I have

 

[Spoonwood]

Is a brute force approach a good mathematical exercise?

Is the 4 colour theorem (reduce it to loads of cases and brute force them) a good proof?

I say NO! Discuss...

I say YES! If a proof works, then it is at least somewhat good. If proof A and proof B prove the same theorem, and A has fewer steps than B and has more readily thought hypotheses, then A comes out more good than B. All proofs are good, it's only a matter of degree. There does exist an aesthetic appeal to so-called "brute force" approaches to proofs. It comes as much the same as the aesthetics of brick-laying or meditation or ritual where one does the same things over and over and over again. Wanting all proofs to come as short, elegant, and "intuitive" to professional mathematicians, comes as analogous to wanting all people to think well quickly, speak in beautiful words, and simply.

But, not only does that come as unrealistic, if that ever were to happen there wouldn't exist any possibility (or much less possibility) of creativity in seeing new ways of understanding and appreciating language. In the same way, if no brute force proofs existed, then there wouldn't exist the possibility of new proofs emerging, the possibility of simplification of proofs, and there would exist less ways in which proofs can work. Proofs would exist in a less diverse context. Considering that diversity in the natural world produces and allows for far more beauty and possibility, if we had the choice to do so, why would we want to limit the diversity of how proofs may appear? If you enjoy listening to Mozart, Bach, and Beethoven, do you want only those composers music ever to get heard and all music sheets of Duke Ellington, The Beatles, Queen, Count Basie, Berlioz, Scott Joplin, Arnold Schoenburg, and Weird Al Yankovic to get burnt?

It would be one thing if "brute force" proofs forced everyone to always use them, or we all had to constantly get subjected to them like people don't know how to shut their music off in the interest of courtesy. However, has this happened with brute force proofs? I don't think so. And barring something like that, rejecting brute force techniques in proofs as "good" comes as no different than not liking Edgar Allen Poe's "The Raven" or Coleridge's "The Rime of the Ancient Mariner" or Shakespeare's Hamlet, because they evoke some dark emotion in you. All of those are art despite their lack of prettiness. And proofs like those of the four-colour theorem and the brute-force techniques used in the referenced link have an aesthetic quality to them despite some mathematicians personal, a priori, conceptions of "elegance". If Mathematics were conscious, it would feel insulted at people who call such brute force techniques "bad". For if Mathematics were conscious, it surely comes as large enough in scope to end up beyond the "good and bad" or "good and evil" of the mathematicians who don't like those techniques.

If we could choose to do so, why not perceive Mathematics in its True form, and see its Beauty in how it is, in itself?

 

[ParadigmShifter]

Nice post!

I think there is an elegant proof of the four colour theorem waiting to be found though.

 

[ThinkTank]

I GOT THE ANSWER I GOT THE ANSWER!!!

Nice! Within 2 days!

Glad you enjoyed it, I sure did. If you are interested in a recent logical analysis that also has some background of the puzzle, Google for an article named "Sum and Product in Dynamic Epistemic Logic".

 

[Mise]

Well I don't mean to brag but technically it took me an afternoon, since I didn't read it until midday yesterday. /smugmode

Also, Para, the article has links to "elegant" proofs, and a treatment of the modal logic and whatnot. It, incidentally, makes my spreadsheet look more elegant and aesthetically appealing than ever.

 

[Spoonwood]

Let e denote any even number. Show that 3 divides into 2^e-1.

Possible techniques:

Spoiler :

Use mathematical induction.

Spoiler :

Use mathematical induction in terms of rates of change. E. G. say we want to show 1+2+...+n=n(n+1)/2. Let L(k)=1+...+k, R(k)=k(k+1)/2. Then L(k+1)=1+...+k+(k+1), and thus the rate of change from L(k) to L(k+1) equals L(k+1)-L(k)=k+1. Similarly R(k+1)-R(k)=
(k+1)(k+2)/2-k(k+1)=(1/2)[(k+1)(k+2)-k(k+1)]=(1/2)[(k+1)(k+2-k)]
=(1/2)*2*(k+1)=k+1. So, L(k+1)-L(k)=R(k+1)-R(k). Thus, the rates of changes of 1+2+...+n and n(n+1)/2 equal each other, which implies the induction step. 1=1(1+1)/2. So, we have a base case, which completes this proof.

My solution:

Spoiler :

2²-1=3=3*1. (2^k+2-1)-(2^k-1)
=2^k2²-1+1-2^k
=2^k(2²-1)
=2^k(4-1)=(3)2^k. So, the rate of change of from P(k) to P(k_S) where k_S denotes the successor of k in the sequence, equals (3)2^k. So, the induction step holds. Therefore, we can always factor out 3 from P(e)=2^e-1.

 

[dutchfire]

never mind

 

[dutchfire]

Induction: Assume it's true for e-2, then: 2^(e-2) - 1=3k for some integer k -> 2^(e-2)=3k+1 -> 2^e = 12k+4 -> 2^e-1 = 12k+3 which is easily seen to be divided by 3.

The claim is true for e = 0, 2^0-1=0=3*0

By induction, the lemma is true for all even natural numbers e.

 

[ParadigmShifter]

2^0-1 = -1?

Really? You might want to check that dutchy

 

[dutchfire]

*mumble mumble*, it's holiday over here

 

[nc-1701]

show 3|(2^e)-1.

Since e is even e=2*k.
=>2^e -1=(2^k)^2 -1=(2^k -1)(2^k +1)
3 does not divide 2^k => 3 not congruent 0 mod 3
=>2^k congruent to either 1 or -1 mod 3 <=> 3|(2^k +1) v 3|(2^k -1)

Q.E.D.

Much cleaner than induction...

 

[Spoonwood]

show 3|(2^e)-1.

Since e is even e=2*k.
=>2^e -1=(2^k)^2 -1=(2^k -1)(2^k +1)
3 does not divide 2^k => 3 not congruent 0 mod 3
=>2^k congruent to either 1 or -1 mod 3 <=> 3|(2^k +1) v 3|(2^k -1)

Q.E.D.

Much cleaner than induction...

Nice proof! Comparing an induction proof with this one, which one requires more assumptions? To speak surely, this proof requires that we know what "congruent", "mod", and "v" mean in context. So, I guess you don't mean 'cleanliness' in the sense of having fewer assumptions?

Let b and r denote real numbers (I believe complex numbers might work also), with r not equal to 1. Let n denote a non-negative integer. Show that:
b+br+br²+...+brⁿ=b(1-rⁿ⁺¹)/(1-r).

 

[nc-1701]

Nice proof! Comparing an induction proof with this one, which one requires more assumptions? To speak surely, this proof requires that we know what "congruent", "mod", and "v" mean in context. So, I guess you don't mean 'cleanliness' in the sense of having fewer assumptions?

Let b and r denote real numbers (I believe complex numbers might work also), with r not equal to 1. Let n denote a non-negative integer. Show that:
b+br+br²+...+brⁿ=b(1-rⁿ⁺¹)/(1-r).

I generally view constructive proofs as better than induction, contradiction, etc. proofs as they don't require those extra logical steps. "v" can easily be replaced with "or" so no big deal their, I do use congruence though which is a more powerful tool but not a huge one.
Really I mean cleanliness as "directness" I suppose, induction always feels kind of round about to me. Could just be I like the one I made though

b+br+br²+...+brⁿ=b(1+r+r²+...+rⁿ) since 1-rⁿ⁺¹ can be factored as (1-r)(1+r+r²+...+rⁿ) we can divide by (1-r) and get (1-rⁿ⁺¹)/(1-r)=(1+r+r²+...+rⁿ)
Then by substitution into our original equation we get:
b+br+br²+...+brⁿ=(1-rⁿ⁺¹)/(1-r)



My turn

Prove
[a]+[a+1/n]+[a+2/n]+...+[a+(n-1)/n]=[a*n] for all real numbers a. Where [x] denotes the integer part of x.

 

[Petek]

Write a = [a] + b/n, where 0 <= b < n. Then

[na] = [n[a] + b] = n[a] +

because n[a] is an integer. Next,

[a] + [a + 1/n] + ... + [a + (n-1)/n]
= [[a] + b/n] + [[a] + (b+1)/n] + ... + [[a] + (b+n-1)/n]
= n[a] + [b/n] + [(b+1)/n] + ... + [(b+n-1)/n] (using [[a] + (b+j)/n] = [a] + [(b+j)/n])
= n[a] + [(b+n-1)/n] + [(b+n-2)/n] + ... + [b/n] (reversing the order of the sum)
= n[a] + {([b+n-1)/n] + ... + [b+n-)/n]} + {([b+n--1)/n + ... + [b/n]} (breaking the preceding sum into two parts)

Now, it follows from the definition of the terms that

[(b+n-j)/n] = 1 if j = 1, 2, ..., , and
[(b+n-j)/n] = 0 if j = +1, +2, ..., n

Therefore, the last sum above equals

n[a] + {1 + ... +1} ( summands) + 0
= n[a] +

This shows that [a] + [a + 1/n] + ... + [a + (n-1)/n] = n[a] + = [na], as required.

If this solution is OK, do I get to propose a problem?

Petek

 

[ParadigmShifter]

Anyone can propose a problem at any time! This isn't just a quiz thread.

 

[Truronian]

You can never have too many maths problems!

 

[Petek]

OK, here's a favorite of mine:

Let N be a positive integer. Show that some integer multiple of N consists entirely of the digits 0 and 1 (written in base 10).

Petek

 

[Truronian]

I got nowhere with a back of the envelope by-induction...

 

[ParadigmShifter]

I don't think induction will cut it since it probably depends upon prime factors.

2*5 = 10
3*37 = 111
4*25 = 100
5*2 = 10

Interesting relationship between 2 and 4 there, 100 = 10^2

You can also get 1110 as a multiple of 6 by multiplying 2*5*3*37 as well (not sure if that is the lowest number that does the trick).

EDIT: I think the first step will be to show that if p is prime then there exists an x such that px has the desired property.

EDIT2: Hmm 9 case is interesting the smallest value has to be 111111111 = 9 * 12345679 = 9 * 37 * 333667, so 37 is a factor of that too

EDIT3: Also, 111111111 = 111 * 1001001

EDIT4: 1001 = 7 * 143. 143 = 11 * 13 so my first thought that the "companion" number to a prime would also be prime is false.

 

[ParadigmShifter]

Looking at the problem from the other way around, we have the following sequence (prime numbers in bold, dots denote multiplication)

1
10 = 2.5
11 = 11
100 = 2.2.5.5
101 = 101
111 = 3.37
1000 = 2.2.2.5.5.5
1001 = 7.11.13
1010 = 2.5.101
1011 = 3.337
1100 = 2.2.5.5.11
1101 = 3.367
1111 = 11.101
10000 = 2.2.2.2.5.5.5.5
10001 = 73.137
10010 = 2.5.7.11.13
10011 = 3.47.71

(thanks to Wolfram Alpha there )

Obviously, after 10 we can disregard any new factors showing up for numbers ending in sequences of zeroes (they will just be a previous number in the sequence multiplied by 2^k.5^k).

But I can't see much progress going down that route, we would have to show that any prime number shows up as a factor of one of the numbers in the sequence.