Решить по-русски

zhekas · Сообщение **zhekas** » 02 ноя 2011, 01:51

6.

на помежутке $1/2<x\le 1$ $1\le1/x < 2$ . Поэтому $\left\{\frac1x\right\}=\frac1x -1$
Аналогично

на помежутке $1/(n+1)<x\le 1/n$ $n\le1/x < n+1$ . Поэтому $\left\{\frac1x\right\}=\frac1x -n$

Получили

$I = \sum\limits_{n=1}^\infty \int\limits_{1/(n+1)}^{1/n} \frac1x-n\,dx = \sum\limits_{n=1}^\infty \left(\ln{\frac1n} - \ln{\frac1{n+1} - \frac1{n+1}\right)$

частичная сумма равна

$I_n = \ln{(n+1)} - \sum\limits_{k=1}^n\frac1{k+1} = \ln{(n+1)} - \sum\limits_{k=1}^{n+1}\frac1k +1$

в пределе получаем $1-\gamma$

Ian · Сообщение **Ian** » 02 ноя 2011, 09:32

Браво, Zhekas!
Хотя я при цитировании пропустил возведение в квадрат, но идейно задача осталось такой же, с ответами через константу Эйлера-Маскерони

Ian писал(а):Source of the post 6.Вычислить $\displaystyle \int_0^1\{\frac 1x\}dx$ , где фиг.скобки обозначают дробную часть числа.
Там есть пост, но недостигший нужного результата

А по ссылке находим $\displaystyle \int_0^1\{\frac 1x\}^2dx$ И теперь там есть и достигшие (3+4) А думают над $\displaystyle \int_0^1\{\frac 1x\}^ndx$
В связи с этим несколько слов о форуме?, с которого переводил. Число народу там в разы больше, чем у нас, как по зарегистрированным, так и в онлайне. (и dxdy, и мы, не говоря уж об остальных -в этом сравнении "микрофорумы") Но во столько же раз больше и число тем, возникающих в единицу времени. И неудивительно, что число просмотров каждой - примерно как у нас. Поэтому попробуем сравнить качество:
задачи 1 и 3 мы решили, а они все еще нет
Задачу 5 они решили раньше
Задачи 2 и 4 не поддались никому.
Задача 6 -сравнение невозможно.
Итого пока 2:1 :yes:

zhekas · Сообщение **zhekas** » 02 ноя 2011, 10:49

6. Для квадрата добавляется ещё один предел. Получается $\ln{(2\pi)} - \gamma-1$

BSK · Сообщение **BSK** » 03 ноя 2011, 10:16

a) верхняя часть рисунка
С нижнего левого угла единичного квадрата друг за другом выкладываем самые большие квадратики пока общая ширина не дестигнет единицы (или чуть больше). Синюю часть (по высоте самого малого квадрата отрежем и выкинем). Выкинутая площадь не больше $$H-h.$$

Сверху опять выложим самые большие квадраты, обрежем, выкинем. И так далее пока не израсходуем все квадратики. Если предположить, что заложить единичный квадрат не удалось, то выкинутая синяя часть не превосходит $$H,$$

т.е. не превосходит $$1.$$

Красных излишков тоже не более $$1.$$

Противоречие.

б) нижняя часть рисунка
С нижнего левого угла единичного квадрата друг за другом (вправо и вверх) выкладываем самые большие квадратики пока это сделать можно (за правый и верхний край теперь не заступать!) Цель - заложит уголок более чем наполовину, оставив тем самым на зелёный квадрат маленьких квадратиков общей площади не более половины зелёного. С синей частью все в порядке, она занимает по крайней мере половину соответствующей части уголка. Осталось увидеть, что и красная занимает по крайней мере половину, т.е. что $\frac{H^2}{2}+h^2 \ge 2hH-h^2.$ Это верно.

Ian · Сообщение **Ian** » 04 ноя 2011, 10:57

BSK, спасибо! Решение а) я понял, теперь и понятно, почему в задаче именно число 3 (возможно, верно и для меньших коэффициентов, но с большим усложнением решения. Для коэффициентов, меньших $1+\sqrt 2$ утверждение точно неверно)
Решение б) пока непонятно.
Теперь "красные" и "синие" Вы определяете другим способом?(но не указали как)
У Вас на определенном шаге в квадрате построена "этажерка",в занятых секциях которой квадратики занимают не менее 1/2 площади. Отсюда действительно следует, что неиспользованные квадратики составляют не более 1/2 площади незанятых прямоугольных секций. Но может, эти секции столь узки, что наибольший из оставшихся квадратиков не влезет по ширине? Такое могло бы случиться, если бы разбиение на секции проходило беспорядочно. Но какой у Вас порядок разбиения, пока не понял:(

BSK · Сообщение **BSK** » 05 ноя 2011, 06:57

а) В этой задаче для коэффициента меньше 3 утверждение неверно (квадратов для покрытия может оказаться всего 3, каждый с площадью меньше 1).

