Задачка от Google

и задачки для интервью.
Forum rules
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Layla wrote:Я, должно быть, пропустила какие-то пояснения по условию задачи?

Как ни странно, исходная формулировка не допускает других трактовок. Разве что надо бы добавить слово "все", хота оно там и подразумевается:
Длины всех хорд - натуральные числа.

Где-то было ограничение, что все хорды - разные?

Такого ограничения нет.

Могут ли все хорды быть диаметрами (проходить через центр и иметь, соответственно, одинаковую длину, skazhem - 1)?

Все хорды быть диаметрами могут только если количество точек <= 2.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

olg2002 wrote:Я думаю, что могу доказать, что 12.5 - минимальный радиус.

Я думаю, 12.5 - минимум, только если среди хорд есть диаметр.
Если же нет - число вариантов сильно увеличивается.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Re: Задачка от Google

Post by venco »

serg14 wrote:Проводили рекрутинг на кампусе. Одна задачка показалась мне интересной ...

А кстати, дают компьютер для поиска ответа?
Если да, то такая задача вполне имеет смысл, т.к. у меня создалось ощущение, что минимальное решение, если оно меньше 12.5, найти можно только перебором.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Нашёл кучу решений < 12.5.
Минимальное - 7/sqrt(3) ~= 4.04.
Top
vaduz
Уже с Приветом
Posts: 27652
Joined: 15 Jul 2002 17:05
Location: MD

Post by vaduz »

varenuha wrote:
serg14 wrote:мой ответ меньше 12.5, но больше 2.5

посему на 2.5 моя реакция тоже будет: "Ну-ка ну-ка?"


Два прямоугольных треугольника со сторонами 3,4,5 вписанные в окружность дадут требуемый шестиугольник.


Не дадут.
Top
User avatar
Kotiara
Уже с Приветом
Posts: 2245
Joined: 24 Feb 2006 21:27
Location: London

Post by Kotiara »

У меня получилось 1.
Top
vaduz
Уже с Приветом
Posts: 27652
Joined: 15 Jul 2002 17:05
Location: MD

Post by vaduz »

Kotiara wrote:У меня получилось 1.


Неправильно. Все 6 точек попарно соеденены.
Top
User avatar
Kotiara
Уже с Приветом
Posts: 2245
Joined: 24 Feb 2006 21:27
Location: London

Post by Kotiara »

vaduz wrote:
Kotiara wrote:У меня получилось 1.


Неправильно. Все 6 точек попарно соеденены.


Я, видать, русский языг забыл. Может быть, объясните что значит попарно? А то в моем понимании возникло 6 равносторонних треугольников со стороной = 1 см., вписанных в круг в виде шестиугольника.
Top
User avatar
olg2002
Уже с Приветом
Posts: 990
Joined: 27 Mar 2002 10:01
Location: Palo Alto, CA

Post by olg2002 »

venco wrote:
olg2002 wrote:Я думаю, что могу доказать, что 12.5 - минимальный радиус.

Я думаю, 12.5 - минимум, только если среди хорд есть диаметр.
Если же нет - число вариантов сильно увеличивается.


Да, действительно, в моем доказательстве неявно полагается, что радиус - рациональное число.
Top
vaduz
Уже с Приветом
Posts: 27652
Joined: 15 Jul 2002 17:05
Location: MD

Post by vaduz »

Kotiara wrote:
vaduz wrote:
Kotiara wrote:У меня получилось 1.


Неправильно. Все 6 точек попарно соеденены.


Я, видать, русский языг забыл. Может быть, объясните что значит попарно? А то в моем понимании возникло 6 равносторонних треугольников со стороной = 1 см., вписанных в круг в виде шестиугольника.


Нет. Нарисуйте окружность, поставьте 6 точек, выберите одну точку, проведите от нее 5 отрезков к другим точкам. Возьмите следующую точку, проведите 4 отрезка к точкам, с которыми она еще не соеденена, ну и т.д.
Итого, из каждой точки выходит 5 отрезков, которые должны иметь длины, выраженные в натуральных числах.
Top
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Post by Ворона »

Kotiara, я тоже не поняла, что значит "попарно" сначала.. Это ВСЕ возможные хорды проведены между всеми точками.
venco, ну показывайте Ваше решение, я сдаюсь - слишком громоздко, много синусов сумм углов и корней :mrgreen: (я стала рассматривать случай, когда вообще никакой симметрии нет), даже Excel не спас.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Ворона wrote:Kotiara, я тоже не поняла, что значит "попарно" сначала.. Это ВСЕ возможные хорды проведены между всеми точками.
venco, ну показывайте Ваше решение, я сдаюсь - слишком громоздко, много синусов сумм углов и корней :mrgreen: (я стала рассматривать случай, когда вообще никакой симметрии нет), даже Excel не спас.

