[–] 40 points41 points  (15 children)

sorry, this has been archived and can no longer be voted on

I don't think this actually answers your question, but I'm a big fan of nuclear flyswatter techniques. One of the most hilarious examples I've seen poses this relatively simple problem:

You just won at a slot machine! The casino always empties the slot when it reaches $1,000.00. The machine only has quarters and nickels. One possible jackpot is 2 quarters and 3 nickels, one possibility is 4,000 quarters and there are many more possibilities. All possibilities totaling$1.00 or less are displayed in the figure below. How many different jackpots are there?

The author then goes on to use the Atiyah-Singer index theorem to solve it. It starts on p. 20 and ends ten pages later with the ridiculous understatement

It is clear that the Atiyah-Singer index theorem is not the easiest way to solve this problem.

[–] 21 points22 points  (14 children)

sorry, this has been archived and can no longer be voted on

In my master's thesis I proved that a class of languages was not regular by showing that it contained languages at arbitrary levels of the arithmetical hierarchy.

[–] 1 point2 points  (8 children)

sorry, this has been archived and can no longer be voted on

This is usually done with the pumping lemma, right?

[–] 3 points4 points  (6 children)

sorry, this has been archived and can no longer be voted on

Yes, indeed, or the Myhill-Nerode theorem. As vincentrevelations pointed out, there are languages that can pump without being regular. But in fact, my work was not on regular languages, but on the less-known (and more powerful) ET0L languages -- the situation is similar to the regular languages but I didn't want to go into details.

I had proved a type of pumping lemma for ET0L languages, and needed to show that it was not a sufficient condition (only necessary). So the class of languages was exactly the set of languages which satisfied the lemma, and I needed to show they were not all ET0L. Well, I thought, how far from ET0L can we go? and this lead me to a proof. When it came to writing the result I simplified a bit, taking only a single example language and showing it was uncomputable.

[–] 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

That's great! I love stuff like this.

[–] 0 points1 point  (4 children)

sorry, this has been archived and can no longer be voted on

Wait, did you show it was undecidable?

[–] 0 points1 point  (3 children)

sorry, this has been archived and can no longer be voted on

Yeah, I prefer "computable" to "decidable" but they mean the same.

[–] -1 points0 points  (2 children)

sorry, this has been archived and can no longer be voted on

Sure. I use "decidable" and "recognizable", and I think "decidable" makes sense because you're talking about decision machines.

[–] 1 point2 points  (1 child)

sorry, this has been archived and can no longer be voted on

And "computable" makes sense because you're talking about decision machines :)

[–] -1 points0 points  (0 children)

sorry, this has been archived and can no longer be voted on

Yup, but computable could also refer to recognition.

[–] 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

Depends. There are languages that can pump without being regular. In that case you'll need something else to prove that they aren't regular.

[–] 0 points1 point  (3 children)

sorry, this has been archived and can no longer be voted on

Can you explain this a little more? I'm thinking of writing a thesis as an undergrad, and I'm looking for ideas.

[–] 1 point2 points  (1 child)

sorry, this has been archived and can no longer be voted on

I'm sure Wikipedia can explain both regular languages and the arithmetic hierarchy better than I can.

[–] 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

Actually your response to mrdmnd is what I was interested in, i.e. what specifically you worked on and your techniques. Thanks!

[–] 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

See if you can find something interesting to work on from here.

There are many references to some interesting problems within that book. Also, the classification of sets as "mathematical data types" is pretty amusing.

[–] 29 points30 points  (1 child)

sorry, this has been archived and can no longer be voted on

OP, You didn't even fully answer your own question: What was the problem that you solved?

[–] 24 points25 points  (5 children)

sorry, this has been archived and can no longer be voted on

Earlier this semester I was sitting in a Metaphysics G.E, and for some reason what was functions from one copy of a 2-disk to itself. The professor then needed to argue that some philosophers argument was wrong because there was a mapping that had a fixed point. I then pointed out that all the mappings had a fixed point. Thank you Algebraic Topology.

[–] 49 points50 points  (2 children)

sorry, this has been archived and can no longer be voted on

I would like to hear more about proving philosophers wrong using fixed points please.

[–] 10 points11 points  (1 child)

sorry, this has been archived and can no longer be voted on

We were going over various definitions for when an object is said to be moving. One account suggested breaking the object down into different partitions and then analyzing whether those parts of the object move. The professor brought up a counter example of a spinning disk whose center is not moving given a certain partition, which I then generalized to what I said above.

[–] 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

Awesome.

[–] 2 points3 points  (1 child)

sorry, this has been archived and can no longer be voted on

[–] 1 point2 points  (0 children)

sorry, this has been archived and can no longer be voted on

[–] 25 points26 points  (0 children)

sorry, this has been archived and can no longer be voted on

In a physics class of mine, we were learning about applying differential equations. I was struggling to grasp it all. On one of our projects there was a question about a river that contained two trees right on the banks - the line between them perpendicular to the river. A man started at one tree and kayaked across the river (at the same constant rate that the river flowed) to the other side. The caveat was that he constantly paddled in the direction of the tree, so it wasn't linear. Where did he land on the other bank?

After struggling with it for a second, it occured to me that I could just apply my knowledge of conics, as the tree was the focus of a parabola. That meant that the man would land at the latus rectum which was a really obscure thing for me to have remembered. Although intended to be a full-page write up, I managed to knock it out in three lines.

[–] 22 points23 points  (0 children)

sorry, this has been archived and can no longer be voted on

I was cramming for a cryptography exam on the flight to Seattle for a Microsoft interview, and managed to apply a lattice reduction algorithm to a search query interview question. Got me a job!

[–] 36 points37 points  (4 children)

sorry, this has been archived and can no longer be voted on

For my first postdoc, I was working on controlling an instrument on a remote spacecraft (SOHO). I had to learn a stripped-down language that the team had written to control uploads to the spacecraft. The first thing they asked me to do was write a codewalker that would estimate the amount of time a given upload would take. I demonstrated that the language was Turing-equivalent and therefore the problem was impossible in the general case due to Godel's Incompleteness Theorem (they had asked me to solve the Halting Problem).

It turns out, though, that you can solve it in all the cases you care about. Classic engineering dilemma.

[–] 13 points14 points  (1 child)

sorry, this has been archived and can no longer be voted on

I used to have a job as a compiler-tools writer. We had to solve halting problems every day. E.g. "warning: unreachable code"

[–] 4 points5 points  (0 children)

sorry, this has been archived and can no longer be voted on

This is a key point that I think the software engineering world is getting better at. When something is impossible in the general case, the solution is to make the tooling good enough that it is easy to deal with in the specific case.

[–] 3 points4 points  (1 child)

sorry, this has been archived and can no longer be voted on

Every time somebody brings up the Halting problem in an argument, which happens waaay to often, I ask them for an example that is undecidable. Most of them can barely remember any example.

