Author Topic: The Puzzle Thread!  (Read 7544 times)

0 Members and 1 Guest are viewing this topic.

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17668
  • MHNATY ~~~~~
    • View Profile
    • sidoh
The Puzzle Thread!
« on: March 17, 2011, 04:29:31 PM »
Lots of smart people here.  This calls for a puzzles thread.  I've heard a few new (and old) ones recently, and thought I'd share.  Here's how I'm gonna run it:

1. All puzzles will be listed in this post.  I'll edit the post to add new ones.  Add a post/send a PM and I'll add yours to this post.
2. PM answers, add posts to ask questions.
3. I'll indicate who has solved each of the puzzles underneath it.

Let's do this.

Quote
You gather 100 perfect logicians. You tell all of them the following:
  • They will be placed in a room with 99 other perfect logicians, in a circle so they can all see eachother
  • Their head will be painted a particular color; they cannot see the color of their own head, but everyone else can
  • At least one of the hundred's head's will be painted blue
  • You will flip the lights on and off
  • If they figure out their head is painted blue, they must leave next time the lights go off
  • They are not allowed to talk or signal each other in any way. They may only observe the others, and leave if/when they figure out their head is blue.

You proceed to paint all of their heads blue, and begin the exercise. What happens, if anything, and when?

Quote
Prove or disprove: you can completely fill a cube with finitely many smaller, all-differently-sized cubes.

Quote
You have 100 pennies.  Exactly 50 of them a heads-up, but you don't know which ones.  If you're blindfolded, how would you divide the pennies up into two groups with an equal number of heads?  Repeat the same exercise when exactly 10 of them are heads-up.  You're not allowed to feel the pennies to test if they're heads up.  Say you're only allowed to touch the pennies by gripping them on the edges.
SOLVED BY: dark_drake

I came across this problem recently

Given [latex]\{ f_m(\mathbf{x}) \}_{m=1}^M,\ f_m(\mathbf{x})\ :\ X \subseteq \mathbb{R}^n \to \mathbb{R}[/latex] and denote
[latex]
\mathbf{f}(\mathbf{x}) = \begin{bmatrix} f_1(\mathbf{x}) & f_2(\mathbf{x}) & ... & f_M(\mathbf{x}) \end{bmatrix}^T
[/latex]

Under what assumptions is the matrix
[latex]
H = \int_X \mathbf{f}(\mathbf{x}) \mathbf{f}(\mathbf{x})^T d \mathbf{x}
[/latex]
strictly positive definite? Here integration is component-wise.
« Last Edit: March 18, 2011, 04:20:55 PM by Sidoh »

Offline dark_drake

  • Mufasa was 10x the lion Simba was.
  • x86
  • Hero Member
  • *****
  • Posts: 2447
  • Dun dun dun
    • View Profile
Re: The Puzzle Thread!
« Reply #1 on: March 17, 2011, 09:37:52 PM »
Why would perfect logicians hang out in a room with heads painted blue?
errr... something like that...

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17668
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: The Puzzle Thread!
« Reply #2 on: March 17, 2011, 10:55:14 PM »
Why would perfect logicians hang out in a room with heads painted blue?

All perfect logicians hang out in a room with their heads painted blue (or red).

Offline deadly7

  • 42
  • x86
  • Hero Member
  • *****
  • Posts: 6496
    • View Profile
Re: The Puzzle Thread!
« Reply #3 on: March 17, 2011, 11:33:28 PM »
So Blue Man Group is perfect logicians?
[17:42:21.609] <Ergot> Kutsuju you're girlfrieds pussy must be a 403 error for you
 [17:42:25.585] <Ergot> FORBIDDEN

on IRC playing T&T++
<iago> He is unarmed
<Hitmen> he has no arms?!

on AIM with a drunk mythix:
(00:50:05) Mythix: Deadly
(00:50:11) Mythix: I'm going to fuck that red dot out of your head.
(00:50:15) Mythix: with my nine

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17668
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: The Puzzle Thread!
« Reply #4 on: March 18, 2011, 12:07:08 AM »
So Blue Man Group is perfect logicians?

No, no.  The converse is not true.

Offline rabbit

  • x86
  • Hero Member
  • *****
  • Posts: 8098
  • I speak for the entire clan (except Joe)
    • View Profile
