Thursday, October 11, 2012

Forehead Numbers Brain Teaser of Khan Academy

Today I remembered a little brainteaser I saw on Khan Academy quite a while back:  Khan Academy Link or Youtube Link

What surprises me though is that people still seem to think that there are values for which this can not be solved. My conjecture is that it CAN be solved for all 3-tuples of numbers provided that the participants know that they are unique.

I would recommend seeing the teaser and understanding the logic behind it before reading further.

3 years ago, when I first saw this, I posted a reply on Youtube describing the same 'game' from the perspective of a player who sees 15 and 11. For the sake of simplicity we'll call the player with 15 A and the one with 11 on his forehead C. Therefore the game is described from the perspective of B:
A-pass
B-pass
C-pass
A-pass
B-pass
C-pass
A-pass
B-pass
C-pass
A-figures out his number (15)
B-figures out his number also
C-figures out his number as well (11)

The question then is, what is B's number (obviously it's either 26 or 4 but which one)?

I'm still not going to give the answer, but what I'm going to do is explain it on a particular 3-tuple which somebody on Khan Academy says it's impimpossibleimpossibleossible: numbers 5 7 and 12.
Let's presume they are again named A B and C respectively, A starts.
A sees 7 and 12 therefore he can be either 5 or 19 (sum), since he doesn't know he passes.
B sees 5 and 12 therefore he can be either 7 or 17, doesn't know => passes
C sees 5 and 7, he can be 12 sure, but since he's a PERFECT LOGICIAN, he'll think what if he was 2 (the difference).

