My Math Forum Need fast help for a hard equation

 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...
 October 21st, 2015, 03:46 PM #2 Global Moderator     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.
 October 23rd, 2015, 10:45 AM #3 Senior Member   Joined: Oct 2013 From: New York, USA Posts: 660 Thanks: 87 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?
 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...
October 25th, 2015, 08:02 AM   #5
Global Moderator

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 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

 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.
 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!
 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?
October 27th, 2015, 05:36 PM   #9
Global Moderator

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 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.

 October 31st, 2015, 04:12 PM #10 Newbie   Joined: Oct 2015 From: Finland Posts: 4 Thanks: 0 I guess no one can solve this.

 Tags equation, fast, hard

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post victoriamath Algebra 13 August 11th, 2014 08:48 AM mjbecnel Algebra 7 March 5th, 2014 03:50 AM eliyaoo32 Algebra 5 June 17th, 2013 07:35 AM llambi Algebra 17 May 4th, 2011 11:18 AM mike000 Number Theory 1 June 9th, 2008 11:59 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top