Unsolved problems General forum

28 replies. Last post: 2004-09-01

Reply to this topic Return to forum

Unsolved problems
  • Johan Roos at 2004-08-29

    This thread is for those who likes to ponder about problems that has not been solved yet :-)

    The worm problem.

    There is a worm who lived on a leaf. The leaf has the shape of a perfect circle of diameter exactly the length of the worm. The worm likes this leaf very much as it allows him to sleep in every position possible at night. One night he wakes up hungry and lazy as he is he takes a bite of his own leaf. In the near future he notices that he still can sleep in every configuration he might choose and he starts to ponder. If I wakes up hungry another night how should he go about eating his leaf making it last as long as possible before he must seek another leaf that can accomodate his odd sleeping habits?

    This problem is also knows as:
    What is the minimal area the can hold every curve of length one?

  • Tim Shih at 2004-08-29 The minimal area of the leaf will be one whose size will be exactly the size of the worm? Be it ringlike, a straight line, or a curve. Assume that the position of the leave stem is irrelevant.

    If this is not the correct answer, please kindly state your problem more clearly. :)
  • Lieven Marchand at 2004-08-29

    http://www.mathsoft.com/mathresources/constants/geometryconstant/article/0,,2059,00.html

  • David J Bush at 2004-08-29

    The region of minimal area which can hold every curve of length one, would NOT necessarily fit within a circle of diameter 1. In other words, a smaller region might be attainable if it were longer than one unit in some direction.

    Tim, the above link is what we are talking about. I don’t even know what a “rectifiable arc” is.

  • Johan Roos at 2004-08-29

    Yes David, the two versions of the problem is not equivalent. I just wanted to describe the problem in an easy to understand way without too much math talk.
    (One solution without any restrictions is for example an infinite curve of all curves of length one in succession, with area = 0 )

  • Lieven Marchand at 2004-08-29

    That’s why most formulations of this problem demand a convex solution. This eliminates that kind of solution.

  • Tasmanian Devil at 2004-08-29

    My grid subgraph prize problems are still unsolved. :-D

  • David J Bush at 2004-08-29

    "(One solution without any restrictions is for example an infinite curve of all curves of length one in succession, with area = 0 )"

    Sorry to be nit-picky about this, but that’s the nature of math:

    First of all, you have not proven that such a curve even exists. It has been proven that the set of all continuous functions over the interval [0,1] is uncountably infinite. That means you cannot refer to any enumerated list of such functions and expect to list them all. Since any such function could be “scaled down” until the length of that path is 1, that would seem to imply that the set of all paths of length 1 would also be uncountably infinite. Therefore you cannot simply connect together any enumerable collection of such paths and expect to include them all. This ignores those paths of length 1 on the curve which begin in the middle of one path and end in the middle of the next, so I have not proven anything here either, but still it seems intuitively clear to me that no such curve as you have described can exist.

    Secondly, it is not necessarily valid to state that a curve of infinite length must have zero area. For example, space-filling curves are accepted as infinite curves with positive area.

  • David J Bush at 2004-08-29

    Tasmanian, on your web page you kindly provide links to explain your terms, but you missed "4-cycles"

    How about providing an explanation or a link for that term as well? Thanks.

  • Johan Roos at 2004-08-29

    I appreciate your comments David, they are all good :-)

    Sorry for my sloppy approach, I just tried to make an argument why I chose the restriction of the circle in my version. And as Lieven said normally the restriction is the convex case but as convex also is a math term that needs a definition I chose to avoid it.

    I think the nature of the problem is captured with the circle restriction.



  • Tasmanian Devil at 2004-08-29

    David, a 4-cycle is just a cycle of length 4.

  • Tasmanian Devil at 2004-08-29

    I updated the page.

  • Paul Pogonyshev at 2004-08-30

    Tasmanian, your page has really horrible color palette. How about changing background color to white and text color to black?

  • Tasmanian Devil at 2004-08-30

    Hmmm – I’ll look into it. Is yellow text on black background considered horrible by others? :-)

  • jjjklj at 2004-08-30

    I think it’s fine, but maybe it causes problems for people with sensitive eyes.

  • Paul Pogonyshev at 2004-08-30

    Sorry if I sounded a bit offensive, but this is really impossible to read. It is an extremely aggressive color scheme, I cannot look at it for more than some 20 seconds.

    If you really like black background, I’d suggest to use a very light-gray text, but not these bright colors.

  • Paul Pogonyshev at 2004-08-30

    BTW, looking at your pages HTML, it seems it will not be quite simple to change colors, especially for all pages at once. It is worth it to learn a bit of HTML and CSS and use a text editor (like Emacs) instead of whatever you used (Front Page? Word?).

  • Tasmanian Devil at 2004-08-31

    I don’t take offense in criticism of the colours. I am glad someone points it out to me if many people find it difficult to read. However, I am not sure why you think I don’t know HTML. I take pride in avoiding junk-code-generating programs like Word and simply use notepad to edit my pages. If part of the code looks “suspicious” it’s probably because it is based upon something I copied from somewhere else.

    Anyway, I changed the colours of the grid page (and other maths related pages) so that everybody should be able to read them. :-)

  • Paul Pogonyshev at 2004-08-31

    Now, this is way more readable :)

    I suspected this because of heavy use of tag (now deprecated) which is the favorite of such programs. Typically, hand-written sites contain a `.css' file, linked into every page, so that large part of site’s appearance is coordinate from one small file.

    Sorry for offtopic everyone :o

  • Paul Pogonyshev at 2004-08-31

    Whoops, heavy use of <font%gt; tag. Forgot that Little Golem allows HTML in posts.

  • Tasmanian Devil at 2004-08-31

    You have a point there. Some of the text on the maths page probably dates back to when I first learned to make web pages four years ago and did use a program.

  • Zeycus at 2004-08-31

    Well, I don’t know whether this problem is unsolved or not, but at least I find it interesting and related to hex!

    Assumme that the infinite planar hexagonal teselation (like an infinite hex board) is taken, and that a stone is placed in each cell, black with probability q, white otherwise. The question is to calculate the probability P that the group to which a fixed distinguised cell belongs is bounded.

    Notice that there is no problem with the definition: what must be found is the sum of p_n where n traverses the positive integers and p_n is the probability that the size of the group to which the fixed cell belongs is exactly n. Each p_n depends only on finitely-many statistic variables, so each p_n is well defined.

    Two months ago I made a C program to calculate the probability that the central cell of a hex board of side 2n+1 is not in contact with the border. It seems clear that the limit when n->infty is P. I tested it with q=0.5 and growing n, until n=8000 (more than 256 millions of cells in the board!), but the probability is far to be stable.

    Please, post criticism, ideas, suggestions!

  • Zeycus at 2004-08-31

    Where I wrote: “...I made a C program to calculate the probability that the...” I meant ESTIMATE instead of calculate.

  • Tasmanian Devil at 2004-08-31

    Hi zeycus, I considered that problem several years ago. It seems that the expected size of the black group containing a given black hexagon tends to infinity as q tends to 1/2 from below.

    A related problem is the probability that black has a group that is connected to all three sides of a triangle made of hexagons (like in the game of Y) if the triangle’s side length is n and black has x of the total number T = (n^2+n)/2 hexagons. It seemed like with x = T/2 + k n for a fixed k we would get roughly the same probability for different values of n.

  • Tasmanian Devil at 2004-08-31

    Not exactly the same problem, though.

  • Zeycus at 2004-08-31

    Wow, very interesting!, thanks, TD. Do you know proofs of that result regarding the limit of the expected values, when q -> 1/2?

  • Tasmanian Devil at 2004-08-31

    Sorry, got no proofs, but perhaps one can work out a heuristic argument based on the known properties of Hex and Y (always one winner when the board is full).

  • Johan Roos at 2004-09-01

    Here is another interesting problem.

    Suppose you should sort 16 numbers. The only operation at your disposal is compare two numbers and swap their places due to the outcome of the comparison. All the comparisons must be hardcoded for example sorting 4 numbers indexed 1 to 4 can be done like this. note that the index of the numbers may change after each comparison.
    compare 1 and 2.
    compare 3 and 4.
    compare 1 and 3.
    compare 2 and 4.
    compare 2 and 3.

    the goal is to sort the numbers in as few oparations as possible. The best known result so far is 60 comparisons for 16 numbers.

    Take a look at
    http://www.cs.brandeis.edu/~hugues/sorting_networks.html
    for more info on this.

Return to forum

Reply to this topic




Include game board: [game;id:123456] or [game;id:123456;move:20] or [game;id:123456;move:20;title:some text]