Tickle your brain with fun and tough comb question. : PS Archive
Check GMAT Club Decision Tracker for the Latest School Decision Releases http://gmatclub.com/AppTrack

 It is currently 18 Jan 2017, 04:33

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# Events & Promotions

###### Events & Promotions in June
Open Detailed Calendar

# Tickle your brain with fun and tough comb question.

Author Message
GMAT Club team member
Joined: 16 Mar 2009
Posts: 115
Location: Bologna, Italy
Followers: 47

Kudos [?]: 854 [4] , given: 19

### Show Tags

31 Jul 2009, 10:43
4
KUDOS
00:00

Difficulty:

(N/A)

Question Stats:

0% (00:00) correct 0% (00:00) wrong based on 0 sessions

### HideShow timer Statistics

This topic is locked. If you want to discuss this question please re-post it in the respective forum.

Attention: This is not GMAT question. It is one of those questions that I just start wondering about and solve for fun.

Story: In Ukraine where I live at this moment public transportation is not always a fun way to go from point A to point B. So we invent different ways to make it more entertaining.
Here is one of them: In a bus or trolley bus you purchase a ticket to pay for the ride. Every ticket has a six digit number on it. $$X_1,X_2,X_3,X_4,X_5,X_6$$, where every digit is an integer from 0 to 9.
Now you can get a "lucky" ticket. It will bring luck to whatever your do during the day. Lucky ticket is such were the sum of first three digits equal to the sum of the other three digits. $$X_1+X_2+X_3=X_4+X_5+X_6$$
For example 218 542 is a lucky ticket because 2+1+8 = 5+4+2.
Question: I wondered about the probability of getting such a ticket. (lets talk about that later)Which brought me to the question:
How many lucky tickets are possible?

Have fun!

P.S If you ever come to Ukraine and get one of those - remember, for the "lucky" ticket to work you have to eat it!
_________________

My Recent Posts:
All GMAT CAT Practice Tests - links, prices, reviews
Review: GMATPrep (GMAT Prep) & PowerPrep (Power Prep) Tests

GMAT Club team member
Joined: 16 Mar 2009
Posts: 115
Location: Bologna, Italy
Followers: 47

Kudos [?]: 854 [1] , given: 19

### Show Tags

06 Aug 2009, 15:33
1
KUDOS
Since nobody was interested I decided to make it into GMAT type problem by ... providing possible answers...

a) 512
b) 55,252
c) 152,525
d) 252,000
e) 512,252

Now it is possible to solve the problem under 2 mins!

Did I lure you into giving it a try?
Hint: It is not a combinatorics problem any more. To solve this problem you would need to know one of the divisibility rules....can't tell you which one. Good Luck! Will post an OE after some time.

P.S Kudos to the first intelligent guess (give the reasons for the answer, not just a letter) and to the first correct explanation!
_________________

My Recent Posts:
All GMAT CAT Practice Tests - links, prices, reviews
Review: GMATPrep (GMAT Prep) & PowerPrep (Power Prep) Tests

Senior Manager
Joined: 20 Mar 2008
Posts: 454
Followers: 1

Kudos [?]: 118 [2] , given: 5

### Show Tags

06 Aug 2009, 17:23
2
KUDOS
My answers not on the list, but I will still give it a shot.....since we are here to learn, it's ok to screw up here!

I choose A:

Reason: That's the closest number to my answer, and since, I think, there is no way one can have any more than 999 combinations possible with a 3-digit number, the answer must be equal or less.

My take:

X1-X2-X3 = 0-0-1
.
.
.
.
X1-X2-X3 = 9-9-9

So a total of 999 combinations possible.
Senior Manager
Joined: 20 Mar 2008
Posts: 454
Followers: 1

Kudos [?]: 118 [0], given: 5

### Show Tags

06 Aug 2009, 17:39
On second thoughts I think the number should be somewhere around the 999(1/6) = 167 mark.

In my previous post I counted some possible sums an extra 5 times. For example:

103
130
301
310
013
031

That will go for most of the numbers where all the 3-digits are different. Now, even if I add a few extra for sets like:

001
010
100

I still don't see a way to get to the 500 number zone.

I like this problem, pretty interesting!
GMAT Club team member
Joined: 16 Mar 2009
Posts: 115
Location: Bologna, Italy
Followers: 47

