/sci/ - Science & Math

Previous Thread >>10695011

[math] \mathbf{ \color{ red }{ \heartsuit } } [/math]

Do you think people solve these? The good people probably just solve them and don't even brag.

>>10702199
Sometimes people post solutions, just check the previous threads for proof. Regarding my motivation, I'm just mostly trying to contribute actual quality/wholesome oc to my favorite board on 4chan

>>10702148
We live in a society.

>>10702148
Get fucked you bitch cunt

>>10702217
Doing god's work anon.
>>10702148
So I suck at graph theory but let me at least try and give some ideas. Basically I thought one thing you could do is try to group the people. For some person P there are
a) Some amicable pairs in which both persons are hostile with P
b) Some amicable pairs in which only one person is hostile with P
c) The amicable pairs including P
It makes sense to classify things this way since it allows us to insert q as the sum of the members of a,b,c. So a+b+c=q, rearranging c=q-a-b. If a+b is greater than 4q^2/n^2 we're done, but I'm not sure how to proceed. I kept thinking an induction proof might work, but the fact that induction wouldn't work on q makes things awkward. The grouping is the best I've got right now.

>>10702249
Observe the angry CS major, who can’t even understand the problem presented before him

Considering I never used the formula given (except in the base cases), I feel like this must be wrong, but I can't immediately find the error.

>>10702152
>http://math.harvard.edu/putnam/ !!84u21X0KjW+ 06/05/19(Wed)23:45:17 No.10702152

namefag

>>10702217
Ironically /lit/ would probably be more accepting and better at solving the problems

>>10703023
uhh no

assuming the pairs are not ordered then how is this true for n=3?

wouldn't d(a,b) > 0, d(b,c) > 0, d(a,c) < 0 satisfy this condition? in this case, n=3,q=2, so q(1-4q/n^2) = 2*(1-4*2/9) = .222...

but c has 1 amicable pair. i'm probably reading it wrong.

>>10702148
>Prove that there is at least one member of the society whose foes include q(1−4q/n2) or fewer amicable pairs.

also this is worded strangely. their foes (people with whom they form a hostile pair?) are not pairs, they're individuals.

>>10703071
>>10703083
The question is about the number of amicable pairs between all the foes of a certain person.
Let's take person a in your example. He only has one foe, which is c.
There are 0 amicable pairs between the members of the set {c}, because it only contains one person.

>>10703159

ah, that's clearer then.

i think the condition on every set of three people just means that there are no length-3 cycles with "positive" weights. i guess the obvious thing to try is an induction on n. this seems like a really grindy problem though.

>>10702148
Let's see, take as a starting point the observation in
>>10702336
Where a(P), b(P) and c(P) are defined.
The problem is to find P such that a(P)+b(P)>= 4q^2/n^2.
Note that b(P) are the friends of the friends of P (except for P) because there are no friendly 3 parties.

So if you denote f(x,y) the characteristic function that is 1 if x and y are friendly, and 0 if they are hostile.
Then [math]a(P)+b(P)=\sum_{Q,R}f(P,Q)f(Q,R)[/math]
and [math]2q=\sum_{Q,R}f(Q,R)[/math]

Assume that a(P)+b(P)< 4q^2/n^2 for all P. Now sum over P and obtain
[math]\sum_{P,Q,R}f(P,Q)f(Q,R)<\frac{1}{n}(\sum_{Q,R}f(Q,R))^2[/math]
the one on the left is
[math]\sum_Q (\sum_R f(Q,R))^2[/math].
This contradicts Jensen's inequality
[math]\frac{1}{n}\sum_i f(a_i)\geq f(\frac{1}{n}\sum_i a_i)[/math]
for the convex function f(x)=x^2 and
[math]a_i[/math] the [math]\sum_R f(Q,R)[/math].

I had seen cauchy inequalities estimates before but this is the first time that I have made one like this work, thanks OP.

>>10703919
A correction:

I assume a(P) is the ones friendly with P, b(P) are the friendly pairs one of which is hostile to P and c(P) are the friendly pairs both of which are hostile.

(I think this relabeling is also necesary to make sense of the observation of the post
>>10702336 )