Counting friends in two ways

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joybangla

836 posts

joybangla

#1 h May 11, 2014, 12:51 PM • 3 Y

Y by Adventure10, Mango247, Oly

Suppose a class contains $100$ students. Let, for $1\le i\le 100$ , the $i^{\text{th}}$ student have $a_i$ many friends. For $0\le j\le 99$ let us define $c_j$ to be the number of students who have strictly more than $j$ friends. Show that $\begin{align*} & \sum_{i=1}^{100}a_i=\sum_{j=0}^{99}c_j \end{align*}$

This post has been edited 1 time. Last edited by joybangla, May 11, 2014, 3:56 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tensor

433 posts

tensor

#2 h May 11, 2014, 1:11 PM • 2 Y

Y by Adventure10, Mango247

Come here in this thread post as many as you can.. http://www.artofproblemsolving.com/Forum/viewtopic.php?f=362&t=588965

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chaotic_iak

2932 posts

chaotic_iak

#3 h May 11, 2014, 3:14 PM • 1 Y

Y by Adventure10

I believe the problem is wrong. Just imagine a class with all students hating each other. $a_i = 0$ for all $i$ , but $c_0 = 100$ (and all other $c_j = 0$ ), so the equation becomes $0 = 100$ . Perhaps $c_j$ means the number of students with strictly more than $j$ friends.

If so, student $i$ is counted once for all $c_0, c_1, c_2, \ldots, c_{a_i-1}$ , namely $a_i$ times. Thus the sum of $c_j$ 's counts each student by the number of friends they have, which is exactly the left hand side.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joybangla

836 posts

joybangla

#4 h May 11, 2014, 3:58 PM • 1 Y

Y by Adventure10

Your counter-example is correct. I have edited it. So the problem was indeed wrong.

This is unexpected. And sad. Because I just proved a wrong problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tensor

433 posts

tensor

#5 h May 11, 2014, 4:13 PM • 1 Y

Y by Adventure10

Oho nooooo//// how that can be?? such institutes problem, that's implying evry one would probably get its all point....

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BISHAL_DEB

270 posts

BISHAL_DEB

#6 h May 11, 2014, 4:25 PM • 1 Y

Y by Adventure10

I did not explicitly mention that the problem is wrong but proved the correct version by using considering the students as points and friendship as line segment. I guess I should score

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BBAI

563 posts

BBAI

#7 h May 12, 2014, 8:32 AM • 3 Y

Y by Devarka, Adventure10, Mango247

A simple solution ,
The person having the $a_i$ friends is counted in $c_0,c_1, ....c_{a_i - 1}$ .i.e $a_i$ times . so in the RHS too it is counted $a_i$ times . so these are two different ways of counting the sum $\sum _{i=1}^{100} a_i$ and hence it is proved

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joybangla

836 posts

joybangla

#8 h May 12, 2014, 9:07 AM • 2 Y

Y by Adventure10, Mango247

BBAI wrote:

A simple solution ,
The person having the $a_i$ friends is counted in $c_0,c_1, ....c_{a_i - 1}$ .i.e $a_i$ times . so in the RHS too it is counted $a_i$ times . so these are two different ways of counting the sum $\sum _{i=1}^{100} a_i$ and hence it is proved

So what's new in your solution BBAI?

chaotic_iak already gave that "simple solution" of yours. Why bother repeating it?

chaotic_iak wrote:

I believe the problem is wrong. Just imagine a class with all students hating each other. $a_i = 0$ for all $i$ , but $c_0 = 100$ (and all other $c_j = 0$ ), so the equation becomes $0 = 100$ . Perhaps $c_j$ means the number of students with strictly more than $j$ friends.

If so, student $i$ is counted once for all $c_0, c_1, c_2, \ldots, c_{a_i-1}$ , namely $a_i$ times. Thus the sum of $c_j$ 's counts each student by the number of friends they have, which is exactly the left hand side.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sayantanchakraborty

505 posts

sayantanchakraborty

#9 h May 15, 2014, 12:13 PM • 3 Y

Y by ADEWADE, Adventure10, Mango247

Solution to the edited problem:

Consider a $100$ -gon with vertices $A_i$ ( $i=1....100$ ) as persons.We colour the segment $A_iA_j$ red if $A_i$ and $A_j$ are friends,otherwise we colour it as blue.We shall now show that both the sides number twice the number of red sides.

LHS:Consider a red line $A_iA_j$ .It is counted once when $a_i$ is counted and once when $a_j$ is counted.Thus LHS part is proved.

