2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 занимательная задачка: составить число из цифр
Сообщение15.11.2005, 12:34 
Вот такая вот задачка:

Даны 9 цифр, 1, 2, 3, 4, 5, 6, 7, 8, 9. Из этих цифр нужно составить число таким образом, что 2 старшие разряда этого числа делятся на 2, 3 старшие - на три, и так далее, вплоть до полного числа.
Найдите такое число, докажите его существование, единственность (если она конечно присутствует).

С комьпьютерным перебором просьба не обращаться.

  
                  
 
 
Сообщение15.11.2005, 12:51 
Основатель
Аватара пользователя


11/05/05
4312
каждая цифра используется только один раз и число, которое нужно составить 9-значное, да?

 Профиль  
                  
 
 так точно
Сообщение15.11.2005, 12:58 
так точно

  
                  
 
 
Сообщение15.11.2005, 14:24 
Я довел перебор до 10 вариантов, вроде.

Пятая цифра - 5, это очевидно.
На четных местах стоят четные цифры, на нечетных - нечетные - тоже понятно.
Так как первые три цифры делятся на три, а 6 - на 6, то сумма первых трех цифр, вторых трех и третьих трех - делятся на 3.

Таким образом, на местах "4" и "6" могут стоять либо 2 и 8, либо 4 и 6.

Ясно, что если число из первых 8 цифр делится на 8, то предпоследняя цифра не делится на 4 - потому, что если бы делилась, то ("6 цифра"*100 + "8 цифра") делится на 4, а "7 цифра"*10 - не делится, т.е. противоречие с признаком делимости на 8.

Итак, предпоследняя цифра - 2 или 6.
Проведя аналогичные рассуждения для 4-й цифры, получаем, что она тоже или 2, или 6

Разберем эти 2 варианта.
1) предпоследняя - 6. Тогда четвертая - 2. Шестая - 8, так как средние три цифры в сумме делятся на 3. Тогда вторая - 4. Имеем _4_258_6_.

7-я цифра - либо 9, либо 1 - так как 7-я с 8-й должны дать двузначное число, делящееся на 8. Разбираем 2 варианта:
1а) _4_25896_. Тогда последняя - 3, так как послендие три - тоже делятся на 3. Имеем да случая расположения 1 и 7, честно проверяем, что ни в одном из этих случаев делимости на 7 не будет.
1б) _4_25816_. Тут все просто - последней цифры не подобрать так, чтобы три последних в сумме делились на 3.

2) Предпоследняя - 2. Тогда, рассуждая аналогично 1, имеем
_8_654_2_. Опять же, из признака делимости на 8 имеем, что 7-я цифра - либо 3, либо 7.

2а) Пусть, 3. Тогда _8_65432_ Последняя цифра - 1 или 7.
Имеем 4 варианта
987654321 :-)
789654321
189654327
981654327
Для всех из них первые 7 цифр не делятся на 7.

2б) Пусть 7. Тогда _8_65472_. Последняя цифра - 3 или 9.
Имеем еще 4 варианта.
189654723 - первые 7 цифр не делятся на 7
981654723 - первые 7 цифр не делятся на 7
183654729 - первые 7 цифр не делятся на 7
381654729 - да!!!

  
                  
 
 УРА!
Сообщение15.11.2005, 14:47 
УРА!

Меня лично более всего впечатлил тот факт, что такое число в десятиричной системе уникально.

А как в других системах счисления?

  
                  
 
 
Сообщение15.11.2005, 15:05 
Хе-хе.

Всегда приятно вспомнить время, когда был не бывшим, а самым чтонинаесть настоящим вундеркиндом. Иными словами, вспомнить свое физматшкольное детство. :)

Итак, разбираемся.

Здесь и далее, когда говорится о том, что цифры или "группа цифр" делится на ... подразумевается, что делится число, составленное из этих цифр.

Сначала об очевидном: Четные цифры стоят на четных местах, нечетные - на нечетных, причем цифра 5 - на 5-м месте. Кроме того, группы цифр с 1 по 3, с 4 по 6, с 7 по 9 должны делиться на 3, группа цифр с 3 по 4 - на 4, а с 6 по 8 - на 8.

Для вас это не очевидно? Учите признаки делимости. Что, и теперь?! Тогда к дохтуру. Ну или капелек каких попейте.

Так как 6-я цифра - четная, то последнее требование облегчается: гцыфры 7-8 должны делиться на 4. Выписываем все такие пары, состоящие из нечетной+четной цифры:

16, 32, 56, 72, 96.

