#math proof

[autistobrat]

tell me about the Knight's Tour

that is what I did every time I was bored when I was about 7

(for who don't know what this is check this)

I calculated how many patterns of this closed circuit could have (which I failed because I soon realised there are a LOT of patterns and brute force attack won't be really effective)

Upon further research, I found out:

There are actually over 26 trillion closed Knight’s Tours on the standard 8×8 board.

26,534,728,821,064 closed tours 13,267,364,410,532 unique ones (since each closed tour can be rotated or reflected)

The rule that is used to calculate this is Warnsdorff's rule.

You’re on a square. The knight has a few options. Warnsdorff says "Look ahead. Count how many valid moves each option has. Pick the one with the least future freedom."

Why?

Because if you don’t, you’ll trap yourself later. It’s basically the knight saying “Let me first visit the squares that are hardest to reach later.”

Does it always work?

Nope.

But on an 8×8 board, starting from most squares, Warnsdorff’s Rule tends to find a complete tour. With a good tie-breaker strategy, it works almost every time.

Why does it seem to work so well?

Because the knight’s mobility varies across the board:

Corners have only 2 possible moves

Edges have 3–4

Centre can have up to 8

Warnsdorff’s Rule pushes the knight away from the highly-connected centre and into the periphery early, clearing the hard-to-reach squares while it’s still possible to get out.

Is there a formal proof of its correctness? Nope.

Warnsdorff proposed the rule in 1823, but:

There’s no general proof that it always yields a knight’s tour

It’s a heuristic, not a theorem

It just works a lot, not always

Mathematicians have studied why it often works, but they’ve also shown counterexamples where it fails. And I was able to find one too.

Let’s consider the 8×8 board, starting at sq(0, 0), the top-left corner.

If you apply Warnsdorff’s Rule naively with no tie-breaking, it fails. It gets stuck before completing the tour. The knight ends up in a dead-end after only 60-ish moves, unable to legally finish the tour.

Why does it fail? Because when multiple candidate squares have equal minimal onward moves, the rule just picks one arbitrarily.

If your tie-breaking is dumb (say, you always pick the first one in the list), you might:

Burn the escape routes early

Leave an isolated square that’s now unreachable

So even though each step looks optimal locally, the knight unknowingly walks into a trap.

If this makes sense....?

[simplydnp]

who's hand is in this picture?

A Mathematically Rigorous Proof That I Spent Too Long Writing

welcome to university math: dnp hand edition

(no, don't leave, you'll be fine i promise)

to begin, we need a statement to prove. we have two options:

- the hand is dan's hand

- the hand is phil's hand

now, for most proofs in university math, you are told a true statement, and you must show why it is true using logic rules, definitions, and theorems. but, we do not know which of these statements are true, so we have to find out.

to prove that a statement is true, we must show that it is always true for the situation presented. to show a statement is false, we must present a single instance where the statement is false (also known as a counter example).

a quick not scary math example:

definition: a prime number is only divisible by 1 and itself.

statement: all prime numbers are odd

(this is false, because 2 is a prime number and it is even. you don't even need to check if there's any others, all you need is one single case where it isn't true to disprove it)

so now that we have a little background on proofs and how to prove and disprove them, we go back to our two statements.

the thing with this situation is, one of them must be true (unless you're gung-ho on someone else holding dan's face while phil takes a picture on his phone of dan in his glasses, in which case, i applaud your commitment, but in actuality this proof will cover that option too)

the full statement we have is: dan is touching his face or phil is touching dan's face

now, because this is Real Life and we have a picture where a hand is touching dan's face, we know already that one of these options is true (as mentioned above) but! using symbolic logic you could also come to this conclusion.

this type of statement is an 'or' statement, and if you're curious, you can look into 'truth-tables' and see why, but at least one of the options must be true.

back to the proof at hand (bah-duhm-tss)

okay. now, proofs also must be 'general' in order to mean anything, really. these are statements of truth of the universe, not just for individuals. so, we will prove this generally.

we have 2 people involved, so individual 1 (dan, the owner of the face and potential face toucher) will be labelled as 'D' , and individual 2 (phil, the possible face toucher who does not own the face) will be labelled as 'P'. thus, this can be true for any such D and any such P.

so with our 'or' statement, in order to prove it, we pick one of the options and say that it is not true, and we have to show then that the other is true.

step 1: let's assume this is not P's hand. (assumption)

step 2: thus, it must be D's hand. (what we take from our assumption)

step 3: now, if it is D's hand, we look at what a hand on one's own face is capable of appearing like. (a definition or true fact about step 2)

the position in the given photo shows the hand with a thumb on the cheek, and a finger on the forehead. so, we find an example of a person with their fingers in the same position (or close to) and see if this supports our claim.

consider:

now, with this image, you can clearly see how the subject's right hand has the thumb on the temple and index finger on the top of their head, however, it is a close enough position for our case.

from the view of the camera, the closest finger to the camera is the edge of the pinkie. in fact, it will always be the closest finger to the camera in this position, assuming the subject has all fingers and no additional appendages.

step 4: we now compare this to our photo (we verify if this holds to our claim or contradicts it)

in our photo, the closest appendage to the camera is the edge of the thumb.

step 5: thus, it cannot be the case that D is touching their own face. (what the evidence says)

step 6: as we assumed it was not P's hand and have shown it cannot be D's hand, and as this is an 'or' statement both of these claims cannot be false, we can therefore conclude it must be P's hand. (our conclusion: re-stating the statement and assumptions and conclusion)

step 7: we verify that P is true (optional step but in beginner proofs you generally show why your case works)

to do this, i will show a picture of a person touching another's face, and compare it to our image.

consider:

now, this image is not exactly the same, similar to above. however, P's left thumb is on the cheek, with their index on D's temple. the closest appendage to the camera (if it were in a similar perspective as our original) would be the edge of the thumb.

comparing it to our original:

our comparison holds.

thus, we can conclude that the true claim in this statement is that P must be touching D's face, which, in particular means that:

phil is touching dan's face in the image

thank you for partaking in phannie mathematics. we now know. i am not sorry.

bonus:

phil has a hitchhikers thumb and dan doesn't so why was this necessary at all 🤡

[felixcloud6288]

Did you know if a number is divisible by 3, you can add all the digits of the number and the sum is divisible by 3? For example, 327 is divisible by 3 and 3+2+7 = 12, which is divisible by 3.

For the Proof on why this is, click Read More

Prerequisite Knowledge

Numbers

Yes, I need to explain how numbers work for this proof.

Let's go back to elementary school. You're being taught basic addition of multi-digit numbers. You're given the number 54,321. 54,321 = 50,000 + 4,000 + 300 + 20 + 1

Let's expand that a little.

54,321 = 5*10,000 + 4*1,000 + 3*100 + 2*10 + 1

Now I''m going to take an aside and mention exponents, just in case.

Normal notation for exponents are a base number with a smaller number floating on the top right corner of your base value. Since Tumblr can't support that notation, I'll use a^b as the notation.

When you have an exponent, you have to multiply the base number by itself however many times the exponent number is. For example, 3^4 = 3*3*3*3 = 81.

Also, if the exponent value is 0 or smaller, you start dividing by the base number instead. So 3^0 = 3/3 = 1.

Now that I've explained that, let's go back to earlier.

54,321 = 5*10,000 + 4*1,000 + 3*100 + 2*10 + 1

Each digit in 54,321 is beling multiplied by an exponential power of 10.

54,321 = 5*10^4 + 4*10^3 + 3*10^2 + 2*10^1 + 1*10^0

This expanded form of an arbitrary number is going to be necessary for the proof.

Modulo and Equivalence

Let's go back to elementary school again. Remember how in division, you'd give a remainder as part of your answer? 12 / 5 = 2 remainder 2.

The modulo operator returns the remainder when you divide two numbers. In programming, % is used for modulo so I'll use that for notation. So 12 % 5 = 2.

An expansion of modulo is equivalence. Two numbers are equivalent under a modulo value when both numbers have the same remainder when divided by the modulo value. Under modulo value 5, 7 and 12 are equivalent because 7 % 5 = 2 and 12 % 5 = 2.

The normal notation for equivalence is the equal sign with 3 lines instead of 2. I'll use == for the notation here.

Since 7 and 12 are equivalent under mod 5, the notation is 7 == 12 (mod 5)

If a number is evenly divisible by a modulo power, it's equivalent to 0. 5 / 5 = 1, therefore 5 % 5 = 0, therefore 5 == 0 (mod 5)

There are some special rules about numbers that are equivalent. We'll let a, b, c, and m be arbitrary numbers.

If a == b (mod m), then a+c == b+c (mod m) If a == b (mod m), then a*c == b*c (mod m) If a == b (mod m), then a^c == b^c (mod m)

The Proof

Now let's move onto the proof.

Let's say we have some arbitrary whole number X which is divisible by 3. That means there is some whole number c such that X = 3*c. So if X is 327, c would be 109 because 109*3 = 327.

Now let's rewrite X into the expanded form from the Numbers section. We'll let d(0) refer to the least significant digit (The one at the far right). d(1) will be the next least significant digit and so on until we reach d(n), the most significant digit.

X = d(n)*10^n + d(n-1)*10^(n-1) + ... + d(1)*10^1 + d(0)*10^0

Since X is divisible by 3, that means the long form of X is equal to 3c.

d(n)*10^n + d(n-1)*10^(n-1) + … + d(1)*10^1 + d(0)*10^0 = 3*c

Now let's start doing some modulo.

10 == 1 (mod 3)

By the earlier rules mentioned in the Modulo section, we can multiply and exponentiate each term (The parts between the +) and they're still equivalent. So now we'll replace each term with an equivalent term under mod 3.

d(n)*10^n + d(n-1)*10^(n-1) + ... + d(1)*10^1 + d(0)*10^0 == d(n)*1^n + d(n-1)*1^(n-1) + … + d(1)*1^1 + d(0)*1^0 (mod 3)

1 exponentiated to any power is 1 so

d(n)*10^n + d(n-1)*10^(n-1) + ... + d(1)*10^1 + d(0)*10^0 == d(n) + d(n-1) + … + d(1) + d(0) (mod 3)

Meanwhile 3*c == 0 (mod 3). Since 3*c = X, then anything equivalent to X is equivalent to 0.

d(n) + d(n-1) + … + d(1) + d(0) == 0 (mod 3)

At this point we can say the sum of all the digits of X can be divided by 3 because the sum would have no remainder.

So in conclusion, if the sum of all the digits of a number can be divided by 3, then the number can be divided by 3.

[roomfullofpigeons]

Differentiate f(x) = g(x)h(x) [Product rule proof]

f(x) = g(x)h(x)  [I’m defining the function “f(x)” as the product of two other functions, g(x) and h(x)]

ln(f(x)) = ln[g(x)h(x)] = ln[g(x)] +ln[h(x)] [I took the natural logarithm of both sides, so that I could split up my product into a sum of natural logarithms.]

f’(x)/f(x) = g’(x)/g(x) + h’(x)/h(x) = [g’(x)h(x) + g(x)h’(x)]/g(x)h(x)  [I’ve differentiated both sides, then written my side with g(x) and h(x) as a single fraction]

f’(x)/f(x) = [g’(x)h(x) + g(x)h’(x)]/f(x) [Substituted in f(x)=g(x)h(x)]

f’(x) =  g’(x)h(x) + g(x)h’(x)  [Multiply both sides by f(x). Now we have a formula for the differential of g(x)h(x)! This is called the product rule!]

[mathblab]

An applied mathematician loves the theorem. A pure mathematician loves the proof.

Anonymous

[autistobrat]

can you prove the l'hopital's rule? I'm having a hard time in my calculus and you seem to know these stuffs 😭😭😭

For the ∞/∞ case, you tweak things: instead of

f, g → 0

you require

|f|, |g| → ∞

and the same CMVT argument works.

If you want the full generality like one-sided limits, extended reals, etc, you just slap on technical conditions, but the core is the same.

So basically the L’Hôpital’s rule is just CMVT but with squiggly lines.

Hope this helped :D

[autistobrat]

A king has 1000 bottles of wine, one of which is poisoned. Anyone who drinks even a single drop of the poisoned wine will die, but the poison takes exactly 10 hours to kill. The king needs to find the poisoned bottle as quickly as possible because there's a feast in 10 hours, and he must ensure all wine is safe. He has exactly 10 prisoners to use as test subjects, and he can mix any number of drops from any number of bottles for each prisoner to drink. What is the minimum number of hours needed?

Oh FINALLY some interesting riddle

Let's number the wine bottles from 0 to 999.

Convert each bottle number into a 10-digit binary (b/c 2¹⁰ = 1024 > 1000). For example:

Bottle 0 = 0000000000 Bottle 1 = 0000000001 Bottle 2 = 0000000010 Bottle 3 = 0000000011 Bottle 999 = 1111100111

Assign each of the 10 prisoners to a binary digit position (1 prisoner per bit).

Now, for every bottle, if the digit in a position is a 1, that prisoner drinks a drop of that wine. So a single bottle might be tested by multiple prisoners.

After 10 hours, some prisoners die, and some don’t.

Now read the binary pattern of deaths.

If prisoner #1 (representing the leftmost bit) dies, that bit is 1. If they survive, it’s 0. Put the bits together and the resulting binary number is the poisoned bottle’s number.

So it takes no more than 10 hours to find out the poisoned wine.

[autistobrat]

Infodump of the day bc why not

when you hold your necklace loose

and flip it so it's like the picture on the right

it is the same with the arc on the bridge

When you hold a necklace loosely, it naturally hangs into a catenary curve. When you flip it vertically, you get the same shape as a suspension bridge arch, or even better, a catenary arch.

A bit detailed explanation incoming:

A hanging chain like a necklace forms a catenary, from the Latin catena, that means chain.

Mathematically, this curve is:

y = a cosh (x/a)

where cosh is the hyperbolic cosine.

When you flip the necklace vertically, you get the inverted catenary.

And it is the shape that perfectly distributes compressive forces.

In bridges or arches, that is the best structure it can have.

If you want a self-supporting arch, it should be in the shape of an inverted catenary, because it makes all forces compressive.