Kudos [?]: 854 [0], given: 19

### Show Tags

06 Aug 2009, 18:06
Yeah! great to see someone try.... I was starting to get discouraged... +1 to you.
Now,your reasoning has a flaw.. the question is not about the combinations of a three digit number but about the combinations where the sum of digits equals to another sum.
so
004 = 004
004 = 040
004 = 400
004 = 112
004 = 121
004 = 211
004 = 103
004 = 130
004 = 013
004 = 301
004 = 031
004 = 310
004 = 220
004 = 022
004 = 202

for 1 combination of a 3 digit number 004 we got 15 combinations where the sum's are equal.
Getting my idea? Now I'll say more, the answer cannot be A! Why? Because there is a thousand combinations for thee digit number ( I count 000) so, there'll be at least a thousand cases when sums are equal because the left side is the same as the right side (ex. 285 285)

PS. You really will have to think outside the box with this one. And remember my hint...
_________________

My Recent Posts:
All GMAT CAT Practice Tests - links, prices, reviews
Review: GMATPrep (GMAT Prep) & PowerPrep (Power Prep) Tests

Senior Manager
Joined: 20 Mar 2008
Posts: 454
Followers: 1

Kudos [?]: 118 [0], given: 5

### Show Tags

07 Aug 2009, 08:30
Thanks for the kudos! I appreciate it!

This problem is really taking the tickling part to a whole new level. Anyway, some more thoughts but still don't see a way to set it up:

We know the max value of each digit can be 9, so the total sum of X1+X2+X3 = 9+9+9 = 27. If we know for each increase in value from 1 to 27, how many ways it can be done then we have a resolution.

Now, I just wrote down the possible combos for the first 6, the number in the bracket is the total number of possibilities for that value, but do not see a pattern, and that's what's really bugging me:

1: 001, 010, 100 (3)
2: 002, 020, 200, 101, 110, 011 (6)
3: 003, 030, 300, 111, 102, 120, 201, 210, 012, 021 (10)
4: 004, 040, 400, 121, 112, 130, 103, 202, 220, 211, 301, 310, 031, 013, 022 (15)
5: 005, 050, 500, 104, 140, 203, 230, 302, 320, 401, 410, 014, 041, 023, 032 (15)
6: 006, 060, 600, 142, 124, 240, 204, 303, 330, 402, 420, 501, 510, 033 (14)
GMAT Club team member
Joined: 16 Mar 2009
Posts: 115
Location: Bologna, Italy
Followers: 47

Kudos [?]: 854 [0], given: 19

### Show Tags

07 Aug 2009, 13:04
I like your thinking... you are following the same path I did when I tried to solve it first.
Now there is a pattern..but in a much larger scale... However it is not the way to solve the problem under 2 mins...
As I said after giving the answer choices it is not really about combinations anymore.

Now the problem is hard, so I'll give one more thought after which I'll be silent for some time to see if anyone tackles it. So here it is:

One thing you have to realize is. In a given problem it doesn't really matter in which order we add numbers. Stop. What did he say?
Yes it doesn't. So let's call the ticket were $$X_1+X_3+X_5=X_2+X_4+X_6$$ an "Irish luck ticket".
Think about it for a minute and you'll see that the number of combination where $$X_1+X_2+X_3=X_4+X_5+X_6$$ is the same to the number of combinations where $$X_1+X_3+X_5=X_2+X_4+X_6$$. Now wrap your mind about it. The numbers themselves would be different ( 218 542 vs 251482 ) BUT the total number of combinations for both "lucky ticket" and "Irish luck ticket" would remain the same.

Now how does the Irish luck ticket help to solve the problem is up to you to figure out... Up from here it is very easy if you look on everything that I said.... Did you look through divisibility rules?
_________________

My Recent Posts:
All GMAT CAT Practice Tests - links, prices, reviews
Review: GMATPrep (GMAT Prep) & PowerPrep (Power Prep) Tests

Intern
Joined: 01 Aug 2009
Posts: 29
Location: Australia
Followers: 1

Kudos [?]: 17 [0], given: 3

### Show Tags

08 Aug 2009, 06:39
timetrader, I think you've managed to more than tickle

I am still working/thinking on the legitimate solution, but by working through illegitimate means I think the answer is b) 55,252 ??
_________________

The three most significant times in your life are:
1. When you fall in love
2. The birth of your first child
3. When you prepare for your GMAT

GMAT Club team member
Joined: 16 Mar 2009
Posts: 115
Location: Bologna, Italy
Followers: 47

Kudos [?]: 854 [0], given: 19

### Show Tags

08 Aug 2009, 14:54
scarish wrote:
timetrader, I think you've managed to more than tickle

I guess I have spent to much time thinking about it in trolley buses

scarish wrote:
I am still working/thinking on the legitimate solution, but by working through illegitimate means I think the answer is b) 55,252 ??

Yes! What was your reasoning? (now I know that you didn't find the number (edit: and I was wrong)... it is overly complicated... but why did you think it is less than 152,525?)
_________________

My Recent Posts:
All GMAT CAT Practice Tests - links, prices, reviews
Review: GMATPrep (GMAT Prep) & PowerPrep (Power Prep) Tests

Intern
Joined: 01 Aug 2009
Posts: 29
Location: Australia
Followers: 1

Kudos [?]: 17 [2] , given: 3

### Show Tags

09 Aug 2009, 02:47
2
KUDOS
Like I said, I do not have a proper (2 min) solution...still thinking...
However, I applied some heuristics and lots of good old brute force to calculate the answer.

WARNING: This is very very ugly solution and is certainly not recommended, but this is all I could do in about 2 hours I spent on this LOL
Apologies for the length of the post...

Alright let's start...man, this is gonna hurt

Solution:
The highest sum for a 3 digit number is 27 (9 + 9 + 9).
So, I started playing by listing the combinations for sum 1,2, and 3.

Sum = 1:
For the sum to be equal to 1, the 3 digits must be different combinations of 0,0,1

To find the number of combinations, we can see that we are arranging 0 and 1 in three slots, but there are 2 zeros.
Number of unique ways to arrange 3 items where 2 of the items are identical is: 3!/2! = 3 (Number of items!/number of identical items!)

So we have 3 unique combinations: 001, 010, 100
Now, we have added complexity of each uniques combination combining with any other combination on either side of a 6 digit number.
That is, 001 010 is different from 010 001.

So, let us list the combinations:
001 001 010 001 100 001
001 010 010 010 100 010
001 100 010 100 100 100

Arranging the 3 unique combinations in 2 (left/right) slots when each combination can also combine with itself (001 001) is 3^2= 9

Sum = 2
The digits that can be used to get sum of 2, are 002, 011

002 : 3!/2! = 3 (number of ways to arrange 3 items when 2 are identical)
011 : 3!/2! = 3 (number of ways to arrange 3 items when 2 are identical)

Total ways: 3+3 = 6

Accounting for left/right combinations: 6^2 = 36

Sum = 3
The digits that can be used to get sum of 3, are 003, 021, 111

003 : 3!/2! = 3
021 : 3! = 6 (no identical digits)
111 : 3!/3! = 1

Total ways: 3+6+1 = 10

Accounting for left/right combinations: 10^2 = 100

Wait a minute.....

Sum: 1 : Total Ways = 3
Sum: 2 : Total Ways = 6
Sum: 3 : Total Ways = 10

Ways(Sum: 1) = Ways(Sum: 0) + 2 = 3 [Ways(Sum: 0) = 3!/3! = 1 (only combination 000)]
Ways(Sum: 2) = Ways(Sum: 1) + 3 = 3 + 3 = 6
Ways(Sum: 3) = Ways(Sum: 2) + 4 = 4 + 4 = 10

Could it be, that the difference between the number of ways for consecutive sum, is one more than the difference between the previous two number of ways.

That is, Ways(Sum: x) = Ways(Sum: x-1) + [Ways(Sum:x-1) - Ways(Sum:x-2) + 1]

Ok let's try Sum:4
Ways(Sum: 4) = Ways(Sum: 3) + [Ways(Sum:3) - Ways(Sum:2) + 1]
Ways(Sum: 4) = = 10 + [10-6+1] = 15

Is it??...let's check...
Sum = 4
The digits that can be used to get sum of 4, are 004, 031, 022, 211

004 : 3!/2! = 3
031 : 3! = 6 (no identical digits)
022 : 3!/2! = 3
211 : 3!/2! = 3

Total ways: 6+3+3+3 = 15 = which is what our pattern formula gave above!

So using the pattern, we can now find the number of ways for the rest of the sums...

SUM Number of Ways
0 1
1 3
2 6
3 10
4 15
5 21
6 28
7 36
8 45
9 55
10 66 (not true)

But I thought that it wouldn't continue forever, cos when we get to Sum: 10, we will no longer have our first combination with zeros! that is we don't have 0010 like we had 009.
So we have to subtract 3 ways from the total number of ways: 66-3 = 63

SUM Number of Ways
10 63

Now I didn't knew how to continue for 11, so I just calculated combinations for Sum: 11:

Which gave:
SUM Number of Ways
11 69

Looking at the difference between Ways(Sum:10) and Ways(Sum:9) and Ways(Sum:11) and Ways(Sum:10):
Ways(Sum:10) - Ways(Sum:9) = 63 - 55 = 8
Ways(Sum:11) - Ways(Sum:10) = 69 - 63 = 6

Looks like the increment in number of ways is slowing down.

Is the difference between Ways(Sum:12) and Ways(Sum:11) = 4??
that is, Ways(Sum:12) = 73 [yes it is!]

Right then, we have a pattern
SUM Number of Ways
12 73 [difference of 4 from sum:11]
13 75 [difference of 2 from sum:12]
14 75 [difference of 0 from sum:13]

But now for Sum:15, what do I do?? Does it start to reverse?? I checked 15 and 16 and yes it does...so
SUM Number of Ways
15 73
16 69
17 63
18 55
19 45
20 36
21 28
22 21
23 15
24 10
25 6
26 3
27 1

Square all number of ways and add them all together to get: 55,252 combinations!

It's not an ideal solution by any means, still hoping to find (or ask timetrader LOL ) for the neater/more elegant solution
_________________

The three most significant times in your life are:
1. When you fall in love
2. The birth of your first child
3. When you prepare for your GMAT

GMAT Club team member
Joined: 16 Mar 2009
Posts: 115
Location: Bologna, Italy
Followers: 47

Kudos [?]: 854 [0], given: 19

### Show Tags

09 Aug 2009, 14:39
WOW awesome!!! You did it!! I didn't expect anyone to do it that way... but wow... that exceeded my expectations. You certainly deserve kudos! Awesome solution!
I'll give another way of looking onto the problem shortly!
_________________

My Recent Posts:
All GMAT CAT Practice Tests - links, prices, reviews
Review: GMATPrep (GMAT Prep) & PowerPrep (Power Prep) Tests

Founder
Affiliations: AS - Gold, HH-Diamond
Joined: 04 Dec 2002
Posts: 14428
Location: United States (WA)
GMAT 1: 750 Q49 V42
GPA: 3.5
Followers: 3715

Kudos [?]: 22967 [0], given: 4510

### Show Tags

09 Aug 2009, 15:17

Can't think of anything else to say.
_________________

Founder of GMAT Club

US News Rankings progression - last 10 years in a snapshot - New!
Just starting out with GMAT? Start here...
Need GMAT Book Recommendations? Best GMAT Books

Co-author of the GMAT Club tests

GMAT Club Premium Membership - big benefits and savings

Manager
Joined: 28 Jul 2009
Posts: 124
Location: India
Schools: NUS, NTU, SMU, AGSM, Melbourne School of Business
Followers: 6

Kudos [?]: 75 [0], given: 12

### Show Tags

09 Aug 2009, 22:45
Hail Scarish!
_________________

GMAT offended me. Now, its my turn!
Will do anything for Kudos! Please feel free to give one.

Intern
Joined: 01 Aug 2009
Posts: 29
Location: Australia
Followers: 1

Kudos [?]: 17 [0], given: 3

### Show Tags

10 Aug 2009, 03:57
WOW awesome!!! You did it!! I didn't expect anyone to do it that way... but wow... that exceeded my expectations. You certainly deserve kudos! Awesome solution!
I'll give another way of looking onto the problem shortly!

bb wrote:
:pray

Can't think of anything else to say.

bhanushalinikhil wrote:
Hail Scarish!

Thanks guys

Look forward to timetrader's solution, which I am sure will be more useful than the head-hurting solution above!
_________________

The three most significant times in your life are:
1. When you fall in love
2. The birth of your first child
3. When you prepare for your GMAT

GMAT Club team member
Joined: 16 Mar 2009
Posts: 115
Location: Bologna, Italy
Followers: 47

Kudos [?]: 854 [0], given: 19

### Show Tags

10 Aug 2009, 04:33
scarish wrote:
Thanks guys

Look forward to timetrader's solution, which I am sure will be more useful than the head-hurting solution above!

Well, no, it is not really useful I really wanted to make out of the box problem but I feel that I failed. Oh well maybe next puzzle will be better)).

