Author |
Topic: combinations (Read 3557 times) |
|
almost dead
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?
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.
|
|
 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
|
|
|
almost dead
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
|
|
|
almost dead
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:
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: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: 7526
|
|
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: 7526
|
|
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?
I think I need to think more about this problem.
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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print