б) В левый нижний угол квадрата ставим самый большой квадратик со стороной $$H$$

. По нижней (и аналогично левой) границе квадрата вплотную друг к другу выстраиваем остальные квадратики в порядке убывания. Сторона последнего вместившегося квадратика равн $$h,$$

этот последний квадратик изображен красным, расстояние от этого красного квадратика до правой стенки квадрата меньше $$h.$$

Нашей целью является замостить часть исходного квадрата (лежащую вне зеленого квадрата и имеющую форму уголка толщиной $$H$$

) более чем наполовину. Половинку самого большого квадратика, который мы поставили в нижний левый угол, отнесем к горизонтальной нижней ножке уголка. Эта половинка вместе с самым правым красным квадратиком имеют большую площадь, чем непокрытая площадь уголка справа и выше красного квадратика.
Теперь разберёмся с частями угока, лежащими выше остальных квадратиков (они все синие), положенных вдоль нижней стенки. Если квадратик имеет высоту не менее $$H/2$$

(не ниже пунктирной линии), то его площадь составляет не менее половины соответстующей части уголка. На рисунке есть один такой.
Второй синий квадратик со стороной $$H_1$$

ниже пунктирной линии, поэтому его площадь меньше половины соответствуюшей части уголка. Но если он ниже пунктирной линии, то на него, не вылезая за границу уголка, можно поставить по крайней мере один следующий по размеру квадратик. Вот и будем над эти синим квадратиком по правой границе соответствующего участка уголка выставлять остальные квадратики, пока это позволяет верхняя граница уголка. Мы попали в исходную ситуацию (теперь роль квадратика $$H$$

играет квадратик $$H_1$$

)! И так далее и так далее. Чем закончится этот процесс? Либо израсходуем все квадратики, что хорошо, ведь это и было конечной цель. Либо не найдется квадратика, лежащего ниже своей пунктирной линии, что тоже хорошо, так как означает покрытие уголка не менее чем наполовину.

Ian · Сообщение **Ian** » 05 ноя 2011, 10:48

BSK писал(а):Source of the post
а) В этой задаче для коэффициента меньше 3 утверждение неверно (квадратов для покрытия может оказаться всего 3, каждый с площадью меньше 1).

Квадраты можно развернуть 2 под 45^о, а один в угол, условие не запрещает разворот

б) В левый нижний угол квадрата ставим самый большой квадратик со стороной . По нижней (и аналогично левой) границе квадрата вплотную друг к другу выстраиваем остальные квадратики в порядке убывания. Сторона последнего вместившегося квадратика равн этот последний квадратик изображен красным, расстояние от этого красного квадратика до правой стенки квадрата меньше
Нашей целью является замостить часть исходного квадрата (лежащую вне зеленого квадрата и имеющую форму уголка толщиной ) более чем наполовину.

Толщиной скорей уж назвать $$1-H$$

, а

тогда длина "крыла"="полки" уголка. И дальше надо разбираться, где у Вас Н, а где 1-Н

Половинку самого большого квадратика, который мы поставили в нижний левый угол, отнесем к горизонтальной нижней ножке уголка. Эта половинка вместе с самым правым красным квадратиком имеют большую площадь, чем непокрытая площадь уголка справа и выше красного квадратика.
Теперь разберёмся с частями угока, лежащими выше остальных квадратиков (они все синие), положенных вдоль нижней стенки. Если квадратик имеет высоту не менее (не ниже пунктирной линии), то его площадь составляет не менее половины соответстующей части уголка. На рисунке есть один такой.
Второй синий квадратик со стороной ниже пунктирной линии, поэтому его площадь меньше половины соответствуюшей части уголка. Но если он ниже пунктирной линии, то на него, не вылезая за границу уголка, можно поставить по крайней мере один следующий по размеру квадратик. Вот и будем над эти синим квадратиком по правой границе соответствующего участка уголка выставлять остальные квадратики, пока это позволяет верхняя граница уголка. Мы попали в исходную ситуацию (теперь роль квадратика играет квадратик )! И так далее и так далее. Чем закончится этот процесс? Либо израсходуем все квадратики, что хорошо, ведь это и было конечной цель. Либо не найдется квадратика, лежащего ниже своей пунктирной линии, что тоже хорошо, так как означает покрытие уголка не менее чем наполовину.

Не только. Еще может тривиально кончиться место, куда упаковывать. Но тогда квадрат полностью (?как доказать?) разбит на прямоугольники, в каждом из которых площадь упакованных квадратиков составляет не меньше половины их площади.
Мне кажется, что задача BSK скорей решена, чем нет, но хотелось бы сделать еще усилия в сторону точного изложения алгоритма упаковки, ну и всего доказательства. Применена рекурсия. Но то, что можно сделать рекурсией, то можно и доказать индукцией.
Предлагаю индукционное утверждение: Пусть даны n квадратиков со сторонами $a_1\leqslant a_2\leqslant ...\leqslant a_n$ и прямоугольник $A\times B,A\leqslant B$ , такие, что 1) $\sum_{i=1}^n a_i^2\leqslant \frac{AB}2$ и 2) $a_n\leqslant A$ , Тогда квадратики можно разместить без пересечений (по границам пересекать можно) внутри прямоугольника

