wu :: forums
« wu :: forums - Unsolved Problems in the Hard Forum »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 1:32am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Icarus, SMQ, Eigenray, ThudnBlunder, towr, william wu, Grimbal)
   Unsolved Problems in the Hard Forum
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Unsolved Problems in the Hard Forum  (Read 45051 times)
Icarus
wu::riddles Moderator
Uberpuzzler
*****



Boldly going where even angels fear to tread.

   


Gender: male
Posts: 4863
Unsolved Problems in the Hard Forum  
« on: Jul 23rd, 2003, 9:01pm »
Quote Quote Modify 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.)


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! Wink)
« 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
****





   
Email

Gender: male
Posts: 513
Re: Unsolved Problems in the Hard Forum  
« Reply #1 on: Jul 23rd, 2003, 10:29pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 203
Re: Unsolved Problems in the Hard Forum  
« Reply #3 on: Aug 13th, 2003, 9:10pm »
Quote Quote Modify 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.  Smiley  And I do regret it okay! sheesh.  Hehe
IP Logged

A job is not worth doing unless it's worth doing well.
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Unsolved Problems in the Hard Forum  
« Reply #4 on: Sep 9th, 2003, 9:03am »
Quote Quote Modify Modify

Ditto. Awesome work Icarus, as always. Thanks so much Smiley
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Unsolved Problems in the Hard Forum  
« Reply #5 on: Sep 23rd, 2003, 1:28pm »
Quote Quote Modify 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: male
Posts: 4863
Re: Unsolved Problems in the Hard Forum  
« Reply #6 on: Sep 23rd, 2003, 6:00pm »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 4863
Re: Unsolved Problems in the Hard Forum  
« Reply #8 on: Sep 23rd, 2003, 6:55pm »
Quote Quote Modify 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! Sad That's what I get for doing something ambitious once. Wink
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
*****





   
Email

Gender: male
Posts: 949
Re: Unsolved Problems in the Hard Forum  
« Reply #9 on: Sep 24th, 2003, 9:44am »
Quote Quote Modify 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
*





   
WWW

Gender: male
Posts: 22
Updated 12-balls (variation)  
« Reply #10 on: Oct 14th, 2003, 9:22am »
Quote Quote Modify 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: male
Posts: 4863
Re: Unsolved Problems in the Hard Forum  
« Reply #11 on: Oct 14th, 2003, 7:58pm »
Quote Quote Modify 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: male
Posts: 4863
Re: Unsolved Problems in the Hard Forum  
« Reply #12 on: Nov 11th, 2003, 6:59pm »
Quote Quote Modify 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".Wink  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
*





   
Email

Gender: male
Posts: 30
convex set projection  
« Reply #13 on: Dec 3rd, 2003, 4:43am »
Quote Quote Modify 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 Quote Modify Modify

Huhahhh 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  Huh
IP Logged
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Unsolved Problems in the Hard Forum  
« Reply #15 on: Jan 5th, 2005, 10:51am »
Quote Quote Modify 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! Smiley
 
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Re: Unsolved Problems in the Hard Forum  
« Reply #16 on: Jan 5th, 2005, 11:38am »
Quote Quote Modify 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  Huh

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: male
Posts: 4489
Re: Unsolved Problems in the Hard Forum  
« Reply #17 on: Mar 21st, 2005, 1:15am »
Quote Quote Modify 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: male
Posts: 13730
Re: Unsolved Problems in the Hard Forum  
« Reply #18 on: Mar 21st, 2005, 5:36am »
Quote Quote Modify 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: male
Posts: 4489
Re: Unsolved Problems in the Hard Forum  
« Reply #19 on: Mar 21st, 2005, 6:31am »
Quote Quote Modify 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: male
Posts: 13730
Re: Unsolved Problems in the Hard Forum  
« Reply #20 on: Mar 22nd, 2005, 6:39am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: Unsolved Problems in the Hard Forum  
« Reply #21 on: Mar 22nd, 2005, 6:58am »
Quote Quote Modify 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: male
Posts: 4489
Re: Unsolved Problems in the Hard Forum  
« Reply #22 on: Mar 23rd, 2005, 1:12am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: Unsolved Problems in the Hard Forum  
« Reply #23 on: Mar 23rd, 2005, 7:03am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2872
Re: Unsolved Problems in the Hard Forum  
« Reply #24 on: Mar 23rd, 2005, 7:28am »
Quote Quote Modify 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
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board