wu :: forums « wu :: forums - combinations » Welcome, Guest. Please Login or Register. Aug 12th, 2022, 7:55am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: william wu, SMQ, Icarus, Eigenray, Grimbal, ThudnBlunder, towr)    combinations « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: combinations  (Read 3517 times)
Newbie

Posts: 17
 combinations   « on: Dec 21st, 2006, 7:16am » Quote Modify

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?

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
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: combinations   « Reply #1 on: Dec 21st, 2006, 7:55am » Quote Modify

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?
 « Last Edit: Dec 21st, 2006, 7:56am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Newbie

Posts: 17
 Re: combinations   « Reply #2 on: Dec 21st, 2006, 8:23am » Quote Modify

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
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: combinations   « Reply #3 on: Dec 21st, 2006, 8:34am » Quote Modify

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.
 « Last Edit: Dec 21st, 2006, 8:35am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Newbie

Posts: 17
 Re: combinations   « Reply #4 on: Dec 21st, 2006, 5:18pm » Quote Modify

somebody help!!
 IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: combinations   « Reply #5 on: Dec 21st, 2006, 5:38pm » Quote Modify

on Dec 21st, 2006, 5:18pm, almost dead wrote:
 somebody help!!

Would that not be cheating?
 IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
azalia
Newbie

Posts: 36
 Re: combinations   « Reply #6 on: Dec 21st, 2006, 6:51pm » Quote Modify

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.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: combinations   « Reply #7 on: Dec 22nd, 2006, 3:28am » Quote Modify

on Dec 21st, 2006, 5:18pm, 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?
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7519
 Re: combinations   « Reply #8 on: Dec 22nd, 2006, 6:28am » Quote Modify

I took part in the PuzzleUp competition, I gave 38015 as an answer and I got points for that.  It must be the intended answer.
 « Last Edit: Dec 22nd, 2006, 6:29am by Grimbal » IP Logged
balakrishnan
Junior Member

Gender:
Posts: 92
 Re: combinations   « Reply #9 on: Jan 9th, 2007, 8:32am » Quote Modify

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?
 « Last Edit: Jan 9th, 2007, 8:32am by balakrishnan » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: combinations   « Reply #10 on: Jan 9th, 2007, 8:39am » Quote Modify

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..)
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7519
 Re: combinations   « Reply #11 on: Jan 9th, 2007, 8:48am » Quote Modify

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.
 IP Logged
balakrishnan
Junior Member

Gender:
Posts: 92
 Re: combinations   « Reply #12 on: Jan 9th, 2007, 8:59am » Quote Modify

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.

 IP Logged
balakrishnan
Junior Member

Gender:
Posts: 92
 Re: combinations   « Reply #13 on: Jan 9th, 2007, 9:02am » Quote Modify

on Jan 9th, 2007, 8:48am, 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?
As an aside:
Do you think there will be puzzleup-2007?
 « Last Edit: Jan 9th, 2007, 9:18am by balakrishnan » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: combinations   « Reply #14 on: Jan 9th, 2007, 9:37am » Quote Modify

on Jan 9th, 2007, 8:59am, 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.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »