/sci/ - Science & Math » Thread #12870817

91KiB, 768x512, mm.jpg

View Same Google iqdb SauceNAO

Anonymous Tue 23 Mar 03:32:15 2021 No.12870817 View Reply Original Report

Quoted By: >>12871427 >>12873215 >>12876628

There's a pile of candies, of colors 1...C. There are N_i candies for each color i. There are k kids.

We need to distribute the candies to the kids; each kid must have the same number of candies; each kid must have at least one candy in every color.

How many ways can this be done? (Candies are distinguishable even if they are of the same color)

Anonymous

Anonymous Tue 23 Mar 2021 07:33:59 No.12871427 Report

Quoted By: >>12871434 >>12876628

>>12870817
Is there a limit on how many candies there are?
ie can there be infinite candies?

Anonymous

Anonymous Tue 23 Mar 2021 07:36:39 No.12871434 Report

Quoted By: >>12871838 >>12876628

>>12871427
In the proof it shouldn't matter

Anonymous

Anonymous Tue 23 Mar 2021 10:39:06 No.12871838 Report

Quoted By: >>12876628

>>12871434
Do we have to take candies from certain kids and give them to others?

Anonymous

Anonymous Tue 23 Mar 2021 14:06:59 No.12872370 Report

Quoted By: >>12872809 >>12875423 >>12876628

obviously it's $k!^{c\left(\frac{\sum\limits_{i=1}^c(n_i-k)}{k}\right)}\prod\limits_{i=1}^k\prod\limits_{j=1}^c(n_j-i)\prod\limits_{m=1}^{\left(\frac{\sum\limits_{i=1}^c(n_i-k)}{k}\right)}\frac{\left(\sum\limits_{i=1}^c(n_i-mk)\right)!}{\left(\sum\limits_{i=1}^c(n_i-(m+1)k)\right)!}$

Anonymous

Anonymous Tue 23 Mar 2021 16:14:51 No.12872809 Report

Quoted By: >>12876628

>>12872370
dude. that's so complicated it's probably correct, you wouldn't just make it up.

Anonymous

Anonymous Tue 23 Mar 2021 18:12:10 No.12873215 Report

Quoted By: >>12873273 >>12873335 >>12874213 >>12875513 >>12876628