The only example I know about (but can't fully remember) is the one with the contradiction machine, which was incredibly contrived and unrealistic. I still hate my professor for not stressing that the Halting problem is mostly a theoretical tool.

[–] 2 points3 points  (0 children)

sorry, this has been archived and can no longer be voted on

The contradiction machine? You mean, the language of machines that do not accept when given themselves as input? If the language were decided by a machine M, then either M(M) returns a no, in which case M does not accept itself and M should return yes, or M(M) returns yes, in which case M halts and accepts on itself as input, and M(M) should return no.

This is exactly what we have to work with, the language of machines which do NOT halt, because the language of machines which DO is recognizable. In fact, this machine is exactly the same as the diagonal argument for the halting problem being undecidable.

[–] 41 points42 points  (4 children)

sorry, this has been archived and can no longer be voted on

I haven't seen the relevant episode, but the writers for Futurama ended up having to prove a new group theory result to demonstrate that the protagonists' scheme to deal with some weird extradimensional shit would've worked.

[–] 24 points25 points  (3 children)

sorry, this has been archived and can no longer be voted on

[–] 11 points12 points  (1 child)

sorry, this has been archived and can no longer be voted on

Ha! I literally just watched this episode over the weekend! The proof is up on the glowboard onscreen for like half a second, but I paused it and was able to follow the proof fairly well, but I had no idea the writers had come up with this theorem. More people need to know about stuff like this. Also, I'm gonna keep this bookmarked for any time anyone talks about how smart Big Bang Theory is.

EDIT: Also, my favorite part is that, in the show, this theorem is postulated not by Farnsworth but by the Harlem Globetrotters.

[–] 3 points4 points  (0 children)

sorry, this has been archived and can no longer be voted on

It's great because we have genuinely well-written - and tightly-written, I might add - shows like this that are both a lot of fun and provoke a great deal of thought - that then get cancelled to make room for Family Guy, The Cleveland Show, Jersey Shore (actually, virtually any reality show), and so on.

[–] 4 points5 points  (0 children)

sorry, this has been archived and can no longer be voted on

It would be really good if Futurama found a way to reference the Futumara projections (from compiler theory)

[–] 29 points30 points  (7 children)

sorry, this has been archived and can no longer be voted on

This is small potatoes, but I liked it. I was playing pub trivia, and our team tied for first. So the host asked for a representative from each team to come up for a tie breaker. I went up, and he asked each of to pick a number between 1 and "oh, 13,000" and whoever came closest would win. I immediately recognized this as the cake cutting problem, and so "graciously" let my opponent choose first. They said something like 344, and so I said 345 and claimed the lion's share of the possible numbers.

Well, it was good math, but not good psychology. The correct answer was in the 200s, and I lost. :(

[–] 15 points16 points  (6 children)

sorry, this has been archived and can no longer be voted on

Who in their right mind wouldn't have picked 6500 if they went first.

[–] 18 points19 points  (2 children)

sorry, this has been archived and can no longer be voted on

Who in their right mind would have the participants communicate the numbers at all.

[–] 13 points14 points  (1 child)

sorry, this has been archived and can no longer be voted on

At all? ;)

[–] 10 points11 points  (0 children)

sorry, this has been archived and can no longer be voted on

Erm, well.

[–] 4 points5 points  (0 children)

sorry, this has been archived and can no longer be voted on

probably 99%+ of the population

[–] 2 points3 points  (1 child)

sorry, this has been archived and can no longer be voted on

The way it was phrased, it wasn't clear that the goal was to pick the number closest to the secret number that the host was thinking.

[–] 1 point2 points  (0 children)

sorry, this has been archived and can no longer be voted on

You're right, thanks. I've fixed the wording...

[–] 25 points26 points  (0 children)

sorry, this has been archived and can no longer be voted on

I once had to do some cooking with my mother, and we had to cut out a third of some spherical vegetable. I used revolution of objects around the x-axis to find out where to cut it so the cross-section at the cut would have the least area, so the vegetable would spoil the least.

[–] 9 points10 points  (5 children)

sorry, this has been archived and can no longer be voted on

I wound up coming up with a divisibility rule for 10x -1, with x in Z to settle a debate about whether or not the \$.99 store we were at near the US-Canada border was duty-free

[–] 5 points6 points  (4 children)

sorry, this has been archived and can no longer be voted on

Just to understand it better: isn't 10x -1 always divisible by 9?

[–] 3 points4 points  (2 children)

sorry, this has been archived and can no longer be voted on

Yes, since x is an integer we may rewrite 10x - 1 = 10x - 1x = (10-1)×(10x-1 + 10x-2 ×1 + ... + 10×1x-2 +1x-1 )

Clearly the left term in the product is divisible by 9, so that 10x -1 is also divisible by 9.

[–] 9 points10 points  (1 child)

sorry, this has been archived and can no longer be voted on

Yeah... also....

999...999 = 111...111 x 9

[–] 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

... or 10x - 1 mod 9 = 1-1 = 0

[–] 1 point2 points  (0 children)

sorry, this has been archived and can no longer be voted on

Yup, but the converse is not true. the rule I came up with is similar, but instead of adding individual digits, you group the numbers based on how many digits the number you're testing for divisibility by happens to have, so for ninety nine, you group then in pairs

edits for weird cell phone things

[–][deleted]  (3 children)

sorry, this has been archived and can no longer be voted on

[deleted]

[–] 1 point2 points  (1 child)

sorry, this has been archived and can no longer be voted on

Not just from 1996 -- it's been known for about a century that iteration of entire transcendental functions produces interesting sets. I suppose that not much has come of it since, but it would be interesting if the additional information present in such a map could be used to nail things down more. It would seem that Erdos was right, for now -- "Mathematics is not yet ripe for such problems."

[–] 9 points10 points  (1 child)

sorry, this has been archived and can no longer be voted on

Nice try, Numb3rs writers.

[–] 2 points3 points  (0 children)

sorry, this has been archived and can no longer be voted on

That show ended three years ago, dude.

[–]Algebraic Geometry 3 points4 points  (2 children)

sorry, this has been archived and can no longer be voted on

Using group theory to compute all possible rotations of a cube in 3 space.

[–] 1 point2 points  (1 child)

sorry, this has been archived and can no longer be voted on

Now do it for a rubik's cube!

[–] 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

And list all normal subgroups!

[–] 6 points7 points  (0 children)

sorry, this has been archived and can no longer be voted on

I'm an engineer in R&D, and spend a good fraction of my time doing math modeling. This happens to me pretty often. That said, my math knowledge tops out at DFEQs and vector Calc. Usually my slick math trick is recognizing that some integral is some transform I already know and doing it in my head. That or a change of variables and slick application of some multidimensional chain rule.

[–] 2 points3 points  (0 children)

sorry, this has been archived and can no longer be voted on

I used a power diagram to speed up a path-finding algorithm.

[–] 3 points4 points  (0 children)

sorry, this has been archived and can no longer be voted on

Last semester, I was drinking with some friends and playing BS (the card game). I was supposed to play 7s and I felt like an idiot because I had just lied and played my 7 as a 2. I then realized that I could quickly calculate a plan minimize the number of lies I tell as a matter of modulo arithmetic.

Pretty obvious in hindsight, but planning out your entire strategy in the opening minute feels really good.

[–] 2 points3 points  (0 children)

sorry, this has been archived and can no longer be voted on

My math TA last quarter in calc 3 used la grange multipliers to determine the optimal number of brews for tea leaves/ how much would be left in the leaves after each subsequent brew.

Unfortunately I didn't take notes that day or I'd share his methods.

[–] 2 points3 points  (0 children)

sorry, this has been archived and can no longer be voted on

I once saw a discussion of ways to catch a lion. I can only remember two. The first was rather resource intensive - you build a fence dividing the world in two. Identify which half the lion is in, and build a fence separating that half in two. Repeat until you have placed the lion in an area small enough to qualify as caught. Of course, you still need to prove that there exists a lion. The other solution, however, was definitely both easiest and my favourite. Get a cage. Stand in the cage, and invert with respect to the cage.

[–] 13 points14 points  (0 children)

sorry, this has been archived and can no longer be voted on

[–] 1 point2 points  (2 children)

sorry, this has been archived and can no longer be voted on

This is FAR less impressive and obscure than many of the other things in this thread, but I'm still a little proud of it.

A while back, I was making a Google Doc-based character sheet for New World of Darkness Changeling that would auto-calculate your XP expenditures, based on what you wanted your stats to be. The problem was that the XP rules were very weird. If you had 2 dots in an attribute, the cost to get the third was something like 15 (5*number of new dot). Getting a 4th dot in a skill would be 12 (3*number of new dot).

I stared at this in bafflement for a while before realizing that I was looking at a version of triangular numbers. One quick Google Search found me the equation for triangular numbers, and some algebra let me figure out how to get from "starting dots" to "total dots" (e.g. the XP cost to go from 2 dots to 4 dots in a skill), and voila!

Edit: Fixed formatting

[–] 1 point2 points  (1 child)

sorry, this has been archived and can no longer be voted on

You might want to escape your *s; they're causing reddit to italicize your text.

Like this: \*


Also, I can relate. I have a tendency to randomly remember "Oh, this sequence is important". I usually just use OEIS, though. I just had a not-so-shining moment with that technique earlier today: I came across a sequence that didn't seem very predictable, so I decided to search for it.

[–] 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

Thanks for the tip! That's what I get for not proof-reading after I submit.

This is the first I've heard of OEIS. Nice! Thanks for the note, as well!

[–] 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

Some abstract concepts that I've found are generally useful IRL are:

• compactness
• convexity
• computability
• polynomial time reduction
• isomorphism
• fixed points
• positive/null recurrence

[–] 0 points1 point  (0 children)

sorry, this has been archived and can no longer be voted on

I'm frequently sorting ~35 papers at a time for my class, and I wonder about the algorithm I use ad-hoc by using all the spacing between my fingers.