BSK · Сообщение **BSK** » 07 ноя 2011, 06:16

Ian писал(а):Source of the post
BSK писал(а):Source of the post Чем закончится этот процесс? Либо израсходуем все квадратики, что хорошо, ведь это и было конечной цель. Либо не найдется квадратика, лежащего ниже своей пунктирной линии, что тоже хорошо, так как означает покрытие уголка не менее чем наполовину.
Не только. Еще может тривиально кончиться место, куда упаковывать.

Никаких "ещё". Если кончилось место, все квадратики (кроме самого правого в своей области, на него наплевать) лежат выше своей пунктирной линии, я об этом сказал.

Всегда очередной ход делаем самым большим из оставшихся квадратиков.
Красная часть покрыта более чем наполовину.
Синие части 1 и 2 покрыты более чем наполовину.
Для синих частей 3 и 4 исходная задача сводится к двум зеленым задачам, в точности равным исходной задаче.
Одна зеленая область уже замощена более чем наполовину, в ней "тривиально кончилось место", радуемся.
Во второй зеленой области снова возникает исходная задача, т.е. место в ней не кончилось.

Под "исходной задачей" здесь подразумевается покрытие более чем наполовину прямоугольника с уже покрытым куском $$H$$

на

Ian · Сообщение **Ian** » 07 ноя 2011, 14:18

BSK, спасибо! теперь совсем понял. Пока понимал, думал как попроще реализовывать Ваш алгоритм, вышло, что ради изложения можно отказаться от фиктивных красных половинок и пунктирных линий.
Утверждение индукции, оно же задание алгоритму рекурсии:
Пусть $B\geqslantA=a_1\geqslant a_2\geqslant a_3...\geqslant a_n>0$ . Тогда либо 1)все квадратики можно упаковать в прямоугольник $A\times B$ , либо 2)найдется такое k, что первые k квадратиков со сторонами $$a_1,...a_k$$

имеют площадь более $\frac{AB}2$ но упаковываются в прямоугольник $B\times A$ .
Док-во.Процесс и рисунок Ваши: $$a_1$$

понятно как располагаем, $$a_2$$

рядом,

сначала пробуем над ним, если невозможно, то рядом. Если возможно, рекурсия. В итоге сторона исходного прямоугольника длиной В разобьется на некоторое количество m отрезков- сторон квадратиков и (m+1)-й отрезок короче чем $a_{k+1}$ .По предположению индукции для прямоугольников длиной А, а ширинами равными 2му,...m-му отрезкам, расположенные в них квадратики занимают не менее 50% их площади. А в 1-м и (m+1)м прямоугольниках, вместе взятых, $$a_1$$

составляет не менее 50% площади. Шаг индукции сделан, а база очевидна.
При бесконечном числе квадратиков тоже применимо, мы же фактически показали, что каждый конкретный квадратик рано или поздно войдет в упаковку.
Это было лишь переизложение решения BSK другими словами.

Вот задачка, по которой пока нет ответов
7.Дана таблица n*n.
1) в первый раз выбрали наибольшее число в таблице и вычеркнули строку и столбец, содержащие его. В полученной таблице снова проделали ту же операцию, и так n раз(на последнем шаге выбора не было).Выбранные n чисел сложили, получилось А
2) во второй раз в исходной таблице выбрали наименьшее число и вычеркнули строку и столбец, содержащие его. В полученной таблице снова проделали ту же операцию, и так n раз(на последнем шаге выбора не было).Выбранные n чисел сложили, получилось В.
Может ли оказаться, что B>A?
(Равные числа в таблице могут встретиться. Если в этих процессах получалось несколько наибольших/наименьших, можно брать любое)

BSK · Сообщение **BSK** » 08 ноя 2011, 07:05

Ian писал(а):Source of the post По предположению индукции для прямоугольников длиной А, а ширинами равными 2му,...m-му отрезкам, расположенные в них квадратики занимают не менее 50% их площади. А в 1-м и (m+1)м прямоугольниках, вместе взятых, составляет не менее 50% площади. Шаг индукции сделан, а база очевидна.
При бесконечном числе квадратиков тоже применимо, мы же фактически показали, что каждый конкретный квадратик рано или поздно войдет в упаковку.

Пара вопросов:
1) Где база индукции при бесконечном числе квадратиков?
2) Допустим, можем заложить прямоугольник высоты $$H$$

с уже накрытым куском $$H$$

на

(у меня

на

) не менее чем наполовину. Что дальше, как решать исходную задачу про то, как вместить в квадрат все маленькие квадратики?

yourdomain.com