>>12870817
In order for the question to be tractable, we must
require N_i be greater or equal to number of kids
[or else a kid misses a color] and that each kid
has greater than or equal to C candies
[or else a kid doesn't have enough of a color].

Anonymous

Anonymous Tue 23 Mar 2021 18:24:00 No.12873273 Report

Quoted By:

>>12873215
Almost forgot that the sum of all N_i is divisible
by number of kids, k, as a max. limit
[or else the kids won't have the same candy].

Anonymous

Anonymous Tue 23 Mar 2021 18:34:34 No.12873335 Report

Quoted By: >>12876628

>>12873215
Also for the max. limit of candies a kid could
have, the sum of all N_i is the closest divisible
to k rounded down.

Anonymous

Anonymous Tue 23 Mar 2021 22:15:08 No.12874213 Report

Quoted By: >>12875513 >>12876628

>>12873215
no, the question is well defined. if there's no way to split the candies satisfying the conditions, the answer is simply 0.

Anonymous

Anonymous Wed 24 Mar 2021 00:30:34 No.12874778 Report

Quoted By: >>12876628

John is driving a car. Every minute, there's a 3% chance he misses a turn. At any time, John can spend 1 minute to check a map. If he misses a turn, he must drive back. How often should John check his map?

Anonymous

Anonymous Wed 24 Mar 2021 04:52:05 No.12875423 Report

Quoted By: >>12876628

>>12872370
This is double fisting my ass right now.
k faculty of the fucking speed of light and then what

Anonymous

Anonymous Wed 24 Mar 2021 05:38:17 No.12875513 Report

Quoted By: >>12876470 >>12876628

>>12873215
>>12874213
There are solutions, though. I'm running through
some examples.

Anonymous

Anonymous Wed 24 Mar 2021 12:02:19 No.12876470 Report

Quoted By: >>12876628

>>12875513
I'm almost there with the solution...

Anonymous

View Same Google iqdb SauceNAO IMG_20210324_085945394.jpg, 2MiB, 4096x3072

Anonymous Wed 24 Mar 2021 13:01:14 No.12876628 Report

Quoted By: >>12877032 >>12877211 >>12877635 >>12878415 >>12878459 >>12878482 >>12878505 >>12878597 >>12878809

>>12870817
>>12871427
>>12871434
>>12871838
>>12872370
>>12872809
>>12873215
>>12873335
>>12874213
>>12874778
>>12875423
>>12875513
>>12876470
I've done it everybody. It took me the entire night,
pic related is the formula for OP's question.

Notation:
>C is the number of colors in i={1,...,C}
>N_i is the number of candies in each color
>N is the sum total of all N_i
>k is the number of kids with k>0

Assumptions:
>N_i is greater or equal to k
>each kid gets minimum of C candies (one of each color)
>each kid gets maximum of the floor of N/k candies
>all candies distinguishable, even if the colors repeat

I'll be here to consider improvements to this formula.

Anonymous

Anonymous Wed 24 Mar 2021 15:31:46 No.12877032 Report

Quoted By: >>12877211

>>12876628
>that looks like a simple question
24 hours later
>brute force it, fuck.

Anonymous

Anonymous Wed 24 Mar 2021 16:26:00 No.12877211 Report

Quoted By:

>>12876628
>>12877032
Yep, it felt like that.

Anonymous

Anonymous Wed 24 Mar 2021 18:28:44 No.12877635 Report

Quoted By: >>12878415 >>12878459 >>12878482 >>12878505 >>12878597 >>12878809 >>12878940

>>12876628
This is the same formula as in the picture but
rendered in TeX and expanded for clarity and appreciation.

$\prod_{r=1}^{C}N_r(N_r-1)(N_r-2)\dotsm(N_r-(k-1))\cdot\left[1+\sum_{s=C+1}^{\left\lfloor\frac{N}{k}\right\rfloor}\left(\prod_{t=0}^{s-C-1}\left[(N-kC)-kt\right]\left[(N-kC)-(kt+1)\right]\left[(N-kC)-(kt+2)\right]\dotsm\left[(N-kC)-(kt+(k-1))\right]\right)\right]$

Anonymous

Anonymous Wed 24 Mar 2021 21:37:24 No.12878415 Report

Quoted By:

>>12876628
Some examples using the formula:

Let >>12877635 be denoted as $F([N_1,N_2,...,N_c],C,k)$

$F([3,1,2,5],4,4)=0$
>there's not enough candy per color as kids (at least 4)

$F([7,6,7,6],3,6)=0$
$F([7,6,7],4,6)=0$
>there's not enough color or candies per color respectively

$F([2,3,1,4],4,1)=46,968$
>low k compared with high C

$F([3,4,2,5],4,2)=133,320$

$F([6,7,8],3,5)=242,256$
>high k compared with low C

Anonymous

Anonymous Wed 24 Mar 2021 21:53:52 No.12878459 Report

Quoted By:

>>12876628
Some examples using the formula:

Let >>12877635 be denoted as $F([N_1,N_2,...N_c],C,k)$

$F([3,1,2,5],4,4)=0$
>there's not enough candy per color as kids (at least 4)

$F([7,6,7,6],3,6)=0$
$F([7,6,7],4,6)=0$
>there's not enough color or candies per color respectively

$F([2,3,1,4],4,1)=46,968$
>low k compared with high C

$F([3,4,2,5],4,2)=133,320$

$F([6,7,8],3,5)$
>high k compared with low C

Anonymous

Anonymous Wed 24 Mar 2021 22:02:47 No.12878482 Report

Quoted By:

Anonymous

Anonymous Wed 24 Mar 2021 22:08:13 No.12878505 Report

Quoted By: >>12878597

Anonymous

Anonymous Wed 24 Mar 2021 22:39:09 No.12878597 Report

Quoted By: >>12878809 >>12878940

>>12876628
>>12877635
doesn't work

For example, here >>12878505 you look at distributing 10 candies over 1 child.
The maximum amount of ways you could ever distribute 10 distinct candies over 1 child is 2^10 = 1024.
So the answer can't be bigger than 1024. Yet your formula gives 46968.

Anonymous

Anonymous Wed 24 Mar 2021 22:57:03 No.12878647 Report

Quoted By:

this sounds like it's perfect for a solution with a recurrence relation and a generating function, I'm too tired/stupid to come up with one right now though.

Anonymous

Anonymous Wed 24 Mar 2021 23:45:55 No.12878809 Report

Quoted By: >>12878940 >>12879023 >>12879311 >>12879327 >>12879361

>>12876628
>>12877635
>>12878597
That answer is correct for distributing 10 distinct
candies over one child. However, the problem
states that the child must have at least one
candy of every color assuming all candies are
distinct.

So, the child first satisfies having one color
of each by having a choice of 2 by 3 by 1 by 4,
or 24. Then, I add over the possibilities of
having more than 4 candies up to a max of 10.
From 5 candies onwards, it's down to how many
distinct candies remain regardless of color.

The count is then:

$24\cdot(1+[6+(6\cdot5)+(6\cdot5\cdot4)+(6\cdot5\cdot4\cdot3)+(6\cdot5\cdot4\cdot3\cdot2)+(6\cdot5\cdot4\cdot3\cdot2\cdot1)])=\\24+144+720+2,880+8,640+17,280+17,280=46,968$

Anonymous

Anonymous Thu 25 Mar 2021 00:21:21 No.12878940 Report

Quoted By: >>12879023

>>12877635
>>12878597
>>12878809
Wait...actually I don't think 1024 is correct for
distributing 10 distinct candies over one child.
If you can show me this, I might have an idea.

Anonymous

Anonymous Thu 25 Mar 2021 00:39:52 No.12879023 Report

Quoted By: >>12879085 >>12879311

>>12878809
>>12878940
I'm not saying the answer should be 1024.
I'm saying 1024 is an upper limit to what the answer can be.
Forget about color for a second. If you have 10 distinct elements, the number of ways you can choose a selection from these elements is 2^10 = 1024. So the answer CAN NOT be bigger than this.

Anonymous

Anonymous Thu 25 Mar 2021 00:57:05 No.12879085 Report

Quoted By: >>12879202

>>12879023
ps: I checked with a program and the correct answer to F([2,3,1,4],4,1) should be 315

Anonymous

Anonymous Thu 25 Mar 2021 01:35:30 No.12879202 Report

Quoted By: >>12879311 >>12879510 >>12884493

>>12879085
Ah and the way you get that is with:
$\prod_{i=1}^{C} (2^{N_i} - 1)$

So now we know how to solve it for k=1 at least lol.

Anonymous

Anonymous Thu 25 Mar 2021 02:12:09 No.12879311 Report

Quoted By: >>12879419 >>12879510

>>12878809
>>12879023
Okay, I get it now. 1024 is from the sum of no
distinct candies at a time up to 10 distinct candies
at a time, not counting order. This is assuming
that the child starts with no candy and goes up
to 10 candies, resulting in 1024 ways.

My calculations don't start from zero for the
child because of the condition the child must
have a minimum of 4 candies, one of each color.

Also, >>12879202 is a nice looking start for k=1
but there is the case that I might get a repeated
color from the start (4 candies) and I won't have
all the colors.

Anonymous

Anonymous Thu 25 Mar 2021 02:21:44 No.12879327 Report

Quoted By: >>12879361

>>12878809
What the hell are you guys talking about? If there is only one kid, there is one way to distribute the candies, i.e. give them all to the kid.

Or are you guys thinking there could be leftover candies?

Anonymous

Anonymous Thu 25 Mar 2021 02:32:33 No.12879361 Report

Quoted By:

>>12878809
>>12879327
It is true that all of the candies can be given to
the one kid, but there's the possibility of the kid
having less candies. Also, the kid is required to
have a minimum of C candies from the start, one
candy for each color.

Anonymous

Anonymous Thu 25 Mar 2021 02:48:01 No.12879419 Report

Quoted By: >>12879510

>>12879311
I don't know what you mean. My formula works correctly for k=1.
We can look at a small example if you want: 2 red and 3 blue candies.
The formula gives (2^2 - 1) * (2^3 - 1) = 21.

Let's call the candies R1, R2, B1, B2, B3.
Then indeed there are 21 possible selections satisfying the requirements of having at least on of each color:

(R1,B1)
(R1,B2)
(R1,B3)
(R2,B1)
(R2,B2)
(R2,B3)
(R1,B1,B2)
(R1,B1,B3)
(R1,B2,B3)
(R2,B1,B2)
(R2,B1,B3)
(R2,B2,B3)
(R1,B1,B2,B3)
(R2,B1,B2,B3)
(R1,R2,B1)
(R1,R2,B2)
(R1,R2,B3)
(R1,R2,B1,B2)
(R1,R2,B1,B3)
(R1,R2,B2,B3)
(R1,R2,B1,B2,B3)

Anonymous

Anonymous Thu 25 Mar 2021 03:18:37 No.12879510 Report

Quoted By:

>>12879311
>>12879419
The first six on the list is perfect. I was concerned
of the situation where you have 2 reds or 2 blues
at the level of two candies.

At the level of three candies, I was expecting 18
(6 ways of red/blue duo times 3 remaining candies),
but I see 9--also in perfect arrangement.

At 4 candies, I expected 36 (6*3*2) but see five.
And one big 5 candy roster. I have overcounted,
but not sure why...

Well, >>12879202 is going straight to the front
of the formula.

Anonymous

Anonymous Thu 25 Mar 2021 11:54:05 No.12880816 Report

Quoted By:

bump

Anonymous

Anonymous Thu 25 Mar 2021 17:18:50 No.12881886 Report

Quoted By: >>12881896 >>12883431

Still getting the formula made...

Anonymous

Anonymous Thu 25 Mar 2021 17:20:57 No.12881896 Report

Quoted By: >>12883431

>>12881886
OP is sorry for wasting your time. Didn't know there are people so autistic.

Anonymous

Anonymous Thu 25 Mar 2021 22:46:46 No.12883414 Report

Quoted By: >>12888265

Anonymous

Anonymous Thu 25 Mar 2021 22:49:57 No.12883431 Report

Quoted By:

>>12881886
>>12881896
Well, if an actual formula were to come out from
all this effort and is regarded by /sci/ just one
time, it time well wasted.

Anonymous

Anonymous Fri 26 Mar 2021 05:01:55 No.12884493 Report

Quoted By: >>12885895

>>12879202
can it be extended to k>1?

Anonymous

Anonymous Fri 26 Mar 2021 15:17:24 No.12885895 Report

Quoted By:

>>12884493
maybe

Anonymous

Anonymous Fri 26 Mar 2021 23:57:19 No.12888265 Report

Quoted By:

>>12883414
bu

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches