Детская олимпиадная задача

[Профессор Снэйп]

ewert в сообщении #231900 писал(а):

Что значит "нестрого"? То, что предлагал я -- было лишь тривиальными оценками.

Простите, я не утверждал, что Вы что-то делаете нестрого.

Если честно, то вообще слабо вникал в тему. Просто прочитал условие исходной задачи, а потом, проглядев всё написанное в теме по диагонали, обнаружил, что все обсуждают правильную мозаику. Но если удастся найти ответ для правильной мозаики, то будет ли это ответом на исходный вопрос? Я Вас так понял, что геометрическая интуиция подсказывает, что да, будет, но строго это не доказано.

[vvvv]

ewert в сообщении #231900 писал(а):

Профессор Снэйп в сообщении #231896 писал(а):

То есть это не строго?

Что значит "нестрого"? То, что предлагал я -- было лишь тривиальными оценками.

-- Чт июл 30, 2009 01:13:41 --

vvvv в сообщении #231898 писал(а):

на каком диаметре Вы располагаете второй слой точек? Если на 15, то 16 точек там не разместятся

Не разместились бы; но они и не "на диаметре", а просто поставлены методом какого-то научного тыка.

Имелось в виду, конечно, не на диаметре, а на окружности диаметра 15.Вот только разметчик молчит

[ewert]

Профессор Снэйп в сообщении #231903 писал(а):

Но если удастся найти ответ для правильной мозаики, то будет ли это ответом на исходный вопрос? Я Вас так понял, что геометрическая интуиция подсказывает, что да, будет, но строго это не доказано.

Нет-нет, конечно, скорее всего, не будет (и фактически не есть), но это -- некая оценка, от которой можно отталкиваться.

vvvv в сообщении #231904 писал(а):

Имелось в виду, конечно, не на диаметре, а на окружности диаметра 15.Вот только разметчик молчит

Ну он же нарисовал.

[venco]

vvvv в сообщении #231898 писал(а):

venco в сообщении #231891 писал(а):

Видно?

Видно-то, видно, но только вопрос: на каком диаметре Вы располагаете второй слой точек? Если на 15, то 16 точек там не разместятся

Они не на диаметре.
Начиная с самой далёкой от центра точки пересечения (вверху слева на картинке), построил в обе стороны максимально далёкие от центра окружности. У последней (которая напротив от начальной точки) довольно много места.

[vvvv]

ewert в сообщении #231905 писал(а):

Профессор Снэйп в сообщении #231903 писал(а):

Но если удастся найти ответ для правильной мозаики, то будет ли это ответом на исходный вопрос? Я Вас так понял, что геометрическая интуиция подсказывает, что да, будет, но строго это не доказано.

Нет-нет, конечно, скорее всего, не будет (и фактически не есть), но это -- некая оценка, от которой можно отталкиваться.

vvvv в сообщении #231904 писал(а):

Имелось в виду, конечно, не на диаметре, а на окружности диаметра 15.Вот только разметчик молчит

Ну он же нарисовал.

Вот именно, нарисовал.У меня рисует компьютр по матформулам и заданным числам, а здесь - точно "научный втык ":)
Так все-таки, на окружности какого диаметра расположен второй слой точек, а если не на окружности, то как?

[venco]

vvvv в сообщении #231908 писал(а):

Вот именно, нарисовал.У меня рисует компьютр по матформулам и заданным числам, а здесь - точно "научный втык"

Вы что, думаете я ручками в пейнте круги рисовал?
Вот вам ещё симметричный вариант:


-- Ср июл 29, 2009 17:44:52 --

А вот и построение:

<?xml version="1.0" encoding="utf-8"?>
<CaR>
<Construction>
<Window x="0.007744872842107675" y="-0.03979150074484439" w="4.756828460010936"/>
<Objects>
<Point name="P1" n="0" hidden="true" x="0.0" y="0.0" shape="circle">Point at 0.0, 0.0</Point>
<Circle name="c1" n="3" fixed="3.5" midpoint="P1" acute="true">Circle around P1 with radius 3.5</Circle>
<PointOn name="P4" n="275" on="c1" alpha="-1.5707963267948966" x="2.143131898507868E-16" y="-3.5" shape="circle">Point on c1</PointOn>
<Circle name="c67" n="278" fixed="1" midpoint="P4" acute="true">Circle around P4 with radius 1</Circle>
<Intersection name="I130" n="279" first="c1" second="c67" shape="circle" which="second">Intersection between c1 and c67</Intersection>
<Circle name="c68" n="282" through="P4" midpoint="I130" acute="true">Circle around I130 through P4</Circle>
<Intersection name="I132" n="283" first="c1" second="c68" awayfrom="P4" shape="circle" which="second">Intersection between c1 and c68</Intersection>
<Circle name="c69" n="286" through="I130" midpoint="I132" acute="true">Circle around I132 through I130</Circle>
<Intersection name="I133" n="287" first="c69" second="c1" awayfrom="I130" shape="circle" which="first">Intersection between c69 and c1</Intersection>
<Circle name="c70" n="290" through="I132" midpoint="I133" acute="true">Circle around I133 through I132</Circle>
<Intersection name="I135" n="291" first="c70" second="c1" awayfrom="I132" shape="circle" which="first">Intersection between c70 and c1</Intersection>
<Circle name="c71" n="294" through="I133" midpoint="I135" acute="true">Circle around I135 through I133</Circle>
<Intersection name="I138" n="295" first="c1" second="c71" awayfrom="I133" shape="circle" which="second">Intersection between c1 and c71</Intersection>
<Circle name="c72" n="298" through="I135" midpoint="I138" acute="true">Circle around I138 through I135</Circle>
<Intersection name="I140" n="299" first="c1" second="c72" awayfrom="I135" shape="circle" which="second">Intersection between c1 and c72</Intersection>
<Circle name="c73" n="302" through="I138" midpoint="I140" acute="true">Circle around I140 through I138</Circle>
<Intersection name="I141" n="303" first="c73" second="c1" awayfrom="I138" shape="circle" which="first">Intersection between c73 and c1</Intersection>
<Circle name="c74" n="306" through="I140" midpoint="I141" acute="true">Circle around I141 through I140</Circle>
<Intersection name="I144" n="307" first="c1" second="c74" awayfrom="I140" shape="circle" which="second">Intersection between c1 and c74</Intersection>
<Circle name="c75" n="310" through="I141" midpoint="I144" acute="true">Circle around I144 through I141</Circle>
<Intersection name="I146" n="311" first="c67" second="c1" shape="circle" which="second">Intersection between c67 and c1</Intersection>
<Circle name="c76" n="314" through="P4" midpoint="I146" acute="true">Circle around I146 through P4</Circle>
<Intersection name="I147" n="315" first="c1" second="c76" awayfrom="P4" shape="circle" which="first">Intersection between c1 and c76</Intersection>
<Circle name="c77" n="318" through="I146" midpoint="I147" acute="true">Circle around I147 through I146</Circle>
<Intersection name="I149" n="319" first="c1" second="c77" awayfrom="I146" shape="circle" which="first">Intersection between c1 and c77</Intersection>
<Circle name="c78" n="322" through="I147" midpoint="I149" acute="true">Circle around I149 through I147</Circle>
<Intersection name="I152" n="323" first="c78" second="c1" awayfrom="I147" shape="circle" which="second">Intersection between c78 and c1</Intersection>
<Circle name="c79" n="326" through="I149" midpoint="I152" acute="true">Circle around I152 through I149</Circle>
<Intersection name="I154" n="327" first="c79" second="c1" awayfrom="I149" shape="circle" which="second">Intersection between c79 and c1</Intersection>
<Circle name="c80" n="330" through="I152" midpoint="I154" acute="true">Circle around I154 through I152</Circle>
<Intersection name="I156" n="331" first="c80" second="c1" awayfrom="I152" shape="circle" which="second">Intersection between c80 and c1</Intersection>
<Circle name="c81" n="334" through="I154" midpoint="I156" acute="true">Circle around I156 through I154</Circle>
<Intersection name="I157" n="335" first="c1" second="c81" awayfrom="I154" shape="circle" which="first">Intersection between c1 and c81</Intersection>
<Circle name="c82" n="338" through="I156" midpoint="I157" acute="true">Circle around I157 through I156</Circle>
<Intersection name="I159" n="339" first="c1" second="c82" awayfrom="I156" shape="circle" which="first">Intersection between c1 and c82</Intersection>
<Circle name="c83" n="342" through="I157" midpoint="I159" acute="true">Circle around I159 through I157</Circle>
<Intersection name="I162" n="343" first="c83" second="c1" awayfrom="I157" shape="circle" which="second">Intersection between c83 and c1</Intersection>
<Circle name="c84" n="346" through="I159" midpoint="I162" acute="true">Circle around I162 through I159</Circle>
<Intersection name="I164" n="347" first="c1" second="c75" awayfrom="I141" shape="circle" which="second">Intersection between c1 and c75</Intersection>
<Circle name="c85" n="350" through="I144" midpoint="I164" acute="true">Circle around I164 through I144</Circle>
<Line name="l1" n="353" from="P4" to="P1">Line through P4 and P1</Line>
<Intersection name="I197" n="422" first="l1" second="c67" shape="circle" which="first">Intersection between l1 and c67</Intersection>
<Circle name="c103" n="425" through="P4" midpoint="I197" acute="true">Circle around I197 through P4</Circle>
<Intersection name="I199" n="426" first="c103" second="c76" awayfrom="P4" shape="circle" which="first">Intersection between c103 and c76</Intersection>
<Circle name="c104" n="429" through="I197" midpoint="I199" acute="true">Circle around I199 through I197</Circle>
<Intersection name="I201" n="432" first="c104" second="c78" shape="circle" which="first">Intersection between c104 and c78</Intersection>
<Circle name="c105" n="435" through="I199" midpoint="I201" acute="true">Circle around I201 through I199</Circle>
<Intersection name="I204" n="436" first="c79" second="c105" shape="circle" which="second">Intersection between c79 and c105</Intersection>
<Circle name="c106" n="439" through="I201" midpoint="I204" acute="true">Circle around I204 through I201</Circle>
<Intersection name="I205" n="440" first="c68" second="c103" awayfrom="P4" shape="circle" which="first">Intersection between c68 and c103</Intersection>
<Circle name="c107" n="443" through="I197" midpoint="I205" acute="true">Circle around I205 through I197</Circle>
<Intersection name="I208" n="444" first="c107" second="c70" shape="circle" which="second">Intersection between c107 and c70</Intersection>
<Circle name="c108" n="447" through="I205" midpoint="I208" acute="true">Circle around I208 through I205</Circle>
<Intersection name="I209" n="451" first="c71" second="c108" shape="circle" which="first">Intersection between c71 and c108</Intersection>
<Circle name="c109" n="454" through="I208" midpoint="I209" acute="true">Circle around I209 through I208</Circle>
<Intersection name="I211" n="455" first="c106" second="c81" shape="circle" which="first">Intersection between c106 and c81</Intersection>
<Circle name="c110" n="458" through="I204" midpoint="I211" acute="true">Circle around I211 through I204</Circle>
<Intersection name="I214" n="459" first="c82" second="c110" shape="circle" which="second">Intersection between c82 and c110</Intersection>
<Circle name="c111" n="462" through="I211" midpoint="I214" acute="true">Circle around I214 through I211</Circle>
<Intersection name="I215" n="463" first="c73" second="c109" shape="circle" which="first">Intersection between c73 and c109</Intersection>
<Circle name="c112" n="466" through="I209" midpoint="I215" acute="true">Circle around I215 through I209</Circle>
<Intersection name="I217" n="467" first="c74" second="c112" shape="circle" which="first">Intersection between c74 and c112</Intersection>
<Circle name="c113" n="470" through="I215" midpoint="I217" acute="true">Circle around I217 through I215</Circle>
<Intersection name="I219" n="471" first="c75" second="c113" shape="circle" which="first">Intersection between c75 and c113</Intersection>
<Circle name="c114" n="474" through="I217" midpoint="I219" acute="true">Circle around I219 through I217</Circle>
<Intersection name="I222" n="475" first="c83" second="c111" shape="circle" which="second">Intersection between c83 and c111</Intersection>
<Circle name="c115" n="478" through="I214" midpoint="I222" acute="true">Circle around I222 through I214</Circle>
<Intersection name="I224" n="479" first="c84" second="c115" shape="circle" which="second">Intersection between c84 and c115</Intersection>
<Circle name="c116" n="482" through="I222" midpoint="I224" acute="true">Circle around I224 through I222</Circle>
<Intersection name="I226" n="483" first="c114" second="c85" shape="circle" which="second">Intersection between c114 and c85</Intersection>
<Circle name="c117" n="486" through="I219" midpoint="I226" acute="true">Circle around I226 through I219</Circle>
<Intersection name="I228" n="487" first="c1" second="c117" shape="circle" which="second">Intersection between c1 and c117</Intersection>
<Circle name="c118" n="490" through="I226" midpoint="I228" acute="true">Circle around I228 through I226</Circle>
<Intersection name="I230" n="491" first="c116" second="c1" shape="circle" which="second">Intersection between c116 and c1</Intersection>
<Circle name="c119" n="494" through="I224" midpoint="I230" acute="true">Circle around I230 through I224</Circle>
<Intersection name="I232" n="495" first="l1" second="c118" shape="circle" which="second">Intersection between l1 and c118</Intersection>
<Circle name="c120" n="498" through="I228" midpoint="I232" acute="true">Circle around I232 through I228</Circle>
<Intersection name="I306" n="646" first="l1" second="c120" shape="circle" which="second">Intersection between l1 and c120</Intersection>
<Circle name="c156" n="649" through="I232" midpoint="I306" acute="true">Circle around I306 through I232</Circle>
<Intersection name="I309" n="654" first="c115" second="c156" shape="circle" which="first">Intersection between c115 and c156</Intersection>
<Circle name="c158" n="657" through="I306" midpoint="I309" acute="true">Circle around I309 through I306</Circle>
<Intersection name="I311" n="658" first="c111" second="c158" shape="circle" which="first">Intersection between c111 and c158</Intersection>
<Circle name="c159" n="661" through="I309" midpoint="I311" acute="true">Circle around I311 through I309</Circle>
<Intersection name="I314" n="662" first="c159" second="c106" shape="circle" which="second">Intersection between c159 and c106</Intersection>
<Circle name="c160" n="665" through="I311" midpoint="I314" acute="true">Circle around I314 through I311</Circle>
<Intersection name="I317" n="670" first="c104" second="c160" shape="circle" which="first">Intersection between c104 and c160</Intersection>
<Circle name="c162" n="673" through="I314" midpoint="I317" acute="true">Circle around I317 through I314</Circle>
<Intersection name="I319" n="674" first="c156" second="c114" shape="circle" which="first">Intersection between c156 and c114</Intersection>
<Circle name="c163" n="677" through="I306" midpoint="I319" acute="true">Circle around I319 through I306</Circle>
<Intersection name="I322" n="678" first="c113" second="c163" shape="circle" which="second">Intersection between c113 and c163</Intersection>
<Circle name="c164" n="681" through="I319" midpoint="I322" acute="true">Circle around I322 through I319</Circle>
<Intersection name="I324" n="682" first="c109" second="c164" shape="circle" which="second">Intersection between c109 and c164</Intersection>
<Circle name="c165" n="685" through="I322" midpoint="I324" acute="true">Circle around I324 through I322</Circle>
<Intersection name="I326" n="686" first="c107" second="c165" shape="circle" which="second">Intersection between c107 and c165</Intersection>
<Circle name="c166" n="689" through="I324" midpoint="I326" acute="true">Circle around I326 through I324</Circle>
<Intersection name="I327" n="690" first="l1" second="c162" shape="circle" which="first">Intersection between l1 and c162</Intersection>
<Circle name="c167" n="693" through="I317" midpoint="I327" acute="true">Circle around I327 through I317</Circle>
<Intersection name="I329" n="694" first="c167" second="c159" shape="circle" which="first">Intersection between c167 and c159</Intersection>
<Circle name="c168" n="697" through="I327" midpoint="I329" acute="true">Circle around I329 through I327</Circle>
<Intersection name="I331" n="698" first="c164" second="c167" shape="circle" which="first">Intersection between c164 and c167</Intersection>
<Circle name="c169" n="701" through="I327" midpoint="I331" acute="true">Circle around I331 through I327</Circle>
</Objects>
</Construction>
</CaR>

