My Math Forum  

Go Back   My Math Forum > College Math Forum > Advanced Statistics

Advanced Statistics Advanced Probability and Statistics Math Forum


Thanks Tree2Thanks
  • 1 Post By CRGreathouse
  • 1 Post By CRGreathouse
Reply
 
LinkBack Thread Tools Display Modes
October 21st, 2015, 03:06 PM   #1
Newbie
 
Joined: Oct 2015
From: Finland

Posts: 4
Thanks: 0

Need fast help for a hard equation

Hello!

I just registered to this site to find a solution for the following problem:

"There are 25 students. 10 Greek, 8 Finns, 2 Russians and 5 Swedes. The students study in groups. A group always consists of one or more students. If a group has at least 2 students that are of same nationality, then the group has to have at least one student who is different nationality. How many different ways are there to divide the 25 students to groups?"

I would appreciate fast help! This equation is killing me as I am no maths expert...
Darien Fawks is offline  
 
October 21st, 2015, 03:46 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
This looks hard!

Without the restriction on ethnicity, the answer would be C(25), the 25-th Catalan number. The most straightforward approach seems to be taking that as the starting point and subtracting off those groups which are disallowed. But that's not entirely straightforward since you can have instances with two or more illegal monoethnic groups and you don't want to double-count these.
CRGreathouse is offline  
October 23rd, 2015, 10:45 AM   #3
Senior Member
 
Joined: Oct 2013
From: New York, USA

Posts: 638
Thanks: 85

Wikipedia says the 25th Catalan number is 1,289,904,147,324 which is 13 digits.

Without any restriction on how many groups to make, I don't know how to solve it quickly. You could break it down into every amount of groups from 1 group of 25 to 25 groups of 1 (a group of 1 sounds strange but the problem says "one or more students," not two or more). For some amounts of groups the number of possibilities can be done quickly but for other amounts of groups it is hard. Here's a start:

1 group of 25: 1 way
24 groups (23 groups of 1 and 1 group of 2): 6 ways (the group of 2 must have two different nationalities so it's 4 C 2 = 6).
25 groups of 1: 1 way

For 23 groups you would have to break it into 2 parts:

22 groups of 1 and 1 group of 3
21 groups of 1 and 2 groups of 2

For 10 groups you would have to break it into many parts (I don't know how many).

What's the source of the problem? What math course are you taking?
EvanJ is offline  
October 24th, 2015, 03:35 PM   #4
Newbie
 
Joined: Oct 2015
From: Finland

Posts: 4
Thanks: 0

This was actually on a Finnish game show where they're taking phone calls and giving out some money for the people who solve certain puzzles.

No idea what the answer was as this was only a part of the puzzle...
Darien Fawks is offline  
October 25th, 2015, 08:02 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by EvanJ View Post
24 groups (23 groups of 1 and 1 group of 2): 6 ways (the group of 2 must have two different nationalities so it's 4 C 2 = 6).
No, because it matters which people are in the group, not just their ethnicity. With 10 Greek, 8 Finns, 2 Russians and 5 Swedes I get:

Greek + non-Greek: 10 * 15 ways
Finn + (Russian or Swede): 8 * 7 ways
Russian + Swede: 2*5 ways
Total: 216 ways
Thanks from EvanJ
CRGreathouse is offline  
October 25th, 2015, 12:50 PM   #6
Newbie
 
Joined: Oct 2015
From: Finland

Posts: 4
Thanks: 0

This is impossible.

Last edited by Darien Fawks; October 25th, 2015 at 12:53 PM.
Darien Fawks is offline  
October 27th, 2015, 11:26 AM   #7
Member
 
Joined: Jun 2015
From: Ohio

Posts: 99
Thanks: 19

I thought of a possible solution, but I'm still trying to work it out and see if it makes enough sense :/ this is a lot of work!
numberguru1 is offline  
October 27th, 2015, 05:18 PM   #8
Member
 
Joined: Jun 2015
From: Ohio

Posts: 99
Thanks: 19

Yeah, I'm not entirely sure if this works, but any input would be appreciated. Basically you can think of the question as you can't have a group of more than one student with only one nationality.

What if you took $\displaystyle C_{25} - C_{10}C_8C_5C_2$?

I was thinking, wouldn't $\displaystyle C_{10}$ be the number of groups that could be formed where all students were Greek. $\displaystyle C_{8}$ for the Finns, $\displaystyle C_{5}$ for the Swedes and $\displaystyle C_{2}$

So,

$\displaystyle C_{10}C_8C_5C_2$

would be all possible combinations where groups only had students from one ethnic group. Thus making $\displaystyle C_{25} - C_{10}C_8C_5C_2$ the answer. Is this valid logic?
numberguru1 is offline  
October 27th, 2015, 05:36 PM   #9
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by numberguru1 View Post
So,

$\displaystyle C_{10}C_8C_5C_2$

would be all possible combinations where groups only had students from one ethnic group. Thus making $\displaystyle C_{25} - C_{10}C_8C_5C_2$ the answer. Is this valid logic?
No. What about when all the groups are valid except the Russians are paired off? You're not counting it in $C_{10}C_8C_5C_2$ but it's still invalid.
Thanks from numberguru1
CRGreathouse is offline  
October 31st, 2015, 04:12 PM   #10
Newbie
 
Joined: Oct 2015
From: Finland

Posts: 4
Thanks: 0

I guess no one can solve this.
Darien Fawks is offline  
Reply

  My Math Forum > College Math Forum > Advanced Statistics

Tags
equation, fast, hard



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Nice hard equation to solve - can you do it? victoriamath Algebra 13 August 11th, 2014 08:48 AM
solve the following equation - Hard problem mjbecnel Algebra 7 March 5th, 2014 03:50 AM
Hard equation eliyaoo32 Algebra 5 June 17th, 2013 07:35 AM
hard equation llambi Algebra 17 May 4th, 2011 11:18 AM
Hard equation mike000 Number Theory 1 June 9th, 2008 11:59 AM





Copyright © 2019 My Math Forum. All rights reserved.