Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

A Boggle-like Challenge


  • Please log in to reply
18 replies to this topic

#11 brifri238

brifri238

    Newbie

  • Members
  • Pip
  • 7 posts

Posted 16 November 2012 - 11:59 AM

Spoiler for Possible solution for the first part:

Edited by brifri238, 16 November 2012 - 12:07 PM.

  • 0

#12 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

Posted 16 November 2012 - 09:11 PM

Curr3nt and brifri238 both found good adjacency hookups. I think phil1882 got
into a bit of trouble trying to keep the dimension down to two or three. Also,
curr3nt's solution makes for an easy second part solution. I had hoped that
someone would go a bit further and hint at some algorithm for generating these
things. I know of no way to generate a random one -- i.e. an algorithm which
can choose one with probability 1/N where N is the total number of possible
adjacencies. I don't even know how to find N. Thanks for working on it.

  • 0

#13 phil1882

phil1882

    Senior Member

  • Members
  • PipPipPipPip
  • 551 posts

Posted 17 November 2012 - 02:04 PM

Spoiler for assuming curr3nts

  • 0

#14 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 18 November 2012 - 07:41 AM

Spoiler for assuming curr3nts


N is not going to be that simple to calculate. Any given adjacency you find could have multiple possible cycles that could be found within it (So it may incorrectly be counted multiple times). Adjacencies don't need to be as neatly organized as curr3nt's answer was.
Spoiler for Large range for N


Spoiler for Anticlimactic way to generate with 1/N probability

  • 0

#15 curr3nt

curr3nt

    The

  • Members
  • PipPipPipPip
  • 2839 posts
  • Gender:Male
  • Location:in a field of spatulas...

Posted 19 November 2012 - 07:58 PM

Spoiler for Why wouldn't phil's approach for N work?

  • 0

#16 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 19 November 2012 - 11:06 PM

Spoiler for Why wouldn't phil's approach for N work?


Spoiler for can you "cube" this?

  • 0

#17 superprismatic

superprismatic

    Not just Prismatic

  • Moderator
  • PipPipPipPip
  • 1281 posts
  • Gender:Male

Posted 19 November 2012 - 11:39 PM

Perhaps going down to a smaller alphabet will help
shed light on this problem. I wrote a little program
to generate all possible ways of making adjacencies on
an alphabet of size 8 with each letter having 3 adjacencies.
The number of these I got was 19,355.
  • 0

#18 EventHorizon

EventHorizon

    Senior Member

  • VIP
  • PipPipPipPip
  • 512 posts
  • Gender:Male

Posted 20 November 2012 - 01:47 AM

Yay for integer sequences (found using your 19355 :) )...

Spoiler for Not the answer, but some pretty numbers anyway


Spoiler for Estimation of N based on list 3 + connected=cycle assumption


Spoiler for Simple proof for connected=cycle in 2-regular graphs

Time to look at 3-regular graphs... which aren't as simple and quite possibly don't have this property.

Spoiler for Useful article...

  • 0

#19 curr3nt

curr3nt

    The

  • Members
  • PipPipPipPip
  • 2839 posts
  • Gender:Male
  • Location:in a field of spatulas...

Posted 20 November 2012 - 04:21 PM

Spoiler for can you "cube" this?


Spoiler for You had me at...

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users