[vvvv]

А, так Вы написали программу (алгоритм) и она выдала такое решение! Ну, так бы и сказали, а то молчите!
А Вы проверили - условие минимума расстояния (равно или больше трех) выдерживается для всех точек? На глаз-то не определить
Если это условие соблюдено, то тогда Вы правы.

[venco]

Я пользовался геометрическим редактором C.a.R. (Compass and Ruler).
Если поставите себе, то можете сохранить приведённый код в фаил, загрузить в C.a.R., и исследовать.

[vvvv]

Посмотрел Вашу картинку по-внимательней. На окружности диаметра 21 расстояния между точками равно 3.Но если сравнить длины
отрезков, изображенных красным, визуально, то видно, что меньший отрезок меньше 3-х.Картинку рисовал компьютр - ему нужно верить.
Так что, здесь что-то не то

[venco]

vvvv в сообщении #231922 писал(а):

Посмотрел Вашу картинку по-внимательней. На окружности диаметра 21 расстояния между точками равно 3.

Нет. Из 21 отрезков только 18 равны 3.

-- Ср июл 29, 2009 18:23:58 --

vvvv, там вокруг каждой точки построены окружности одинакового радиуса 1 (я поделил все размеры на 3, большой круг имеет радиус 7).

[vvvv]

venco в сообщении #231924 писал(а):