Now here is how I thought it can be solved:

Remember the "Irish luck" ticket from above, and how the number of its combinations is equal to the lucky ticket? Well, it easy to see that all the "Irish luck tickets" can be divided by 11. (Starting with ones digit, add every other number (A). Add the remaining numbers (B). If A - B is divisible by 11, then the number is also divisible.) Since in our problem A=B, therefore A-B=0, and is divisible by 11. Why is it useful?

Out of this we can conclude that the number of combinations of lucky tickets is not greater than the number of tickets which can be divided by 11. So we know that the number of lucky tickets is not greater than 999 999/11 = 90909 +1 = 90910 !
(Of course there are tickets that can be divided by 11 and which are not lucky)

And as I mentioned in one of the posts above we know that the number of combinations is certainly greater than 512. So after looking on the possible answers B) is the only fitting solution.
That is it... I hope my next puzzle will be more fun )) Cheers!

PS. scarish you are scary! Once again - great job! Good luck with GMAT!
_________________

My Recent Posts:
All GMAT CAT Practice Tests - links, prices, reviews
Review: GMATPrep (GMAT Prep) & PowerPrep (Power Prep) Tests

Intern
Joined: 01 Aug 2009
Posts: 29
Location: Australia
Followers: 1

Kudos [?]: 17 [0], given: 3

