Author |
Topic: Unsolved Problems in the Hard Forum (Read 45191 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Unsolved Problems in the Hard Forum
« on: Jul 23rd, 2003, 9:01pm » |
 Quote  Modify
|
New Stuff
Puzzles with no solution to the original problem (but likely to be solvable).
Puzzles with possible solutions, solutions not clearly demonstrated, or solutions which have been seriously contested.
Puzzles with incomplete solutions (but likely completable.)
- Last Man Standing. SWF has come up with a surprising statistical result. The ultimate goal has not yet been reached, though.
- Arrange the 13 pieces. Rezyk has resurrected SWF's unlucky dissection from obscurity. But SWF indicates that his inventive solution to the second part was not the intended square.
- A math puzzler from Barukh, Random Exponentiation, is solved - provided you don't mind glossing over those piddling little details... For those with a mind for completeness, this one is diving into some advanced number theory. Can you prove Wutang's Conjecture? [wutang]
- Tunnels of Callicrates.
- Random Line Segment In Square. SWF has found a good Large number approximation. Is a formula for smaller N feasible?
- Growing Number Sequence. James has given the means for defining this sequence now, but no nice formula has yet been found.
- Seating Couples. Hyperdex has offered a partial solution to this one, but no one has ever finished it.
- Recurrence relation divisibility. Another partial solution from hyperdex.
- "Erik's Puzzle" (Conway's Game of Life). The answer to the higher dimensional problem has been found (almost certainly), but not proven.
- Perpetual Motion (Basic Chemistry). James' final post to this thread he started suggests that SWF' solution to problem #2 is incomplete, but no-one has addressed the question.
- Firing Squad Synchronization. Another masterful contribution by James to the solution, but not a complete solution.
- How Far Can a Truck Go, Carrying Its Own Fuel?. Can someone find a strategy that beats James', or show that James' is optimal?
- Coin Flip Game Worth. AlexH has made some serious inroads, but suggests that better is possible.
- Fitting Circles In A Rectangle . James Fingas's answer is supported by a simulation. Does anyone want to try for something more rigorous?
- Three Dimensional Random Walk. Again, lots of calcuation, but no final word on the matter.
Puzzles with incomplete solutions (and unlikely to ever be completed.)
- Language Proficiency Verification. No final answer.
- HARD: Hamming Distance Questions. This one is an unsolved problem in mathematics. Solve it and your name will be known throughout history! (Okay - only to a rare few die-hard math history nerds, but hey, what do you expect?)
- HARD: Cigarettes Max Clique.
- Rubik's Cube. Another one that has been the focus of mathematical research without finding a complete answer. It's unlikely one will be found here, but maybe someone knows sharper results than those already quoted (and can back them up with links)?
- Worm Propagation. TenaliRaman has breathed a little new life in this one. Maybe I'll get to remove it after all!
- 100 Prisoners & a Light Bulb?. The "Optimal" solution has still not been discovered, or at least not proven. I also rate this one as unlikely to ever have a complete answer, though new progress keeps being made!
- 100 prisoners and no lightbulb. A variation of the classic, the author has never answered Chronos' request for a clarification. Without it this one may be dead in the water.
- 100 PRISONERS AND TWO LIGHT BULBS. Another variation on the classic. With that extra bulb come some other changes that make this a tougher job than the original. Optimality is still far away.
Solved puzzles with open side challenges.
- 10-adic numbers, still has a follow-up question concerning "bidirectional numbers" open.
- Coins on a Table: Progress has been made on Barukh's generalization, but a full solution is not yet shown.
- The Lion and the Lion Tamer. This puzzle was thought to be solved, until Barukh demonstrated that the opposite answer was in fact true! In addition to pointing this out, Barukh has added another question concerning lines.
- Three-way Pistol Duel . While the main question has long been solved, there is a multi-shooter question that is unanswered.
- HARD: GREEDY PIRATES. The original question is solved (though the best answer,999 coins, has been posted without explanation), but I proposed a variation which is much harder than the original. James Fingas and rmsgrey have made some inroads, but a final answer is still unknown. Rmsgrey has also raised the question of what happens with more than 5 pirates in the original version.
- Brick piercing. With his solution TimMann gives a follow-up question no one has touched.
- Shuffling cards into order. The original is solved, but the general equation for out-shuffles has not been found.
- A simple game. The original problem is solved but the follow up question Jonathan_The_Red asks is not touched.
Latest Changes (11/11/03):- Moved the Change History to a separate post.
- Removed Filling a Box with Cubes now that Tohuvabohu's proof for the infinite case has been completed.
- Moved "Coins on a Table" to the "Solved with open side challenges" section.
- Removed Beautiful Chess Puzzle since it has been solved. T&B posted a second problem there, but it should be given a thread of its own if anyone wants to solve it.
- Moved "Cutting A Box From Triangular Stock" to the "Partial or Disputed solutions" section.
- Removed Prisms. I'll go along with James & aero_guy on this one.
- Removed Generating Random Trees. James clears another off.
- Removed Collision With Row Of Spheres. Score another for James, while I got bit by differing terminology.
- Removed 12 balls - variation. TimMann & Rujith polished it off.
- Removed Ellipsoid Power Generation. There may still be more to the story, but I've decided to withdraw my objection.
- Removed Particle Time after rereading the thread. The objection I had raised in it turns out to have been answered early on. (I'm rather surprised no one called me on it!)
- Moved "Last Man Standing" to the "incomplete but likely completable" category, as SWF has made a very significant contribution.
- Replenished the new stuff.
Link to Change History. (Or you could just scroll down to the 12th post!  )
|
| « Last Edit: Nov 15th, 2003, 7:42am by Icarus » |
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #1 on: Jul 23rd, 2003, 10:29pm » |
Quote Modify
|
Damn, thanks. This will help direct efforts. Must have taken a while too.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #2 on: Jul 24th, 2003, 11:07pm » |
Quote Modify
|
Great work, Icarus! This list will be very helpful to keep track of the riddles that slip through the cracks.
The Intersecting Spheres problem looks like it was first solved by cho. There was much sidetrack discussion and debate in the thread, but the question asked was simple and cho answered it.
Many of the hard problems are not likely to ever be solved fully in this forum, and separating these from the more tractable problems would be useful. It would also be nice to include some sort of status, such as "best 100 prisoners and lightbulb solution so far takes 3536 days", but I guess it is tough to verify the accuracy of such claims. Unfortunately, the prisoners and lightbulb thread was taken over by repeated irrelvant suggestions from posters who did not read the thread and any serious solution posted there is likely to get buried in posts suggesting to break the bulb into 100 pieces.
|
|
IP Logged |
|
|
|
Lightboxes
Full Member
Gender:
Posts: 203
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #3 on: Aug 13th, 2003, 9:10pm » |
Quote Modify
|
... Quote:| by repeated irrelvant suggestions from posters who did not read the thread and any serious solution posted there is likely to get buried in posts suggesting to break the bulb into 100 pieces. |
|
Hey!, I was new here, I didn't know how to approach these problems.  And I do regret it okay! sheesh. Hehe
|
|
IP Logged |
A job is not worth doing unless it's worth doing well.
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #5 on: Sep 23rd, 2003, 1:28pm » |
Quote Modify
|
For Fitting Circles in Rectangles: my solution is, of course, correct, and my diameter is almost perfectly optimal, but I would like to point out that I proposed a side question that hasn't been answered (reply #7 in that thread). What if M and N weren't restricted to integers?
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #6 on: Sep 23rd, 2003, 6:00pm » |
Quote Modify
|
Okay! Okay! Okay! I know I've been letting this slide! I actually started on an update last weekend, but got sidetracked while investigating a posted solution, and never got back to it. Unfortunately, I'm having connection problems, so I may not be able to get to it tonight either.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #7 on: Sep 23rd, 2003, 6:25pm » |
Quote Modify
|
Icarus, since you are updating, I think you should reconsider whether the following are unsolved: Tunnels of Callicrates (although when the question is not clear, it is hard to tell when it has been answered), Language Proficiency Verification, Random Line Segment in Square, and Infinite Checkerboard.
Also, how about putting the date of last update in the subject title. Since your changes are edits, they do not register as a new post to the thread and may otherwise go unnoticed.
There are unsolved problems in the Easy and Medium section too. Maybe they should be moved to Hard.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #8 on: Sep 23rd, 2003, 6:55pm » |
Quote Modify
|
I was unsure about that. Every so often a thread will move to the front of the forum, but when I look in it, I don't see any new posts. I had assumed this was the result of someone modifying their post.
Now I realize (because of an incident while fixing thread titles in the Easy forum) what must be happening: if you post to a thread and then immediately delete it, the thread still gets counted as "modified".
So what I will do is: every time I modify the list, I will also add and delete a blank post. That should bring up the "new" flag for everyone. Of course - this requires that I buckle down and work through figuring out what all needs to be changed!  That's what I get for doing something ambitious once.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #9 on: Sep 24th, 2003, 9:44am » |
Quote Modify
|
Yeah ... while you're slaving away being ambitious and all, I'm working hard keeping everybody's expectations low.
If nobody thinks you're going to do anything, you don't have to!
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Rujith de Silva
Newbie
Gender:
Posts: 22
|
|
Updated 12-balls (variation)
« Reply #10 on: Oct 14th, 2003, 9:22am » |
Quote Modify
|
I provided the answer for redPepper's extension to the 12-ball (variation), so this can probably be removed from the Unsolved Riddles. Thanks for putting together this list, by the way! - Rujith.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #11 on: Oct 14th, 2003, 7:58pm » |
Quote Modify
|
I'll get it in my next update - which may be a while yet. I've got to find some spare time when I am not also feeling the call of other things. These are few and far between.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #12 on: Nov 11th, 2003, 6:59pm » |
Quote Modify
|
Change History
9/25/03: I moved Robin Friberg's crypto puzzles to the medium thread, so while BNC's reply crypto remains unsolved, it is no longer "Hard". SWF has solved Jamie's Poor Willy. Removed Infinite Checkerboard, although there is a side problem with no POSTED solution, I'm trusting Eric's statement that it is almose trivial from James' last post. Several category changes. Updated "New Stuff".
9/14/03: Removed Littlewood's Number game, as SWF has posted a good solution. Also updated some thread names.
8/16/03: Removed Willy's true colors, as it is now solved. Added the "New Stuff" section, to keep track of new problems that look like they might be around for a while.
8/3/03: Removed Another Fork In The Road, as SWF has posted the solution. Also included the side question Barukh has posted in the Lion Tamer puzzle.
7/29/03: Removed Intersecting Spheres after convincing myself that Cho is correct. Also added this history, to make it easier to see what changes have been made.
7/28/03: Removed the Crazy Christmas Game, since SWF has posted a solution. I also reorganized the problems into categories, as SWF suggested. Thanks to William for making the thread sticky.
7/24/03: After rereading the Sleeping Beauty thread in response to Rmsgrey's new post, I see that it is among the solved puzzles for which I failed to notice the solution when scanning to create this list. I have removed it.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
pjay
Newbie
Gender:
Posts: 30
|
|
convex set projection
« Reply #13 on: Dec 3rd, 2003, 4:43am » |
Quote Modify
|
my knee-jerk reaction to this problem is to triangulate the boundary of the convex set, but then i realized that the existence of a triangulation is not obvious and hard to prove, so i tried to think of another way. after looking at the hints it seems clear that willie is suggesting the triangulation approach. a comment before i proceed: i think maybe it should be stated that you can assume that the boundary of any convex set can be triangulated with arbitrarily small triangles? maybe this gives away too much?? dunno.
anyways, here goes. take the dot product of 2 unit vectors to get cos(x) where x is the angle between them. letting one vector roam over a sphere and integrating we get:
\int_0^\pi (2\pi cos(x)sin(x))/4\pi dx. use the identity
2 cos(x)sin(x)=sin(2x) to see that the above is equal to 1/4. now let the other vectot represent the height of a given triangle in the triangulation (as in a riemann sum approximation). by integrating over the triangle we get A/4 where A is the area of the triangle. now by taking the limit of triangulations we are done...
|
|
IP Logged |
|
|
|
neopetsaddict
Newbie
Posts: 1
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #14 on: Jan 5th, 2005, 9:40am » |
Quote Modify
|
 ahhh could someone please help me ...for 2 weeks ive been trying to figure this riddle i cant .....(((riddle is what do u feed a sick bird....))) oh by the way im new this place looks kinda cool i love riddles but this one has stumped me big time
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #15 on: Jan 5th, 2005, 10:51am » |
Quote Modify
|
Neo, in the future please post such problems in a different section of the forum; this thread is for problems that have not been resolved after a long period of time.
Answer: Tweetment!
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #16 on: Jan 5th, 2005, 11:38am » |
Quote Modify
|
on Jan 5th, 2005, 9:40am, neopetsaddict wrote: what do u feed a sick bird....))) i love riddles but this one has stumped me big time
|
|
Well, it helps if you get the wording right.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #17 on: Mar 21st, 2005, 1:15am » |
Quote Modify
|
LOGICAL NONSENSE
LEMMAS:
Contrapositive
(i) A => B = B' => A'
de Morgan's laws
(ii) (A or B)' = A' and B'
(iii) (A and B)' = A' or B'
(iv)
(A => B) and (C => D)
implies
(A and C) => (B and D)
(v)
(A and B) => (C and B)
implies
(A => C)
(vi)
(A and B) => C
and
(D and E) => C'
implies
(A and B and D) => E'
(vii)
(A and B) => C
and
(C' and B) => A
implies
B'
-----------------------------------------
Let
D = Dance on tight-ropes
E = Eat penny-buns
Y = Young (equals 'not old')
G = liable to Giddiness
T = Treated with respect
W = Wise
B = go up in Balloons
U = takes an Umbrella
R = look Ridiculous
L = may Lunch in public
F = Fat
Rewrite the statements as:
1) D' and E' => Y'
1a) (D or E)' => Y' (de Morgan)
1b) Y => D or E (contrapositive)
2) P and G => T
3) W and B => U
4) R and E => L'
4a) L => (R and E)' (contrapositive)
5) Y and B => G
6) F and R and D' => L
7) W and G => D'
8) P and U => R
9) D' and T => F
Eliminating E from 1b) and 4a) using (iv) we get
10) Y and L and R => D
Eliminating T from 2) and 9) using (iv) we get
11) P and G and D' => F
Eliminating U from 3) and 8) using (iv) we get
12) W and P and B => R
Combining 6) and 11) using (iv) we get
13) P and G and R and D' => L
Combining 10) and 13) using (iv) and (vii) we get
14) Y and P and G => R'
Combining 12) and 14) using (vi) we get
15) W and P and B and G => Y'
So we now have
5) Y and B => G
7) W and G => D'
15) W and P and B and G => Y'
From 5)
Y => B' or G
From 7)
W => D' or G'
From 15)
W and P and Y => B' or G'
Adding,
W and Y and P => B' and (D' or G') (by (iv))
=> B' and (D and G)' (by de Morgan)
=> [(B or (D and G)]' (by de Morgan)
Hence B or (D and G) => (W and Y and P)' (by contrapositive)
Therefore no wise young pigs are balloonists or (dance on tightropes and are liable to giddiness).
|
| « Last Edit: Mar 22nd, 2005, 10:22pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #18 on: Mar 21st, 2005, 5:36am » |
Quote Modify
|
on Mar 21st, 2005, 1:15am, THUDandBLUNDER wrote:LEMMAS:
(v)
(A and B) => (C and B)
implies
(A => C)
(vii)
(A and B) => C
and
(C' and B) => A
implies
B'
|
|
Can you prove these lemmas?
Because I don't think they're true..
(for (v) take A=true, B=C=false, for (vii) take A=B=C=true)
|
| « Last Edit: Mar 21st, 2005, 5:38am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #19 on: Mar 21st, 2005, 6:31am » |
Quote Modify
|
on Mar 21st, 2005, 5:36am, towr wrote:
Can you prove these lemmas?
Because I don't think they're true..
(for (v) take A=true, B=C=false, for (vii) take A=B=C=true) |
|
A means A is true (given).
A' means A is false.
For (vii)
A and B => C
C' and B => A => A and B => C
Contradiction;
Therefore B'
|
| « Last Edit: Mar 21st, 2005, 1:14pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #20 on: Mar 22nd, 2005, 6:39am » |
Quote Modify
|
It's not clear how "C' and B => A => A and B => C" is to be read.
Besides, a truth table shows that
([(A and B) => C] and [(C' and B) => A]) implies B'
isn't a valid schema.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #21 on: Mar 22nd, 2005, 6:58am » |
Quote Modify
|
Actually, looking at it, the contradiction appears to be valid, meaning that the premise must be false. The error appears to lie in only considering part of the premise - I get
B' or C
as the correct conclusion.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #22 on: Mar 23rd, 2005, 1:12am » |
Quote Modify
|
Well spotted, towr and rmsgrey.
Hence we have
(A and B)' or (C' and B)'
equals
(A' or B') or (C or B') (de Morgan)
equals
A' or (B' or C)
But as
A' => (B and C')' (contrapositive)
equals
(B' or C) (de Morgan)
we can conclude simply A', can we not?
But wait, if (C' and B) is false then we cannot use the contapositive, right?
Jeez, I used to think this stuff was easy!
|
| « Last Edit: Mar 23rd, 2005, 10:31am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #23 on: Mar 23rd, 2005, 7:03am » |
Quote Modify
|
on Mar 23rd, 2005, 1:12am, THUDandBLUNDER wrote:| we can conclude simply A', can we not? |
|
You have:
A' or D
and
A' => D
where D is (B' or C)
they can be rewritten as:
(A and D')' (de Morgan)
and
(A' and D) or (A and D) or (A and D')
which gives:
(A' and D) or (A and D)
which rearranges to:
(A or A') and D
which simplifies to:
D (which is (B' or C))
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Unsolved Problems in the Hard Forum
« Reply #24 on: Mar 23rd, 2005, 7:28am » |
Quote Modify
|
on Mar 23rd, 2005, 1:12am, THUDandBLUNDER wrote:
But stay (!), if (C' and B) is false then we cannot use the contapositive, right? |
|
A => B is always precisely as true as B' => A' regardless of whether A, B or both are true or false, so the contrapositive is always valid.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print