Re: The Puzzle Thread!
« Reply #5 on: March 18, 2011, 08:17:14 AM »
I object.  nslay's "puzzle" is really just advanced math, while the others are cleverly disguised math.  I demand he reword the "puzzle" into a word problem involving logicians and hats.

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: The Puzzle Thread!
« Reply #6 on: March 18, 2011, 10:15:48 AM »
I object.  nslay's "puzzle" is really just advanced math, while the others are cleverly disguised math.  I demand he reword the "puzzle" into a word problem involving logicians and hats.

It turns out to be very easy if approached the right way. It took me a while to figure out anyway.
An adorable giant isopod!

Offline Joe

  • B&
  • x86
  • Hero Member
  • *****
  • Posts: 10320
  • In Soviet Russia, text read you!
    • View Profile
    • William's Blog
Re: The Puzzle Thread!
« Reply #7 on: March 18, 2011, 11:31:29 AM »
Quote
You have 100 pennies.  Exactly 50 of them a heads-up, but you don't know which ones.  If you're blindfolded, how would you divide the pennies up into two groups with an equal number of heads?  Repeat the same exercise when exactly 10 of them are heads-up.

By feeling the pennies. I probably couldn't do it, but my blind friend Kevin probably could easily.

Where is DD's solution? It's early but I don't see it in the thread.
I'd personally do as Joe suggests

You might be right about that, Joe.


Offline Falcon

  • Full Member
  • ***
  • Posts: 241
  • I haven't visited my profile!
    • View Profile
Re: The Puzzle Thread!
« Reply #8 on: March 18, 2011, 12:21:45 PM »
Quote
You have 100 pennies.  Exactly 50 of them a heads-up, but you don't know which ones.  If you're blindfolded, how would you divide the pennies up into two groups with an equal number of heads?  Repeat the same exercise when exactly 10 of them are heads-up.

By feeling the pennies. I probably couldn't do it, but my blind friend Kevin probably could easily.

Where is DD's solution? It's early but I don't see it in the thread.
2. PM answers, add posts to ask questions.

Whats the point of it if we can already see solutions? ;)

And I agree with rabbit and object to nslay's thing being a puzzle, it is just a pure math problem you have to work backwards to get the solution from, given the conditions. Sidoh's original puzzles don't require any complex math, just simple reasoning and deduction to get a solution. In order to solve the math problem you would have to know some advanced math to understand the notations used to describe the problem, not to mention a knowledge of linear algebra to understand matrices and their transpose and properties of them. O yea and integration also, not to mention it just isn't even interesting to solve! Therefore I demand it to be removed thanks :)
« Last Edit: March 18, 2011, 02:05:25 PM by Falcon »

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: The Puzzle Thread!
« Reply #9 on: March 18, 2011, 02:45:38 PM »
Quote
You have 100 pennies.  Exactly 50 of them a heads-up, but you don't know which ones.  If you're blindfolded, how would you divide the pennies up into two groups with an equal number of heads?  Repeat the same exercise when exactly 10 of them are heads-up.

By feeling the pennies. I probably couldn't do it, but my blind friend Kevin probably could easily.

Where is DD's solution? It's early but I don't see it in the thread.
2. PM answers, add posts to ask questions.

Whats the point of it if we can already see solutions? ;)

And I agree with rabbit and object to nslay's thing being a puzzle, it is just a pure math problem you have to work backwards to get the solution from, given the conditions. Sidoh's original puzzles don't require any complex math, just simple reasoning and deduction to get a solution. In order to solve the math problem you would have to know some advanced math to understand the notations used to describe the problem, not to mention a knowledge of linear algebra to understand matrices and their transpose and properties of them. O yea and integration also, not to mention it just isn't even interesting to solve! Therefore I demand it to be removed thanks :)

On the contrary, it is very interesting in the sense of optimization. If you had a Hessian of that form (which I did), positive definiteness would imply strict convexity and therefore a unique global optimum.

The reasoning probably isn't as simple as you think it is. There's a twist and you probably didn't realize it.

EDIT: Oh, I misread. You were talking about Sidoh's puzzle. Nah, this really does boil down to really simple math. You're just intimidated by linear algebra and integration (which really are basic math). But as I said, there is a twist.
« Last Edit: March 18, 2011, 02:50:39 PM by nslay »
An adorable giant isopod!

