The Puzzle Thread!

[Sidoh]

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.

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?

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

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.

[dark_drake]

Why would perfect logicians hang out in a room with heads painted blue?

[Sidoh]

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).

[deadly7]

So Blue Man Group is perfect logicians?

[Sidoh]

So Blue Man Group is perfect logicians?

No, no.  The converse is not true.

[rabbit]

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.

[nslay]

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.

[Joe]

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.

[Falcon]

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 :)

[nslay]

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.

[Falcon]

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?

[Sidoh]

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?

[nslay]

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).

[rabbit]

I'm pretty sure this is The Puzzle Thread not The Math Thread.  Knock it off...

[Sidoh]

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