wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> combinations
        
(Message started by: vinayan1986 on Dec 21^st, 2006, 7:16am)

Title: combinations
Post by vinayan1986 on Dec 21^st, 2006, 7:16am

In a problem within a quizzing competition a condition
is given and, the numbers (or the number) satisfying
that condition is asked. If there is more than one
number that satisfies the given condition, then those
numbers will be entered into the answer box, side by
side, without leaving any space between each other.

If "123456789123456789" is entered into the answer box,
how many different answers correspond to this entry?

If the question were asked for "1212", then the answer
would be 5: (1,2,12), (1,21,2), (1,212), (121,2), (1212).
Note that, (1,2,1,2) and (12,12) are not included since
the same numbers are repeated. Also (12,1,2) is not
included, since the answer (1,2,12) is already present.

Title: Re: combinations
Post by towr on Dec 21^st, 2006, 7:55am

You've really written the puzzle in a very confusing manner.
Does it come down to "In how many ways can you cut up a string such that no two pieces are the same?"

And can I use a computer to find the answer?

Title: Re: combinations
Post by almost dead on Dec 21^st, 2006, 8:23am

no sir u cant use a computer..and i really dont know whether this has the status of being posted in the hard section...and ofcourse we can say it lik cutting a string such that no 2 pieces are equal..but here the no: sequence repeats once again...so its not exactly lik cutting the string...i think i am pretty clear now

Title: Re: combinations
Post by towr on Dec 21^st, 2006, 8:34am

Ah, so if we look at a general case, we'd only consider inputs of the kind
"11"
"1212"
"123123"
"12341234"
etc.

That might be the way to find an answer. It's easy enough to find the result for the first few, and if there's a pattern there, we can find the answer we're looking for.

Title: Re: combinations
Post by almost dead on Dec 21^st, 2006, 5:18pm

somebody help!!

Title: Re: combinations
Post by THUDandBLUNDER on Dec 21^st, 2006, 5:38pm

on 12/21/06 at 17:18:15, almost dead wrote:

somebody help!!

Would that not be cheating? ;)

Title: Re: combinations
Post by azalia on Dec 21^st, 2006, 6:51pm

This was a question in the PuzzleUp competition, but the competition is over (quoted verbatim except for dropping the contest name). They had no rules against using a computer. And they don't reveal the answers.

Title: Re: combinations
Post by towr on Dec 22^nd, 2006, 3:28am

on 12/21/06 at 17:18:15, almost dead wrote:

somebody help!!

No need to be impatient, someone'll get to it eventually. Bare in mind it's almost christmas, so people might be preoccupied with that.
It's not like your life depends on it, right?

Title: Re: combinations
Post by Grimbal on Dec 22^nd, 2006, 6:28am

I took part in the PuzzleUp competition, I gave [hide] 38015 [/hide] as an answer and I got points for that. It must be the intended answer.

Title: Re: combinations
Post by balakrishnan on Jan 9^th, 2007, 8:32am

I also sent the same answer and got points.
But is there an analytical way of solving this problem.
I had to write a C code.
Atleast is there any recursion formulation for this problem?
Grimbal,
How did you solve it?

Title: Re: combinations
Post by towr on Jan 9^th, 2007, 8:39am

Have you tried searching the integer sequence database with the first few numbers? There's a good chance it's there..
(I never actually got around to programming, so I haven't much of a sequence to search on myself..)

Title: Re: combinations
Post by Grimbal on Jan 9^th, 2007, 8:48am

I seem to remember I did an exhaustive search. with 20 digits there are just half a million ways to cut it into pieces. Many have duplicate numbers. The rest can be stored and counted.

Title: Re: combinations
Post by balakrishnan on Jan 9^th, 2007, 8:59am

Hi Towr,
That is a wonderful suggestion!
I just ran my code
The sequence happens to be
n=5:247,
n=6:877,
n=7:3095,
n=8:10869,
n=9:38015,

I cant find any source for this sequence. It would be nice if someone does.

Title: Re: combinations
Post by balakrishnan on Jan 9^th, 2007, 9:02am

on 01/09/07 at 08:48:24, Grimbal wrote:

I seem to remember I did an exhaustive search. with 20 digits there are just half a million ways to cut it into pieces. Many have duplicate numbers. The rest can be stored and counted.

So you went upto 20 digits?
I think I need to think more about this problem.
As an aside:
Do you think there will be puzzleup-2007? :-/

Title: Re: combinations
Post by towr on Jan 9^th, 2007, 9:37am

on 01/09/07 at 08:59:16, balakrishnan wrote:

Hi Towr,
That is a wonderful suggestion!
I just ran my code
The sequence happens to be
n=5:247,
n=6:877,
n=7:3095,
n=8:10869,
n=9:38015,
I cant find any source for this sequence. It would be nice if someone does.

From lookign at it, it seems as there's nearly a constant factor between each. If it has a first or second order recurrence, it shouldn't be difficult to find.
I'll give it some more scrutiny when I'm back behind my own computer.