Let's see the game unfolding in C's mind, when he presumes that he's 2:
Numbers: 5 7 and 2
A - can be 5 or 9 - pass
B - can be 7 OR 3 - now B can presume that he's 3.
So, again, this is all unfolding in C's mind, B would've seen a 5 (A) and a 2 (what C thinks he might have) and there fore would've thought that he was 3. Then, in B's mind the game would've unfolded like this:
Numbers: 5 3 and 2
A - can be 5 or 1, so, like in the previous assumptions he can think what would've happen if he was one
Remember, just to keep track, we're explaining what C thinks of what B thinks of what A would think and I'm being dead serious about what I'm writing (even my head's starting to hurt).
So from A's mind:
Numbers 1 3 and 2
Now notice that we reach a solvable position: B can figure out his number, since he knows the numbers are unique (he can't be also 1). So again, from A's mind in B's mind in C's mind:
A - can be 5 or 1 - pass
B - can only be 3 (remember, A is 1 in this scenario) therefore he SHOULD know his number.

BUT! B said pass, which tells A that he can not be 1, therefore he must be 5 (if B was 3 and C was 2)

Now, coming back out of the mind of B from the mind of C, so back in our initial configuration (5 7 12)
C can not deduce his number so he passes and now we go onto the second round:
A passes
So now C thinks again, if he 2, B would've thought he was either 3 or 7 and furthermore, B would think that since A said pass, he can NOT be 3 (by the previous logic) therefore he's 7
But B passes what does this mean? it means that C is not 2, he's 12
So now C know's that he's 12 and he can safely say his number and receive a bag of kudos for being so smart (well not really).

So in the end, the game unfolds like this:
A = 5, B = 7, C = 12
A - pass
B - pass
C - pass

A - pass
B - pass
C - figures out he's 12

And then the other figure out their numbers as well - this is pretty trivial considering they are perfect logicians they can be either one of two options, so:

A - figures his number, 5
B - figures his number also, 7

Discussion:
If you managed to follow what happened then congrats! To be honest I have a hard time following, so it might be helpful to take a piece of paper in case you're struggling with the recursive nature of their thinking.
What I find it interesting is how much this resembles Euclid's algorithm for computing the GCD between two numbers. From what I can figure out, the game always ends no matter what numbers you choose - eventually they will presume that they are the smaller of the numbers  that they can be and will therefore reach a stage in which the "uniqueness" rule kicks in.

I'm also thinking what would happen if instead of having 2 possible options (sum and difference) we choose any number of functions that can be performed on two numbers. So say we have a game in which a player can be the sum, difference or the integral part of the average (integral part so that we only have natural numbers) of the other two. Also I'm wondering if using this the game can be extended to arbitrary numbers of players.

Thanks for reading :P

Sunday, September 16, 2012

Qyoto - C# bindings for Qt installation

I have recently taken an interest in C# and have been looking for a GUI toolkit to use. For development, I use MonoDevelop under Kubuntu. There are a few options, the three major ones seem to be Gtk#, Winforms and Qyoto. For me, Qyoto seems like a very good option especially since I have bit of a background using Qt with C++.

I haven't seen a lot of documentation online and if there is, it's a bit outdated. Therefore I have decided to write down my experience with the latest version it.

First of all I would recommend checking out the project's webpage on kde techbased: http://techbase.kde.org/Development/Languages/Qyoto

Now for installing, I strongly recommend you install both Qyoto AND Smoke (one of it's deps) from source. I've had problems trying to compile Qyoto using Ubuntu's packaged version of Smoke - so make sure that it's uninstalled first. You can download the git repos from here: https://projects.kde.org/projects/kde/kdebindings/smoke
First install smokegen, then smokeqt and finally install assemblygen (from https://gitorious.org/assemblygen). If you're unfamiliar with cmake, read below.

All of them use cmake so the build procedure is the same.
To install for example smokegen, clone the git repo (source) and then:
cd smokegen
mkdir build
cd build
cmake ../
// if cmake complains about deps, install them (qt4, phonon, mono, etc) and rerun cmake ../)
make
make install

If all has gone well, launch MonoDevelop, create a new Empty C# Project and add the qyoto-qtcore and qyoto-qtgui references. You'll notice that are many more, but for now these will suffice. Now the fun can begin.

Remember that the Main(String[]) function should look like:
{
new QApplication();
(new MainWindow()).Show(); // this is the custom class
QApplication.Exec();
}

Wednesday, May 16, 2012

Consciousness

Hello again, after quite some time, I decided again to write some of my thoughts on my little corner of the internet. The topics I'll write about are consciousness and intelligence along with bits and bobs I've read in my past time. Finally I'll describe a thought that came to me yesterday regarding the Halting Problem and if somebody (not "something") could solve it.

I should start with the idea of self-consciousness and how it could be described. The starting point for this, one could say, is the film "The Prestige". The film poses one interesting question, that is, "if I could copy all of the molecules in my body (in effect, perfect cloning) would there be any distinction between me and my clone?"
From the outside, of course, not. But! internally, there should still be the concept of a me and my clone.
My opinion is that there isn't such a concept. Think of it this way: let's say I have two pods, one of them painted red and one of them painted blue. Initially, both are empty. I enter the red pod, some "magic" happens and then my identical copy appears in the blue pod (notice that there isn't a strict need for shut doors or anything, so the whole process could be in plain sight). Now, one might argue that the "original" me is the one located in the red pod. But! What if the pods performed teleportation at the same time? "I" should then notice that somehow "I" ended up in the blue pod and then "I" would have to convince everyone of that. But what would my clone's perspective be? What if each time, the person in the blue pod, after the "magic" is completed, gets killed (which is what happens in the film). Who gets killed? Can even "I" know which is which?

Here's another thought: what if each time you go to sleep, a mage clones you replaces "you" with the clone and then kills "you" (notice that the first "you" is without quotes). Would 'you' be able to tell the difference when 'you' wake up? Probably no. The reason I used this "sleep" example is because that is a period when you lose consciousness. But here's another example that goes beyond sleep. What if the whole "mage that clones and replaces you" happens every plank-second or every individual quanta of time? Of course this would be physically impossible, but it sort of illustrates the point that there really is no such thing as self-consciousness.

Random ending: http://www.youtube.com/watch?v=dbh5l0b2-0o
Just a "documentary" I found, quite surprising graphics. Only agree with it until the gives that formula about consciousness, but in any case, it's pretty interesting considering the author, "Athene" (I was stunned when I googled him!)