산술 평균을 최소화 할 수 있습니까?
허락하다 $n$양의 정수 여야합니다. 있습니다$2n$ $1$s는 화이트 보드에 적혀 있습니다. John은 다음 절차를 반복합니다.$3n$ 시간, 다음과 같이 :
두 개의 숫자를 선택하세요 $x,y$ 다음으로 각각을 교체하십시오. $2x+y, 2y+x$ 각기.
그의 목표는 숫자의 산술 평균을 가능한 한 낮게 만드는 것입니다. 그의 최고의 전략은 무엇이며 최고의 산술 평균은 무엇입니까?
수학 올림피아드 교육의 수업 과제에 약간의 수정이 있습니다.
힌트:
IMO 문제에서 일반적으로 사용되는 부등식을 사용합니다.
답변
이것은 첫눈에 나타날 수있는 것처럼 명확하지 않습니다. 예를 들어, 게으른 가정
작을수록 좋다
입니다 하지 올바른. 예$n=2$. 이미 첫 번째 단계 이후$1,1,3,3$ 최적의 다음 단계는
$1,1$ 또는 $3,3$
하지만
$1,3$ 보다 작더라도 $3,3$.
실제 증명의 기술로 들어가기 전에 먼저 트릭 이 무엇인지 설명하겠습니다 .
트릭은 추적에 있습니다. 생각하지 마십시오. $x\mapsto 2x+y$, 생각하세요 $x\mapsto x+2y$!
공식 증명 ( 'orrbile 형식 수정에 대해 @bobble에게 감사드립니다) :
표기법 : 동일한 레이블 세트를 유지하는 것이 편리합니다. $\alpha,\beta,\gamma,...$ 진화하는 숫자에 대해 아주 형식적으로 우리는 $X(k) = X_\alpha(k),X_\beta(k),...$ 어디 $k$걸음 수입니다. 우리는 이것을 작성하여 대폭 축약 할 것입니다.$a = X_\alpha(k),b = X_\beta(k)$ 등. 레이블은 평균에 영향을 미치지 않으므로 각 단계에서 선택할 수 있습니다. $S^\times_{\alpha\beta}:a,b \mapsto a+2b,b+2a$ 대 $S^=_{\alpha\beta}:a,b \mapsto 2a+b,2b+a$. (우리는 첫 번째 옵션을 고수하고 두 번째 옵션을 전혀 사용하지 않을 것입니다.) 물론 참조되지 않은 숫자는 변경되지 않은 것으로 이해됩니다. 또한 실제로 처리하지 않고 스왑 할 수 있어야합니다.$\times_{\alpha\beta}: a,b \mapsto b,a$. 이것은 순전히 장부 보관이기 때문에 이러한 종류의 단계는$k$.
우리는 탐욕스러운 전략, "항상 가장 작은 두 숫자를 취하라"가 최적이라고 주장합니다. 이것은 마지막 단계에서 분명합니다. 탐욕이 마지막에 최적 인 것으로 나타났다고 가정합니다.$k$ 상태에 관계없이 단계가 있지만 상태가 있습니다. $X(3n-(k+1))$가장 작은 두 개를 취하는 것이 최적이 아닙니다. 최적의 단계를$S^\times_{\alpha\beta}$. 가정하면 최적의 다음 단계를 탐욕스러운 단계로 선택할 수 있습니다.$S^\times_{\gamma\delta}$. 세 가지 경우 :
1)$\alpha=\gamma,\beta=\delta$: 욕심이없는 첫 걸음을 내디뎠 기 때문일 수 없습니다.
2)$\alpha\ne\gamma,\beta\ne\gamma,\alpha\ne\delta,\beta\ne\delta$ 분명히 왜냐하면
$S^\times_{\alpha\beta} \circ S^\times_{\gamma\delta}=S^\times_{\gamma\delta} \circ S^\times_{\alpha\beta}$첫 번째 단계에서 욕심이 최적이 아니라고 가정했습니다.
마지막 사건을 해결하기 전에 부분 주문을 소개하겠습니다.$X(k)<X'(k)$ 어디 $<$ 방법 $X_\psi(k)\le X'_\psi(k)$ 모든 $\psi \in \{\alpha,\beta,...\}$불평등 중 적어도 하나는 엄격합니다. 분명히$X(k)<X'(k)$ 둘 다 동일한 단계를 거친 다음 $X(k+1)<X'(k+1)$.
삼)$\alpha\ne\gamma,\beta=\delta$ 그런 다음 가정에 의해 $c<a$. 직접 컴퓨팅$X(3n-(k-1))$ 수확량
$S^\times_{\beta\gamma} \circ S^\times_{\alpha\beta}: a,b,c \mapsto a+2b,b+2a+2c,4a+2b+c$
최적이라고 가정했던 원래의 두 단계를 사용하면
우리가 그들을 바꾸고 나중에 레이블도 바꾸면$\alpha$ 과 $\gamma$ 우리는 얻는다
$\times_{\alpha\gamma}\circ S^\times_{\alpha\beta} \circ S^\times_{\beta\gamma}: a,b,c \mapsto c+2b,b+2a+2c,4c+2b+a$
이 상태는 아마도 최적의 절차로 얻은 것보다 구성 요소 적으로 더 좋거나 같기 때문에 이것은 모순입니다. $\square$
거의 잊어 버렸습니다. 물론 최소값은
27
면책 조항 : 이것은 건방진 대답입니다.
함수가 모든 양의 정수에 대해 엄격하게 증가하기 때문에 간단한 대답은 함수에 각 단계에서 가장 작은 숫자를 제공하는 것입니다. 결과$n$ (1,1) ~ (3,3), 다른 $n$ (3,3)에서 (9,9)까지의 작업 및 마지막 $n$ 작업은 (9,9)에서 (27,27), 평균 27입니다.
그러나 수수께끼의 대답은 평균 의 정의를 더 신중하게 선택해야한다는 것 입니다. 평균 을 선택하는 대신 모드를 선택해야 합니다 ( 이 경우 중앙값 이 잘 작동 함). 그런 다음$n=2$ (위의 'straightforward'알고리즘을 사용하는 경우) 함수를 적용합니다. $3n$같은 숫자 쌍에 시간. 이 숫자는$3^{3n}$, 나머지는 모두 1로 유지됩니다.
평균 $n=1$ 과 $n=2$ 여전히 27이지만 $n>2$, 평균 (중앙값 또는 모드)은 이제 1입니다.
깔개 아래에있는 두 가지 변칙을 쓸 수 있을까요? 그래, 우리가 수수께끼 각도를 더 밀면 . 다음은 문제 설명입니다.
그의 목표는 숫자의 평균을 가능한 한 낮게 만드는 것입니다. 그의 최고의 전략은 무엇이며 최고의 평균은 무엇입니까?
그들이 어떤 "숫자"를 가리키는 지 명시되어 있지 않으므로 중앙값 (media?)의 순서를 27, 27, 1, 1, 1, ...로 선택하겠습니다. 이 무한 수열 의 중앙값 또는 최빈값 은 물론 1입니다.
따라서 가장 좋은 평균은 건방진 전략을 사용하는 1 (또는 간단한 전략을 사용하는 27)입니다.
각 단계는 합계를 2 * (x + y)만큼 증가시킵니다. 특정 단계에서 최소 합계 증가는 사용 가능한 가장 낮은 두 숫자를 사용하는 경우입니다. 그러나 이것은 욕심 많은 알고가 최고임을 보여주기에는 충분하지 않습니다.
y = x + d를 취하고 3x + d, 3x + 2d로 변환 한 후 숫자를 다시 씁니다. 이제 다른 숫자 w를 소개합니다. w = x + e; e <d (및 e> = 0). 나중에 다른 작업으로 3x + 2d, 5x + 2e + d, 7x + e + 2d로 끝납니다. 이 숫자를 3x + 2e, 5x + e + 2d, 7x + 2e + d와 대조하십시오. 먼저 x와 w를 혼합 한 다음 y를 혼합에 추가합니다. 차이점은 2 * (de); -(de); (de); 그리고 그 합계는 분명히 탐욕스러운 알고리즘을 선호합니다. d가 거 대해서 2 번째 항이 욕심이없는 경우 실제로 가장 작다고 가정하더라도 차이는 여전히 2x + d,-(2x + e), de-이므로 2 번째 항은 욕심이없는 경우 다시 더 작습니다. 경우, 가장 작은 2 개 용어의 합이 다시 한 번 탐욕스러운 알고리즘을 선호합니다.
모든 경우에 비 욕심쟁이 알고리즘보다 욕심에 의해 모든 숫자가 작은 연산을 찾을 수는 없지만 위의 내용은 가장 작은 2의 합이 이미 탐욕 알고리즘을 선호한다는 것을 보여줍니다.