Offline Falcon

  • Full Member
  • ***
  • Posts: 241
  • I haven't visited my profile!
    • View Profile
Re: The Puzzle Thread!
« Reply #10 on: March 18, 2011, 03:34:38 PM »
Quote
You have 100 pennies.  Exactly 50 of them a heads-up, but you don't know which ones.  If you're blindfolded, how would you divide the pennies up into two groups with an equal number of heads?  Repeat the same exercise when exactly 10 of them are heads-up.

By feeling the pennies. I probably couldn't do it, but my blind friend Kevin probably could easily.

Where is DD's solution? It's early but I don't see it in the thread.
2. PM answers, add posts to ask questions.

Whats the point of it if we can already see solutions? ;)

And I agree with rabbit and object to nslay's thing being a puzzle, it is just a pure math problem you have to work backwards to get the solution from, given the conditions. Sidoh's original puzzles don't require any complex math, just simple reasoning and deduction to get a solution. In order to solve the math problem you would have to know some advanced math to understand the notations used to describe the problem, not to mention a knowledge of linear algebra to understand matrices and their transpose and properties of them. O yea and integration also, not to mention it just isn't even interesting to solve! Therefore I demand it to be removed thanks :)

On the contrary, it is very interesting in the sense of optimization. If you had a Hessian of that form (which I did), positive definiteness would imply strict convexity and therefore a unique global optimum.

The reasoning probably isn't as simple as you think it is. There's a twist and you probably didn't realize it.

EDIT: Oh, I misread. You were talking about Sidoh's puzzle. Nah, this really does boil down to really simple math. You're just intimidated by linear algebra and integration (which really are basic math). But as I said, there is a twist.
Since it contains real values wouldn't f(x)f(x)T be positive-semidefinite? and in order to be positive-definite f(x) needs to be linearly independent. Probably not correct but thats all I can remember from linear algebra.

I'm not intimidated by math, just that I don't find pure math interesting. Now if you put that into a problem (optimization) that's a different story. And if linear algebra and calculus are considered basic math, then what is addition, subtraction, algebra? Dumbass math?

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17668
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: The Puzzle Thread!
« Reply #11 on: March 18, 2011, 04:04:46 PM »
Quote
You have 100 pennies.  Exactly 50 of them a heads-up, but you don't know which ones.  If you're blindfolded, how would you divide the pennies up into two groups with an equal number of heads?  Repeat the same exercise when exactly 10 of them are heads-up.

By feeling the pennies. I probably couldn't do it, but my blind friend Kevin probably could easily.

Where is DD's solution? It's early but I don't see it in the thread.
2. PM answers, add posts to ask questions.

Whats the point of it if we can already see solutions? ;)

And I agree with rabbit and object to nslay's thing being a puzzle, it is just a pure math problem you have to work backwards to get the solution from, given the conditions. Sidoh's original puzzles don't require any complex math, just simple reasoning and deduction to get a solution. In order to solve the math problem you would have to know some advanced math to understand the notations used to describe the problem, not to mention a knowledge of linear algebra to understand matrices and their transpose and properties of them. O yea and integration also, not to mention it just isn't even interesting to solve! Therefore I demand it to be removed thanks :)

On the contrary, it is very interesting in the sense of optimization. If you had a Hessian of that form (which I did), positive definiteness would imply strict convexity and therefore a unique global optimum.

The reasoning probably isn't as simple as you think it is. There's a twist and you probably didn't realize it.

EDIT: Oh, I misread. You were talking about Sidoh's puzzle. Nah, this really does boil down to really simple math. You're just intimidated by linear algebra and integration (which really are basic math). But as I said, there is a twist.
Since it contains real values wouldn't f(x)f(x)T be positive-semidefinite? and in order to be positive-definite f(x) needs to be linearly independent. Probably not correct but thats all I can remember from linear algebra.

I'm not intimidated by math, just that I don't find pure math interesting. Now if you put that into a problem (optimization) that's a different story. And if linear algebra and calculus are considered basic math, then what is addition, subtraction, algebra? Dumbass math?

Algebra is one of the most heavily-populated branches in math.  People get PhDs in math studying algebraic topics.

As for the puzzle, I don't really see what harm it's doing.  If you don't find it interesting, then don't do it.  It's really pretty simple, isn't it?

