수학 문제 하나..

camelcricket의 이미지

궁금해 죽겠는데
머리가 나빠서 답이 안나옵니다.

0보다 큰 정수를 원소로 갖는 집합 A, B 가 있습니다.
A B 가 갖는 원소의 갯수는 같구요, 유한개의 원소를 갖습니다.

A 와 B 의 원소를 한개씩 뽑아서 곱하고, 그걸 싹 더한값이 최소가 나오게 하려면

어떻게 해야 할까요?

그냥 직감으로는
A 집합에서는 가장 큰 수를 차례대로 뽑고,
B 집합에서는 가장 작은 수를 차례대로 뽑아서
둘이 곱하면 왠지 가장 작을거 같은데..

증명을 못하겠음..

아.. 난 왜 주말에 방구석에서 이런걸로 괴로워 하는 걸까아..

kkb110의 이미지

생각하신 알고리즘에 대한 counter example 입니다

A,B = {-2, -1, 1, 2}

자연수가 아니고 정수면 좀 복잡할거같은데요? np hard 문제일 수도 있을 것 같은데..

+
아 0보다 큰 정수 이군요 ㅋㅋ

snowall의 이미지

일단 A=B=(1,2,3, ... , n)으로 이루어진 집합에 대해서는 k*(n-k)를 곱해서 k에 대해 더하는 방법이 답인 것 같네요

임의의 a(n)에 대해서도 그럴지는 생각을 해 봐야겠는데, 그럴 것 같긴 합니다...

피할 수 있을때 즐겨라! http://melotopia.net/b

kkb110의 이미지

집합 A와 B를 페어링하는 문제로 생각할때, 일단 임의의 페어들이 주어졌다고 생각해봅시다. {(a1,b2),(a3,b1),......}

이 중에서 두 페어를 뽑아내 p1,p2,q1,q2라고 이름붙여봅니다. (p1,q1),(p2,q2)

일단 p1 < p2, q1 < q2 이면

p1(q2-q1) < p2(q2-q1)
p2*q2 + p1*q2 < q1*p2 + p1*q2

따라서 (p1,q2),(p2,q1)으로 치환하는 것이 전체 식의 값을 낮추게됩니다.

이렇게 한번 치환을 임의의 두 페어에 대해서 한다고 치면, 유일하게 치환을 해서 식의 값이 낮아지지 않는 페어집합은 글쓴이님께서 제시하신, 역순으로 짝을 맞추는 방법밖엔 없습니다.(완전한 증명을 위해서 보충 설명이 필요하지만 생략.)

예)n=5, {(a1,b5),(a2,b4),(a3,b3),(a4,b2),(a5,b1)}

증명끝.

camelcricket의 이미지

우왕~ 감사합니다~

정리하자면

집합 A 와 B 를 페어링 하는 문제로, 각각의 페어의 곱을 합한 것이 최소가 되야 함.

그런데 (P1, Q1) , (P2, Q2) 에서
P1 < P2 이면, Q2 < Q1 이어야 값이 더 작다.

각각의 페어의 곱이 최소가 되어야 합도 최소가 되므로,
위의 조건에 어긋나는 페어가 없어야 함.
(만약 있다면 더 작아질 수 있으므로 최소값이 아님)

각 페어의 첫번째 원소를 크기가 작은 순서부터 나열했을때
P1 < P2 이면, Q1 > Q2 이므로

P1 < P2 < P3 < P4 < P5 < .... < Pn
Q1 > Q2 > Q3 > Q4 > Q5 > .... > Qn

흐아~ 돌대가리라서 이렇게까지 해도 헷갈리긴하네요 ㅋ

kkb110의 이미지

네 맞습니다. ^^

단지 좀만 엄밀하게 증명해보자면 ...다음과 같이 제시하신 것이 조건(페어치환으로 더 작아질 수 없음)을 충족하는 패어집합 이긴 한데,

P1 < P2 < P3 < P4 < P5 < .... < Pn
Q1 > Q2 > Q3 > Q4 > Q5 > .... > Qn

한발짝 더 나가서, 이것이 모든 가능한 패어집합중에 유일하게 조건을 충족하는 패어집합인지를 증명해야합니다.
왜냐하면, 위 조건은 해가 되기 위한 필요조건이지, 충분조건이 *아직* 아니니까요. (충분조건이긴 하지만, 증명해야함.)

ifree의 이미지

A = { ai | i 는 1에서 n 까지의 정수}
B = { bi | i 는 1에서 n 까지의 정수}

A 를 커지는 순서로 정렬하고 B 는 작아지는 순서로 정렬되었다고 가정하면
i < j 이면 ai < aj, bi > bj

S = a1*b1 + ... + ai*bi + ... + aj*bj + ... + an*bn

위식에서 B 의 임의로 두 원소를 치환하여 그 값을 S1 이라 하면,

S1 = a1*b1 + ... + ai*bj + ... + aj*bi + ... + an*bn

S1 - S = ai*bj + aj*bi - ( ai*bi + aj*bj )
= (aj - ai)*(bi - bj) > 0

즉 S 의 식에서 임의의 두 b 값을 바꾸면 값이 커지게 되므로 S 가 최소값임.

같은 소리구나!