For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

ket123
Posts: 1
Joined: Thu Aug 11, 2016 5:12 pm UTC

I'm so sorry my English.
I believe that me will be understand.

I have no clue at all as it calculate.

11 Czech students ,6 Slovak students , 14 Russian students, 6 Polish students and 6 Croatian students, studying in groups. Group is composed of one or more people. If the group has a minimum two students of the same nationality , then they must also have at least one student of another nationality. Calculate how many ways can be divided 43 students into groups??
Help: are looking for a number that has 39 digits

Thank you so much

LaserGuy
Posts: 4552
Joined: Thu Jan 15, 2009 5:33 pm UTC

This looks... tedious... to calculate. Is this homework?

I think the best thing to do here is start with a simpler problem, figure out a solution strategy, and the scale it up. Suppose we have 3 Czech students, 2 Slovak students and 2 Poles. Can you figure out how many combinations there are? If you can solve this problem, you can probably solve the big one as well.

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

Seems more like a challange from a math olympiad or something similar. Regular homework seldom require exact answers with 39 digits...

I think we should wait for ket to tell us where this problem is from, before we even attempt to give a solution.
(Personally, I have no idea how to find the exact solution without either writing a computer program or doing an extremely tedious calculation. I do have a very simple upper bound though, and it is - indeed - 39 digits)

LaserGuy
Posts: 4552
Joined: Thu Jan 15, 2009 5:33 pm UTC

Also, to clarify, are the students indistinguishable except by their ethnicity? Or can we interchange two Polish students and get a new grouping?

gmalivuk
GNU Terry Pratchett
Posts: 26529
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

I understood the 39 digit comment to be a hint about the size of the answer rather than a requirement of the precision.

I would also assume that students are distinguishable apart from their nationality, but that only nationality is relevant for determining groups.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC

gmalivuk wrote:I understood the 39 digit comment to be a hint about the size of the answer rather than a requirement of the precision.

Doesn't really matter.

The problem is way too difficult to be simple homework.

At any rate, there was a thread (now gone) outside xkcd where ket asked the same question and actually gave a specific 39-digit number as an approximation/guess of the answer (which is was different than the simple 39-digit upper bound, by the way)

And after some research, it is quite clear that there's some ulterior motive here. About a year ago, someone posted a very similar problem (different nationalities and numbers, but otherwise identical) and claimed it was a puzzle-for-the-audience from a Finnish TV show which gave out cash prizes.

I don't know whether he was telling the truth, but either way the game is afoot.

LaserGuy
Posts: 4552
Joined: Thu Jan 15, 2009 5:33 pm UTC

So, nerd sniping?

lorb
Posts: 405
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Well anyway.
The number of groups that can be formed is the number of permutations of 43 times the number of partitions of 43, assuming groups with identical number of nationalities but different students are distinct groups. (Which I think is a sensible assumption, given the setting.) From that number to get to the solution one would have to subtract the number of invalid groups which is every group of size 2+ that has only one nationality.

Is this thinking correct so far?
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

jaap
Posts: 2085
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

lorb wrote:Well anyway.
The number of groups that can be formed is the number of permutations of 43 times the number of partitions of 43, assuming groups with identical number of nationalities but different students are distinct groups. (Which I think is a sensible assumption, given the setting.) From that number to get to the solution one would have to subtract the number of invalid groups which is every group of size 2+ that has only one nationality.

Is this thinking correct so far?

I don't think so. That counts permutations of the people within a single group as distinct. For example, it gives 43! different ways of arranging them into a single group of 43 people, when there is only one way.

There is also a more subtle problem. If a partition has some groups of equal size, permuting those groups is counted as distinct solutions by your method. For example, the partition 20+20+3 results in these three groups
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
{21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
{41,42,43}
but also these three groups:
{21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
{41,42,43}
I would consider those the same, but your method counts them as different.

PsiCubed
Posts: 96
Joined: Thu Mar 03, 2016 11:13 am UTC