So i have four groups of four people, 1-4 5-8 9-12 13-16 How many tables would i need to have one person from each group sit with a different person from each group of 4. So i have 1 5 9 13 at one table, then 1 5 9 14, 1 5 9 15, 1 5 9 16, 1 6 9 13 and continue until every person in each group has sat at a table with each of the four people from the other groups? There can only be one person from each group at any one table, but all people from all the different groups must sit together once. i get 64, basic 16 combintions in each group, am i simplifying it, 16 + 16 + 16 +16 or just confusing myself Help LOL And looking at that im thinking 48, ouch it hurts
It has a name Thanks I did think that, the multiply that is, but seemed too high, although i did think 64 was too low and seemed too easy to get to.
144? Im not sure multiplying is the answer, this isnt my thing but take the first block green, green can only join 4 in the next group, but all four of them can make 4 connections each to the next group (16) who can also make 4 connections each to the final group (16) a total of 36 add blue, yellow and red who repeat greens connections from their own blocks = 4x36 total 144? Even looking at it im still not sure
If I understood correctly, each person has to meet all the people from all the other groups at least once, right? If that's correct, then the list of 4*4*4*4 tables has a ton of redundancy, as in, pairs of people who meet multiple times at different tables even though they don't need to meet more than once. You only need 16 tables, for example: If you check it, everyone met everyone else from other 3 groups exactly once. Take for example person xx2x: Yup, he met everyone from other groups at these four tables. (Or is it "on these four tables" in this situation?) I have no formulas, unfortunately, I was curious and just brute-forced it.
Lol, im not sure i explained it correctly, 4 groups of 4, people can sit together more than once but never two from the same group yep im confused. I think the answer i was looking for is 144 but had to visualise it to get it and even then im not sure
Well, my set of tables achieves that, no? People can sit together more than once, but they don't have to, and also it increases the number of tables you need. If you throw away all the tables that aren't necessary to fulfil the requirements of meeting at least once, you end up with only 16 tables. Anyway, the formulation is the most important part in this type of problems, so make sure it was correct. I'm sure there's an error in the way you got 144, but I can't point out what exactly is wrong... For example, why did you choose exactly this step, the penultimate one, to switch from adding to multiplying? Why not this? (You get 4*(4+16+4)*4 = 384 tables.) Or this? (You get 16+16+16 = 48 tables.) P.S. You can see you have a redundancy in your scheme too. While groups 3 and 4 change their sits to meet each other, Green-1 and Green-2 keep sitting with each other many times in a row, then it's Green-1 and Blue-2, and so on. It's not forbidden, but it's not required either; you can arrange tables in a way to avoid unnecessary repetitions like that. If you want all the possible combinations then 256 is the answer. 1111, 1112, 1113, 1114, 1121, 1122, 1123, etc. to 4444. If you only care about each person meeting everyone else, it's as little as 16.
I just found out that even if you only have two or three groups of 4 people, you'd still need the same 16 tables for all of them to meet everyone from other groups. It blows my mind, I can't figure out how it works.
History As if my brain dosnt hurt enough. Where to start, try same image different orientation. Im still not convinced myself at either 144 nor 256 Edit - yes i am 144 LOL Should have done it with arrows, these connections are one way, left to right (edit - makes no difference) Every person from group 1 has to sit at a table with all the people from groups 2, 3 and 4, i may have missed this next bit, there has to be 4 people at each table, 1 from each group every time, no 2 people from the same group can ever sit at the same table but the same people from different groups can sit at the same table, so gp1 bp1 yp1 rp1 and gp1 bp1 yp1 rp2 is ok but gp1 bp1 bp2 yp1 is not. Using group 1 person 1 and added their blue neighbours whos connections to yellow and red added together, the multiplication at the end was the number of people in group 1 and how many times the connections are repeated for Green 2-4. Green person 1 can sit at 1 table with blue p1, yellow p1 and red p1, that is 1 table to start. Green person 1 can sit at another table with blue p1, yellow p1 and red p2 that is 2 tables. Green person 1 can sit at another table with blue p1, yellow p1 and red p3 3 tables Green person 1 can sit at another table with blue p1, yellow p1 and red p4 4 tables Green p1 then sits at a table with blue p1 and yellow p2 and red p1 5 tables Green p1 then sits at a table with blue p1 and yellow p2 and red p2 6 tables and so on and so on, does that make sense? Green p1 can only sit with p1-4 blue initially, but p1-4 blue can make 16 original\different combinations to the yellow group and the same yellow can make 16 original\different combinations with the red group 4 green p1 to blue p1-4 16 blue p1-4 to yellow p1-4 16 yellow p1-4 to red p1-4 36 total repeat for green p2 p3 and p4 4x36=144
Ah, I get it, it was the way I mark these people that confused you. I decided to skip colours and instead simply tag them with numbers. So, each group consists of people numbered from 1 to 4 (you also numbered them like that in your last picture). The person's group is marked by a position. So, instead of writing something like this: "Green person 1 can sit at 1 table with blue p1, yellow p1 and red p1", I simply write "1111". Which are these people: When I write "2314" it means a table with: - person 2 from group G1 (also called "group green"); - person 3 from group G2 (also called "group blue"); - person 1 from group G3 (also called "group yellow"); - person 4 from group G4 (also called "group red"). So "2314" is a table with these people: When I write "3241", these aren't the same people in a different order, these are: - person 3 from group G1 (also called "group green"); - person 2 from group G2 (also called "group blue"); - person 4 from group G3 (also called "group yellow"); - person 1 from group G4 (also called "group red"). So, "3241" are these people: When I write "person xx2x" I mean person 2 from group G3/group yellow. This one:
Now look again at these 16 tables I suggested: No matter which person you take, you can verify he met everyone from all the other groups. Let's take this one for example, person 2 from group G3/"group yellow". Here he is, we can find him at these four tables: At these tables he met: - all four people from group G1/green (see, 1, 2, 3, and 4): - all four people from group G2/blue (all blue from 1 to 4 again): - and all four people from group G4/red (yup, from 1 to 4): Repeat with any other person you want.
If you start counting all the tables that are possible, i.e. all the tables that fit the requirements "a table must have 4 people; only one person from each group is allowed", you'll get 256 different tables, not 144. Trust me on that one. Start writing the tables down like that: 1st table: 1111, 2nd table: 1112, 3rd table: 1113, 4th table: 1114, 5th table: 1121, etc. You reach the end at the table 4444 (i.e. all people numbered "4" from each group), which would be exactly 256th table. ---- Well, here they are, all 256 of them (16 rows * 16 columns): And I marked all the tables from my solution.
I just want to share my level of confusion after browsing through this thread: And I thought understanding pneumatic trail is difficult...
Damn dude, i was so happy that i had my answer at 144 So its 256, back where we started 4x4x4x4. Seeing the final table (tell me you didnt type that out ) it makes much more sense even tho it hurts to look at, it is 256, but the way i was doing it or looking at it to find 144 made sense and i still see 144. You previously said it was wrong but not sure how or why, any ideas? Thanks for taking the time, appreciated.
Here is proof your solution is optimal: Every person (16 total) needs to meet all 4 people from the 3 other groups (12 total), so you have 16x12 = 192 'new meetings' that need to happen. On every table every person on that table (4 total) can meet at most 3 new people, so 12 'new meetings' can happen at most at every new table. So that means that you can never satisfy the conditions in less than 192/12 = 16 tables! I'm not sure if there is any way to mathematically prove if that minimal solution is actually possible, or if you just have to brute force it like you did, nice job anyway edit: in the same way you can also prove why you still need the 16 tables with only 2 or 3 groups as you found
I got it, had to go to photoshop and draw each person and table then joined the dots to see it, happy at 256 Thanks again for taking the time.
Oh, what's going on here, stochastics 101? I think part of the problem might be that you view these 16 elements as individual people but within each group you can replace them with any kind of object you like. Or maybe it's a bit confusing that it specifically mentions that there can never be two from the same group at the same table. (If this was the case, there would obviously be many many more possible combinations). A common variation of this type of exercise is using clothes, which might be a bit less confusing: You have 4 different hats, 4 different shirts, 4 different pairs of trousers and 4 different pairs of shoes. How many different ways of combining one outfit (= one set consisting of 1 hat, 1 shirt, 1 pair of trousers, 1 pair of shoes) are there if two items (f.e. hat#1 and shirt#3) can be combined more than once but you cannot wear two shirts or two hats at the same time (= no two people from the same group on one table)? In order to solve these types of questions you use the most basic principle of enumerative combinatorics to find out how many k-tuples can be formed from a given number of sets. In German this is called "allgemeines Zählprinzip", in English you refer to it as "multiplicative principle". And you rightly found out that you simply have to multiply the number of items in each given set to get the total number of possible sets (outfits). 256 in this case. When you got to 144 you were using the additive principle. It is the wrong method for this type of problem because the individual events are not disjointed or in other words they happen at the same time. Here's a rather intuitively accessible explanation of the difference between additive and multiplicative principle: http://discrete.openmathbooks.org/dmoi2/sec_counting-addmult.html Hope this helps.