56, ясен пень, не годится, т.к. пятерка уже занята. 16 не годится по той же причине, так как за ней может следовать (из нечетных цифр) только пятерка - ведь нужно, чтобы эти три цифры делились на 3. Остается 32, 72, 96. Дополняем их до тройки нечетной цифрой, чтобы вся тройка делилась на 3. Получаем следующие варианты для последней триады цифр:

321, 327, 723, 729, 963.

Другие варианты невозможны. Теперь займемся второй триадой. Там пятерка обрамлена двумя четными цифрами. Чтобы вся триада делилась на 3, возможны только пары 8 и 2, или 4 и 6. Но цифры с 3 по 4 должны делиться на 4, а треться цифра - нечетная. Следовательно, четвертая цифра - четная, но не кратная 4 - 6 или 2. Таким образом, вторая триада выглядит следующим образом:

654 или 258.

Очевидно, что к каждой "третьей триаде" (из перечисленных) можно подобрать однозначно одну вторую триаду - ту, в которой нет задействованной в третьей триаде четной цифры.

Ну а с первой триадой все очевидно. В центре - оставшаяся "свободной" четная цифра, а по краям - две нечетные. Таким образом, получаем множество чисел, удовлетворяющих всем требованиям, кроме делимости на 7:

789654321 и 987654321,
189654327 и 981654327,
189654723 и 981654723,
183654729 и 381654729,
147258963 и 741258963.

Проверяем все числа на оставшееся требование и убеждаемся, что ему ужовлетворяет только число 381654729.

Задача решена.

  
                  
 
 
Сообщение15.11.2005, 15:06 


03/10/05
13
Ну... В других системах счисления Вы хорошо знаете признаки делимости? Я и в этой-то признак делимости на 7 так и не вспомнил... Может, удалось бы сократить док-во.

 Профиль  
                  
 
 признаки делимости
Сообщение15.11.2005, 15:37 
про признаки делимости

Я полагаю, что можно самому выводить признаки делимости в N-ричной системе счисления.

Например посмотрев на последовательности k*n, n=1...N можно увидеть структуру и характерные свойства операции деления на k.

Для примера, (по предверительным прикидкам) в нечётно-ричной системе счисления признаком деления на 2 будет чётность суммы цифр числа.

  
                  
 
 
Сообщение16.11.2005, 09:16 
Во сне вспомнилось/придумалось:

Что касается признаков делимости для чисел, записанных по произвольному основанию q, то они практически те же самые что и для частного случая q=10. Таких "элементарных" признаков всего 3: для чисел, делящих q^n, q-1 и q+1.

1. Если число k делит q^n, то k делит заданное число тогда и только тогда, когда оно делит "n последних цифр" этого числа (т.е. остаток от деления заданного числа на q^n).

2. Если число k делит q-1, то оно делит заданное число тогда и только тогда, когда оно делит сумму цифр заданного числа.

3. Если число k делит q+1, то оно делит заданное число тогда и только тогда, когда оно делит разность сумм цифр заданного числа, стоящих на четных и нечетных местах.

Остальные признаки более сложны, - как, например, признаки делимости десятичных чисел на 7 и 13, опирающиеся на факт, что 1001=7*11*13. В принципе, аналогичные признаки для чисел, записанных по произвольному основанию можно вывести, разложив число 10...1 на множители. При решениии задачи этого обсуждения данные признаки использовать неудобно.

Что же касается исходной задачи в общей формулировке, то для нее есть ряд очевидных фактов:

- для нечетных оснований q подобных чисел не существует (доказательство тривиальное);
- для четных оснований q выполняются следующие условия:
-- четные цифры стоят на четных местах, нечетные - на нечетных;
-- "в середине числа", т.е. на позиции q/2 всегда стоит цифра q/2.

Больше [очевидных] общих закономерностей пока не просматривается. Что касается существования и единственности решения для четных оснований, то тут, похоже, "дело случая". Например:
q=4: 123, 321
q=6: 14325, 54321
q=8: 3254167, 5234761, 5674321

Кстати, задача к размышлению на 3-5 минут: доказать, что для q=12 решения не существует.

Пока всё.

  
                  
 
 
Сообщение17.11.2005, 09:54 
>> "Кстати, задача к размышлению на 3-5 минут: доказать, что для q=12 решения не существует. "

Не совсем улавливаю Вашу мысль. Поясните, пожалуйста.

  
                  
 
 
Сообщение17.11.2005, 13:45 
дворникУ:

Доказать, что не существует [очевидно, конечной] последовательности 11 различных 12-ричных цифр (от 1 до "11"), такой, что число, записанное первыми n цифрами последовательности делится на n для всех целых n: 1<n<12. Ну то есть что задача, аналогичная исходной задаче, но сформулированная в 12-ричной системе счисления, неразрешима.

Пытался проверить для 14 и 16, но заленился. Может, когда-нибудь потом.

  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group