Offline nslay

  • Hero Member
  • *****
  • Posts: 786
  • Giraffe meat, mmm
    • View Profile
Re: The Puzzle Thread!
« Reply #12 on: March 18, 2011, 05:15:02 PM »
Quote
You have 100 pennies.  Exactly 50 of them a heads-up, but you don't know which ones.  If you're blindfolded, how would you divide the pennies up into two groups with an equal number of heads?  Repeat the same exercise when exactly 10 of them are heads-up.

By feeling the pennies. I probably couldn't do it, but my blind friend Kevin probably could easily.

Where is DD's solution? It's early but I don't see it in the thread.
2. PM answers, add posts to ask questions.

Whats the point of it if we can already see solutions? ;)

And I agree with rabbit and object to nslay's thing being a puzzle, it is just a pure math problem you have to work backwards to get the solution from, given the conditions. Sidoh's original puzzles don't require any complex math, just simple reasoning and deduction to get a solution. In order to solve the math problem you would have to know some advanced math to understand the notations used to describe the problem, not to mention a knowledge of linear algebra to understand matrices and their transpose and properties of them. O yea and integration also, not to mention it just isn't even interesting to solve! Therefore I demand it to be removed thanks :)

On the contrary, it is very interesting in the sense of optimization. If you had a Hessian of that form (which I did), positive definiteness would imply strict convexity and therefore a unique global optimum.

The reasoning probably isn't as simple as you think it is. There's a twist and you probably didn't realize it.

EDIT: Oh, I misread. You were talking about Sidoh's puzzle. Nah, this really does boil down to really simple math. You're just intimidated by linear algebra and integration (which really are basic math). But as I said, there is a twist.
Since it contains real values wouldn't f(x)f(x)T be positive-semidefinite? and in order to be positive-definite f(x) needs to be linearly independent. Probably not correct but thats all I can remember from linear algebra.

I'm not intimidated by math, just that I don't find pure math interesting. Now if you put that into a problem (optimization) that's a different story. And if linear algebra and calculus are considered basic math, then what is addition, subtraction, algebra? Dumbass math?

Indeed, you do get positive semidefinite for free. However, you're still only half right about linear independence (and this got me too!).

Here is an example of linearly independent functions where said integral isn't strictly positive definite.
[latex]
f_1(x) = \sin(x) \\
f_2(x) = \begin{cases}
\sin(x) & x \neq 0
1 & x = 0
\end{cases}
[/latex]

So
[latex]
\begin{bmatrix} 1 & -1 \end{bmatrix} \int_{-\pi}^{\pi} \mathbf{f}(x) \mathbf{f}(x)^T d x \begin{bmatrix} 1 \\ -1 \end{bmatrix} = \begin{bmatrix} 1 & -1 \end{bmatrix} \int_{-\pi}^0 \mathbf{f}(x) \mathbf{f}(x)^T dx \begin{bmatrix} 1 \\ -1 \end{bmatrix} + \begin{bmatrix} 1 & -1 \end{bmatrix} \int_0^{\pi} \mathbf{f}(x) \mathbf{f}(x)^T dx \begin{bmatrix} 1 \\ -1 \end{bmatrix} = 0
[/latex]

One has to additionally say that the functions are linearly dependent only on a set with zero measure. I totally ruined it, but that's the twist!

I asked this question because it is both counter-intuitive (integral of rank 1 matrix somehow giving full rank matrix result) and it's also deceptively obvious once you do exploit linear independence (because one has to remember the twist).
An adorable giant isopod!

Offline rabbit

  • x86
  • Hero Member
  • *****
  • Posts: 8098
  • I speak for the entire clan (except Joe)
    • View Profile
Re: The Puzzle Thread!
« Reply #13 on: March 18, 2011, 08:46:48 PM »
I'm pretty sure this is The Puzzle Thread not The Math Thread.  Knock it off...

Offline Sidoh

  • x86
  • Hero Member
  • *****
  • Posts: 17668
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: The Puzzle Thread!
« Reply #14 on: March 18, 2011, 08:48:57 PM »
I'm pretty sure this is The Puzzle Thread not The Math Thread.  Knock it off...

Math puzzles are a subset of puzzles!  There's no need to be hostile.  If you don't like the math puzzles, don't do them! :D