### Show Tags

10 Aug 2009, 15:55
That is it... I hope my next puzzle will be more fun )) Cheers!

PS. scarish you are scary! Once again - great job! Good luck with GMAT!

This one was fun mate...it helped clear lot of combination cobwebs
Good luck on the GMAT to you too ~ Cheers.
_________________

The three most significant times in your life are:
1. When you fall in love
2. The birth of your first child
3. When you prepare for your GMAT

Math Expert
Joined: 02 Sep 2009
Posts: 36540
Followers: 7074

Kudos [?]: 93072 [1] , given: 10541

### Show Tags

06 Oct 2009, 09:48
1
KUDOS
Expert's post
Work our another way to solve this problem and think it's more elegant.

First of all when analyzing the pattern of a+b+c=d+e+f (each from 0 to 9, sum=<27) from the beginning it seemed to me that there must be another pattern in it. And it is. a+b+c-d-e-f=0 --> a+b+c+(9-d)+(9-e)+(9-f)=27, so there are as many tickets with "lucky" numbers as tickets with the sum of 27. Half of the problem done.

So, lets find how many 6 digit numbers' sum of digit is=27.

I made silly mistake thinking that the answer would be the same as for th problem: "how many ways are there to distribute 27 cakes among 6 people, no restriction (meaning that each can get from 0 to 27)" --> C(6-1; 27+6-1)=C(5;32), BUT no one can get more than 9 cakes (cakes=digits<=9).

It means that we must deduct (from C(5;32)) the number of ways 1 or 2 (no more than 2 people can get more than 9 cakes) will get more than 9 cakes:

Let's give 10 cakes to any of 6 and distribute rest (17) among the 6 people again: C(6-1;27+6-1-10)=C(5;22) (The same number of ways as to distribute 17 cakes among 6 people=C(5;22)), as far as there are 6 people total ways would be C(1;6)*C(5;22)

BUT this formula will count twice the number of 2 people getting more than 9 cakes, so deduct from (C(1;6)*C(5;22)) the number of ways exactly two people can get more than 9 cakes. The same way: lets give 10 to any of 6 and 10 to any of the rest of 6 --> C(6-1; 27+6-1-10-10)=C(5;12) (again it's the same as to distribute 7 cakes among 6 people). As there are C(2;6) ways of doing this, so the total number of ways would be C(2;6)*C(5;12).

Done.

Hope no such problems in GMAT.
_________________
Re: Tickle your brain with fun and tough comb question.   [#permalink] 06 Oct 2009, 09:48
Display posts from previous: Sort by