An Interview Question: Dynamic Median Structure

October 30, 2013 § Leave a comment

While I was thinking about puzzles, I thought it might be nice to do something useful for my readers that actually want jobs (jobs in the technology industry, I mean). I was browsing the internet, and I came across an interview question that I myself have been asked before, and I think it is actually a pretty good technical question. Anyway, enough beating around the bush.

The problem is phrased as follows: you are to design a system (a datastructure, if you want to call it that) which can receive numeric elements as input and can deliver the median at any time as output.

Of course, this is somewhat open-ended as there are so many ways to accomplish this. Of course, that is what interviewers usually want, as it helps them (or so they claim) to take a look at your thought process. So, while I can not gauge your thought process, if you would like to benefit from this, you should find ways to optimize your structure. Try to see how much efficient of a solution you can deliver and how what trade-offs you might be able to make from time and space.

Thanks for reading!

-A Student of Logic

Advertisements

Puzzle: Magic Square

October 29, 2013 § 7 Comments

Hello Math people. I heard this puzzle a few weeks ago, and I thought it was pretty great. Here is how it goes:

You and a friend are playing a game against an adversary. The game is played as follows. You walk into a room with the adversary, leaving your friend outside. The room contains a checker board (the typical 8 by 8 kind), and each square has on it exactly one coin. Each coin can either be heads-up or tails-up. Then, the adversary chooses exactly one square which he calls the magic square. You, then, based on the arrangement of the coins and which square is the magic square, will choose exactly one square and turn its coin over (either from heads-up to tails-up or from tails-up to heads-up). Then, you will leave the room through a back door and wait in a separate room. Your partner then comes into the adversary’s room, looks at the board, and proceeds to take a guess at which square is the magic square. If your partner guesses correctly, you win.

Assuming you and your partner have no idea of what arrangement the board will be in when you enter the room, come up with a strategy for you and your partner to use so that you can always win.

Note: the only information you or your partner can have from looking at a coin is which square it is on and whether or not it is heads-up. The solution does not involve doing something silly by rotating the coins; the adversary chooses the orientation of the coin after you flip it.

Thanks for reading, and feel free to message me if you would like the answer!

-A Student of Logic

A Hopeless Problem: Can π + e or π – e be rational?

October 28, 2013 § Leave a comment

Today, I thought I would share a problem with you that, much like a lot of the things I will be posting, I heard from my Complexity Theory professor who inspired me to write this blog.

The problem is simple, and requires only a little bit of background information, so I will start with that.

First, a rational number is a number that can be expressed as the quotient a/b of two integers a and b where b≠0. We can add to the definition that a and b do not have common divisors as is useful when demonstrating that the square root of 2 is irrational.

From here, we can say that a real irrational number is a real number that can not be expressed as such. Much to the surprise of many people long ago and very few people now, there exist many of these (in fact, there are many more of these than there are rational numbers). Among these are the famous mathematical constants e and π.

It has been known for a very long time that each of these is irrational (proofs can be found on Wikipedia as well as many other places on the internet here and here), but shockingly, it remains unknown whether or not their sum or difference is irrational (that is, we do not know if π+e is rational, and we do not know if π-e is rational) . Peculiar, no?

What is even more interesting about this problem is that we can can conclude that at least one of their sum or difference is irrational rather easily. We simply assume that neither of them are irrational (so both of them are rational). Then, we have, because the rational numbers are closed under addition, that (π-e)+(π+e)=2π is rational. Because dividing a rational number by another non-zero rational number produces a rational number, we then get that π is rational. However, this contradicts the theorem that π is irrational, so we can conclude that π+e and π-e can not both be rational. Of course, most people, if not all people, who think about this would probably guess with a high degree of certainty that neither of these numbers are rational, and yet, we find ourselves hopeless to prove it.

Additionally, because π and e are each transcendental (meaning not algebraic), as well, and algebraic numbers are closed under the same operations we used in our proof, we find that at least one of the sum or difference must be transcendental, as well.

Thanks for reading!

-A Student of Logic

Hello, World!

October 27, 2013 § Leave a comment

Today is the day which I make my first post, and today is almost certainly not the day that I will have figured out what I am doing. Because of this, I will take a minute to describe what I may very well end up doing with this blog. First, however, I will give a small, relevant portion of my background.

I consider myself to be a student of Logic and someone who would very much like to earn the title of Logician someday. I am, however, not in any explicit sense a student of Logic. I am enrolled in an engineering school as a student of Computer Science and Mathematics. While my school is very strong in Theoretical Computer Science and some Mathematics, I (probably uniquely) feel a great sense of shame and disappointment that my current institution offers no support for studying pure Logic.

That being said, I do not intend to exclusively talk about only pure Logic. I anticipate that most of the interest from my readers will be in Computer Science, and this is also the realm containing most of the interesting things that I know or care to talk about. Of course, I am not really writing these things for anyone but myself at the moment, so do not be surprised when I post something that seems totally inapplicable in all ways to anything anyone really cares about.

Thanks for reading!

-A Student of Logic

Where Am I?

You are currently viewing the archives for October, 2013 at A Student of Logic.