В моём случае симметрия есть. :)
Top
serg14
Новичок
Posts: 23
Joined: 23 Aug 2004 11:28
Location: NY

Post by serg14 »

venco wrote:Минимальное - 7/sqrt(3) ~= 4.04.


:appl03:

Я нашел это решение с помощью циркуля и линейки. А вообще, можно было пользоваться чем угодно.
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

serg14 wrote:Я нашел это решение с помощью циркуля и линейки. А вообще, можно было пользоваться чем угодно.

Я написал программку перебора. Без него гарантировать, что какое либо решение - минимально, мне кажется, нельзя.
Top
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Post by Ворона »

И хорды, кажется, будут 3,5,7,8? Я вчера начала рассматривать случай, когда сумма соседних углов равна 120, и не нашла натуральных решений, а они, оказывается, все-таки там есть. :D
Решившим быстрее всех :love:
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Ворона wrote:И хорды, кажется, будут 3,5,7,8?

Правильно.
А я теперь могу легко найти решение для другого количества точек. :)
Top
User avatar
Layla
Уже с Приветом
Posts: 5813
Joined: 24 Aug 2003 07:17
Location: Seattle

Post by Layla »

Kotiara wrote:
vaduz wrote:
Kotiara wrote:У меня получилось 1.


Неправильно. Все 6 точек попарно соеденены.


Я, видать, русский языг забыл. Может быть, объясните что значит попарно? А то в моем понимании возникло 6 равносторонних треугольников со стороной = 1 см., вписанных в круг в виде шестиугольника.


Да, всё упирается в то, что значит - попарно. Шесть точек, три хорды - это попарно? Шесть точек, шесть хорд - это попарно? Как звучит задача по английски?
Top
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Post by Ворона »

venco wrote:А я теперь могу легко найти решение для другого количества точек

Ну, для 2-х , 3-х и 4-х я тоже могу :mrgreen:
То есть, Ваша программка универсальна для любого количества точек? Хоть 117? 8O
Top
serg14
Новичок
Posts: 23
Joined: 23 Aug 2004 11:28
Location: NY

Post by serg14 »

venco wrote:Я написал программку перебора. Без него гарантировать, что какое либо решение - минимально, мне кажется, нельзя.


тут я наверное соглашусь
но Евклид с Пифагором закидали бы помидорами :-)

Layla wrote:Да, всё упирается в то, что значит - попарно.

"попарно" означает, что каждая из шести точек соединена с пятью другими
Top
User avatar
Layla
Уже с Приветом
Posts: 5813
Joined: 24 Aug 2003 07:17
Location: Seattle

Post by Layla »

serg14 wrote:
venco wrote:Я написал программку перебора. Без него гарантировать, что какое либо решение - минимально, мне кажется, нельзя.


тут я наверное соглашусь
но Евклид с Пифагором закидали бы помидорами :-)

Layla wrote:Да, всё упирается в то, что значит - попарно.

"попарно" означает, что каждая из шести точек соединена с пятью другими


А-а...Спасибо. Я думала, попарно - это иное ;-) А как по английски это звучит условие?
Top
serg14
Новичок
Posts: 23
Joined: 23 Aug 2004 11:28
Location: NY

Post by serg14 »

Layla wrote:А-а...Спасибо. Я думала, попарно - это иное ;-) А как по английски это звучит условие?


I can't tell you, since the answer will become googleable :-)
Top
User avatar
venco
Уже с Приветом
Posts: 2001
Joined: 10 Nov 2004 00:34
Location: MD

Post by venco »

Ворона wrote:Ну, для 2-х , 3-х и 4-х я тоже могу

А для 4-х что получилось? (подсказка - это не 2.5)
То есть, Ваша программка универсальна для любого количества точек? Хоть 117?

Ну я не настолько её оптимизировал. Сейчас 18 точек считает меньше минуты. Дальше время растёт по экспоненте. :)
Top
User avatar
Ворона
Уже с Приветом
Posts: 1849
Joined: 06 Mar 2006 20:06

Post by Ворона »

venco wrote:А для 4-х что получилось? (подсказка - это не 2.5)

Уппс :oops: Я именно так и подумала..
Top
User avatar
Layla
Уже с Приветом
Posts: 5813
Joined: 24 Aug 2003 07:17
Location: Seattle

Post by Layla »

serg14 wrote:
Layla wrote:А-а...Спасибо. Я думала, попарно - это иное ;-) А как по английски это звучит условие?


I can't tell you, since the answer will become googleable :-)


резонно :D
Top

Return to “Головоломки”