Author 
Topic: Unsolved Problems in the Hard Forum (Read 37866 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 23^{rd}, 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 noone 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 diehard 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.  10adic numbers, still has a followup 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.
 Threeway Pistol Duel . While the main question has long been solved, there is a multishooter 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 followup question no one has touched.
 Shuffling cards into order. The original is solved, but the general equation for outshuffles 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 15^{th}, 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 23^{rd}, 2003, 10:29pm » 
Quote Modify

Damn, thanks. This will help direct efforts. Must have taken a while too.


IP Logged 



SWF
Uberpuzzler
Posts: 871


Re: Unsolved Problems in the Hard Forum
« Reply #2 on: Jul 24^{th}, 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 13^{th}, 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 23^{rd}, 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 23^{rd}, 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: 871


Re: Unsolved Problems in the Hard Forum
« Reply #7 on: Sep 23^{rd}, 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 23^{rd}, 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 24^{th}, 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 12balls (variation)
« Reply #10 on: Oct 14^{th}, 2003, 9:22am » 
Quote Modify

I provided the answer for redPepper's extension to the 12ball (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 14^{th}, 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 11^{th}, 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 3^{rd}, 2003, 4:43am » 
Quote Modify

my kneejerk 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 5^{th}, 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 5^{th}, 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 5^{th}, 2005, 11:38am » 
Quote Modify

on Jan 5^{th}, 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 21^{st}, 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 tightropes E = Eat pennybuns 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 22^{nd}, 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: 13254


Re: Unsolved Problems in the Hard Forum
« Reply #18 on: Mar 21^{st}, 2005, 5:36am » 
Quote Modify

on Mar 21^{st}, 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 21^{st}, 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 21^{st}, 2005, 6:31am » 
Quote Modify

on Mar 21^{st}, 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 21^{st}, 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: 13254


Re: Unsolved Problems in the Hard Forum
« Reply #20 on: Mar 22^{nd}, 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: 2701


Re: Unsolved Problems in the Hard Forum
« Reply #21 on: Mar 22^{nd}, 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 23^{rd}, 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 23^{rd}, 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: 2701


Re: Unsolved Problems in the Hard Forum
« Reply #23 on: Mar 23^{rd}, 2005, 7:03am » 
Quote Modify

on Mar 23^{rd}, 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: 2701


Re: Unsolved Problems in the Hard Forum
« Reply #24 on: Mar 23^{rd}, 2005, 7:28am » 
Quote Modify

on Mar 23^{rd}, 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 