vvvv в сообщении #231922 писал(а):

Посмотрел Вашу картинку по-внимательней. На окружности диаметра 21 расстояния между точками равно 3.

Нет. Из 21 отрезков только 18 равны 3.

-- Ср июл 29, 2009 18:23:58 --

vvvv, там вокруг каждой точки построены окружности одинакового радиуса 1 (я поделил все размеры на 3, большой круг имеет радиус 7).

-- Чт июл 30, 2009 02:32:57 --

[venco]

vvvv в сообщении #231928 писал(а):

Так делите на сколько угодно.На внешней окружности у Вас отложено 21 точка - это возможно если только расстояния между соседними точками равны!

Нет.

[Профессор Снэйп]

vvvv в сообщении #231922 писал(а):

...если сравнить длины отрезков, изображенных красным, визуально, то видно, что меньший отрезок меньше 3-х.

Чисто визуально меньший из двух красных отрезков --- это, в точности, радиус одной из окружностей, так что его длина равна трём

[vvvv]

Профессор Снэйп в сообщении #231938 писал(а):

vvvv в сообщении #231922 писал(а):

...если сравнить длины отрезков, изображенных красным, визуально, то видно, что меньший отрезок меньше 3-х.

Чисто визуально меньший из двух красных отрезков --- это, в точности, радиус одной из окружностей, так что его длина равна трём

[venco]

Профессор Снэйп в сообщении #231938 писал(а):

vvvv в сообщении #231922 писал(а):

...если сравнить длины отрезков, изображенных красным, визуально, то видно, что меньший отрезок меньше 3-х.

Чисто визуально меньший из двух красных отрезков --- это, в точности, радиус одной из окружностей, так что его длина равна трём

Именно так!

-- Ср июл 29, 2009 20:11:21 --

vvvv в сообщении #231940 писал(а):

21 отрезок длиной 3 на окружности диаметром 21 отложить невозможно т.к. не выполняется условие 21*Sin(pi/21)<=3.

Не-а, возможно. Как раз потому что >3.
vvvv, посчитайте ещё раз, только теперь правильно.