RHS:Let $c_i=r$ .While we are counting $c_i$ ,we are only counting $r$ redlines emanating from $A_{i_1},A_{i_2},...,A_{i_r}$ .This proves our claim for RHS.(Note that thus summing over the $c_i$ 's gives the sum of exact number of redlines originating from each vertex).

This problem is one of the simplest applications of two way counting.So nice to see this in ISI exams.....

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Target_cmi

113 posts

Target_cmi

#12 h Apr 18, 2017, 2:13 AM • 2 Y

Y by Adventure10, Mango247

If $c_j$ means the number of students with strictly more than $j$ friends. , then what is $c_{99}$ ? 0 ?

This post has been edited 1 time. Last edited by Target_cmi, Apr 18, 2017, 2:13 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

adityaguharoy

4657 posts

adityaguharoy

#13 h Apr 18, 2017, 10:33 AM • 2 Y

Y by Adventure10, Mango247

No there was that error in the original problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ftheftics

651 posts

ftheftics

#14 h Feb 1, 2020, 6:08 AM • 2 Y

Y by Gerninza, Adventure10

Translation to a graph theoretic problem

Suppose , $G(V,E)$ be a simple graph with $\boxed{k=100}$ vertex. Suppose $V=\{v_1,\cdots ,v_k\}$ And we connect $v_i,v_j$ if they are friend $i\neq j$ . Suppose $a_i = \deg (v_i)$ .And $\tau _j$ denote number of vertices having degree more than $j,0\le j \le k-1$ .

We would like to show that $\sum_{i=1}^k a_i = \sum_{j=0}^{k-1} \tau_j$ .

$\boxed{\text{Key Lemma}}$ .
$\sum_{j=0}^{k-1} \tau _j =2|E|$ .
Proof.
Suppose the statement is true for $k=n$ .
Then join a certex call $v_{n+1}$ .If it is isolated then $\sum_{i=0}^n \tau ' _i = \sum _{i=0}^{n-1} \tau_i$ , $\tau '_j$ count number of vertex having degree more than $j$ in the new graph with $n+1$ vertex. we are done.

if $v_{n+1}$ is not isolated. . Suppose it joins with $v_j$ , $j\le n$ . Then $\deg (v_{n+1})=1$ .
And , $\tau ' _{\deg v_j} = \tau_{\deg v_j} +1$ ,
$\tau '_0 =\tau_0 +1$ .
And another $\tau_j$ will as same as $\tau '_j$ .

So,in this case $\sum_{j=0}^{n} \tau '_j = 2|E|+2$ .One must see that number of edges in new graph is $|E|+1$ .

Similar approach can prove the case for more than $1$ new edges $\blacksquare$ .

Now , $\sum a_j = \sum_{v\in V} \deg (v)=2|E|$ .

So, $\sum_{i=1}^k a_i = \sum_{j=0}^{k-1} \tau_j$ .

Proved!!!!

This post has been edited 3 times. Last edited by ftheftics, Feb 1, 2020, 10:17 AM
Reason: Nlll

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cyberrushMIKU3799

51 posts

cyberrushMIKU3799

#15 h Jun 7, 2020, 7:57 AM

Y by

I have a different solution than the above ones.
I will use induction
obviously the base case holds true

Lets assume it holds for n students
Our n+1th student has say i friends
So the LHS will increment by i.
For RHS 1 will be added for each j from 0 to i so the RHS Will also increase by 1*i
So LHS = RHS and our induction for n+1th step is complete. $\blacksquare$

This post has been edited 3 times. Last edited by cyberrushMIKU3799, Jun 7, 2020, 7:59 AM
Reason: Latex typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

stranger_02

337 posts

stranger_02

#16 h Jun 21, 2020, 1:21 PM • 1 Y

Y by Mango247

chaotic_iak wrote:

I believe the problem is wrong. Just imagine a class with all students hating each other. $a_i = 0$ for all $i$ , but $c_0 = 100$ (and all other $c_j = 0$ ), so the equation becomes $0 = 100$ . Perhaps $c_j$ means the number of students with strictly more than $j$ friends.

If so, student $i$ is counted once for all $c_0, c_1, c_2, \ldots, c_{a_i-1}$ , namely $a_i$ times. Thus the sum of $c_j$ 's counts each student by the number of friends they have, which is exactly the left hand side.

No your argument is incorrect.. $c_0$ is NOT equal to $100$ , it is indeed $0$ . Observe the question carefully.. $c_0$ means the number of students having MORE than $0$ (i.e. $\geq1$ ) friends.. which according to your assumption that everyone hates everyone is indeed $0$ . For the same reason, the iteration of $j$ stops at $99$ and not $100$ because no one can possibly have $101$ friends.. hope I could make myself clear..

The problem is beautiful..

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

stranger_02

337 posts

stranger_02

#17 h Jun 21, 2020, 1:39 PM

Y by

joybangla wrote:

Suppose a class contains $100$ students. Let, for $1\le i\le 100$ , the $i^{\text{th}}$ student have $a_i$ many friends. For $0\le j\le 99$ let us define $c_j$ to be the number of students who have strictly more than $j$ friends. Show that $\begin{align*} & \sum_{i=1}^{100}a_i=\sum_{j=0}^{99}c_j \end{align*}$

Beautiful problems demand beautiful solutions.. Here's a simple way to think-

observe

if you still need help

my extension on this problem

Q.E.D. $\square$