Дискретная математика и формальные системы. Раздел : позиционные системы счисления

№1523 

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ СТАЛИ И СПЛАВОВ 
(ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ) 

Кафедра автоматизированных систем управления 

Прокопчук Ю.Ю., Широков А.И. 

Одобрено Методическим 
советом института 

Дискретная математика 
и формальные системы 

Раздел: Позиционные системы счисления 

Методические указания 

для студентов специальностей 002202,000718 

Москва 1999 

АННОТАЦИЯ 

В пособии приведен разбор решений задач из контрольных 
работ по теме "Позиционные системы счисления". Перечень формулировок задач приведен в [ 6 | С методами решения задач студенты 
знакомятся на аудиторных занятиях и при чтении учебной и справочной литературы, список которой указан в конце пособия. 

Библиография: 6 названий. 

© Московский 
государственный 
институт 
стали 
и 
сплавов 
(МИСиС), 1999. 

Прокопчук Ю Ю , Широков А.Л. 

РАЗБОР РЕШЕНИЙ ЗАДАЧ ИЗ ВАРИАНТОВ 
КОНТРОЛЬНЫХ РАБОТ 

Вариант 1 

Задача I. Найти двузначное 10-е число, равное сумме квадрата 
числа своих единиц и числа десятков 

ОТВЕТ 89. 

Решение 

Пусть искомое число имеет вид 10у -*- х, где х, у ъ N, 0 5 x 5 9 
н 0 < у 5 9. Из .условия имеем: \0у + х ** у + х2, откуда получаем: 
9у 
ж (х - 
1)х. Отсюда 
х - 
1 или х кратно 9, Так как 
х- 1 5 8, то х = 9 Отсюда 9у = 9 • 8, то есть у - 8. Искомое число есть 
89. 

Задача 2 Выявите и сформулируйте признаки делимости на 
числа вида 2", п е N, в двоичной системе счисления. 

Указание Сформулируйте признаки делимости на 2, 4, 8, 16 в 
двоичной системе счисления и обобщите полученные результаты. 

ОТВЕТ для того, чтобы представленное в двоичной системе 
счисления число делилось на число вида 2", необходимо и достаточно, чтобы оно оканчивалось по меньшей мере п нулями. 

Вариант 2 

Задача 1. Докажите, что для любого положительного нату 
рального числа х существует такое натуральное у, что число 
ху + 1 - составное. 

Решение 

а) При х = 1 и у =* 3 число 1 • 3 + 1 «= 4 - составное. 
б) Пусть х £ 2. Положив у х 2 , получаем: ху + 1 « г3 + 1 * 
« (х + 1Хх2 - х + 1) - составное число, так как (х т 1) 2: 3, а 

3 

Методические указания 
fix) = х2 - х + 1 - возрастающая натуральная функция, наименьшее 
значение которой на полуинтервале (2;<х>) есть ее значение при х « 2. 
НоД2) = 2 2 - 2 + 1 в 3 2 : 3 . Таким образом, при х И 2 число ху может 
быть представлено в виде произведения сомножителей, каждый из 
которых не меньше, чем 3. Значит, оно составное. 

Задача 2. Выявите и сформулируйте признаки делимости на 2, 
3, 4, 6, 12 в двенадцатиричной системе счисления 

ОТВЕТ: для того чтобы число, представленное в двенадцати* 
ричной системе счисления, делилось на 2, 3, 4, 6 и (12)ю, необходимо 
и достаточно, чтобы число, изображаемое его последней (крайней 
правой) цифрой, делилось на 2, 3,4, 6 и (12)ю соответственно. 

Вариант 3 

Задача 1. На доске сохранилась полустертая запись: 

2 
3 - 5 
+ 

1 - 6 4 2 

4 2 4 2 3 
Выявить: а) хотя бы одну систему счисления, в которой произведено сложение; б) определить стертые цифры. 

ОТВЕТ: а) сложение произведено в 7-й системе счисления; 
б) стертые цифры в верхней строке - 4 и 1, а в нижней - 5. 

Решение 
Обозначив пропущенные цифры буквами, имеем: 

2 3 х 5 у 
+ 

1 г б 4 2 
(I) 

4 2 4 2 3 

1)Из крайнего правого столбца имеем: а) у + 2 = 3 или 
б) у + 2 - ОСН + 3, где буквосочетание ОСН обозначает основание 

4 

^ 
Прокопчук Ю Ю., Широков А.А. 

интересующей нас системы счисления. Из а) получаем: у ж 1, а из 
б) - у = ОСН + 1. Так как наибольшая из цифр системы счисления 
изображает число, на единицу меньшее, чем основание, последнее 
равенство неверно. Значит,^ = 1. 

2) Из второго справа столбца получаем: а)5 + 4 = 2 или 
6)5 + 4 ** ОСН + 2 Так как из неравенств 5 > 2 и 4 > 2 следует, что 
5 + 4 > 2, то а) неверно Значит, верно б), откуда получаем, что 
ОСН - 7. Это не противоречит результату, полученному в п.1). 

3) Из третьего справа столбца получаем: а) 1 + х + 6 • 4, т.е. 
х = - 3, что неверно, либо б) 5 + х + 6 « ОСН + 4, т.е. х + 7 = 7 + 4, или 
х*= 4. 

4) Из четвертого справа столбца получаем: а)1 + 3 + г ж 2, т.е. 
г » - 2, что неверно, либо б) 1 + 3 + г - ОСН + 2, т.е. 4 + г = 7 + 2, откуда г = 5. Для проверки правильности решения подставим найденные значения х, у и г в (I): 

2 3 4 5 
1 , 

1 5 6 4 2 , 

4 2 4 2 3 7 
Результат сложения верен. 

Задача 2. Выявите и сформулируйте признак делимости на 8 в 
двенадцатиричной системе счисления. 

ОТВЕТ: для того чтобы число, представленное в двенадцатиричной системе счисления, делилось на 8, необходимо и достаточно, 
чтобы число, изображаемое его двумя последними (правыми) цифрами, делилось на 8. 

Вариант 4 

Задача 1. Натуральное число р есть квадрат какого - то натурального числа, а запись р в 10-й системе счисления оканчивается на 
5. Докажите, что третья справа цифра записи р - четная (то есть является одной из следующих цифр: 0,2,4,6, 8). 

5 

Методические ука-юиия 

Решение 
Поскольку запись р оканчивается на 5, то р ** (10? + 5)2, где 
q - натуральное число. Имеем (10? + 5)2 т 100? + \00q2 + 25 • 
= I00q(q + 1) + 25. Легко понять, что третья справа цифра числа/» 
равна первой справа цифре числа q{q + I) Так как q - натуральное, то 
одно из чисел q,q+ \ - четное, и поэтому q(q + 1) - четное число. 

Задача 2- Выявите и сформулируйте признак делимости на 9 в 
двенадцатиричной системе счисления 

ОТВЕТ: дл» того чтобы число, представленное в двенадцатиричной системе счисления, делилось на 9, необходимо и достаточно, 
чтобы число, изображаемое его дв\ мя последними (правыми) цифрами, делилось на 9. 

Вариант 5 

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

ОТВЕТ: 8281. 

Решение 

По условию искомое число имеет вид: 

/>=1000х+1000>+1)+10х+,у = г \ 
(I) 

где х и у - числа, изображаемые цифрами, стоящими на 1-м и 4-м 
местах (слева направо) при записи р в 10-й системе счисления, а 
z - некоторое натуральное число. Из (I) имеем: 

101(10*+.y)-zI- 100*(* + 10)(z- 10). 
Так как 101-простое число, то z + 10 или г - 10 кратно 101. Но 
2 < 100, так как квадратный корень из четырехзначного числа - число 
двузначное. Значит, г + 10 » 101*, где к - натуральное. При к ж 0 имеем: z * - 10, z1 ж 100, но 100 - трехзначное число. При к - 1 имеем: 
г ш 91 и р « 8281. При к » 2 имеем: z ** 192, но 192 - пятизначное 
число. Значит, задача имеет единственное решение. 

6 

Прокопчу* Ю Ю. Широко» АА. 

Задача 2 Переведите число (2Ц02)п в 10-ю систему, счисления, используя схему Горнера. 
ОТВЕТ: 43490. 

Вариант б 

Задача \. Один школьный учитель на каш вопрос: "Много пну 
него учеников?" ответил. "У меня в классе 100 детей, из них 24 мальчика и 32 девочки". Скачала нас удивил его ответ, но потом мы поняли, что просто учитель пользовался не десятичной системой счисления. Требуется определить: а) Какую систему счисления имел ввиду 
учитель? б) Сколько девочек и мальчиков было в классе, если для 
представления интересующих нас чисел использовать десятичную 
систему счисления? 

ОТВЕТ: а) шестиричную; б) в классе 36ю учеников, из них 
16,о мальчиков и 20ю девочек. 

Решение 

Пусть х - основание системы счисления. Тогда слова учителя 
означают следующее: у него х* учеников, из них 2х + 4 мальчиков я 
Зх + 2 девочек. Таким образом, 2х + 4 + Зх + 2 " х \ или х2 - 5х - 6 « 0, 
откуда 

„ 
J25 + 2 4 _ S ± 7 
*»- 
2 
Г' 

то есть х, = 6, х 2 « - 1. 

Корень х, не удовлетворяет условиям задачи, так как число 
девочек, равное Зх + 2, при х * - 1 оказывается равным - 1, что бессмысленно. Значит, х = б|0 Таким образом, в классе 36|0 учеников, из 
них 16|0 мальчиков и 20)0 девочек. 

?TVW*a 2, Переведите число (24713), в 10-ю систему счисления, используя схему Горнера. 
ОТВЕТ: 10699. 

7 

Методические .указания 

Вариант 7 

Задача 1. Пусть натуральное число р - точный квадрат некоторого натурального числа. Швестно, что в 10-й системе счисления 
р - четырехзначное, причем число тысяч р равно числу его сотен, а 
число десятков - числу единиц Найти р. 
ОТВЕТ: р « 7744 « 882. 

Решение 
По условию 

/)= Ю00х + Ю0х + Wy + y™ II(I00x+j>), 
(I) 

где 

О < х £ 9, 
(II) 

О £ у й 9. 
(Ш) 

Так как/? - точный квадрат, то число ЮОх +у делится на 11, и, 
значит, число х + у = (100х + _у) - 99х также делится на 11 как разность 
двух чисел, делящихся на 11. В силу (II) и (Ш) имеем; 0 < х + у £ 18. 
Поэтому 

х+у^11. 
(IV) 

Отсюда: ЮОх +у « 99х + (х + ,у) = 99х + И = 11(9х + 1). Из (I) 
имеем: р «= Пх11х(9х + 1) * 113х(9х + 1). По условию задачи число 
9х + 1 - точный квадрат. Пусть 

9х+1=? 2, 
(V) 

Покажем, что 
q й 9, 
(VI) 

В самом деле, если q 2 10, то 

/ > « И 2 . ? 2 2 П 2 . 1 0 2 * П 0 2 » №12100, 
что противоречит тому, что р - четырехзначное число. Если q £ 9, то 
р - П3-*?*, U2- 92 = 992«99*1, что соответствует условию. 
Из (V) получаем: 

х » (д2 - 1)/9 - (9 + 1К9 - ! V9- 
(У11) 

Числа q + 1 н q - 1 разнятся друг от друга на 2, и поэтому оба 
не могут делиться на 3. Значит, на 3, а в силу (VII) и на 9 делится. 

8 

Ирокопчук to Ю. Широков А А. 

только одно из них. Но в соответствии с (VI) получаем, что q + 1 £ 10 
и q - I £ 8, то есть на 9 может делиться только q + 1. Таким образом, 
q £ 9 и q + 1 делится на 9. Отсюда выводим, что q = 8 Из (VII) имеем: 
х * 7. а из (IV) - у * 4. Таким образом, />« 7744 * 11282 »(11 -8)2 - 882. 

Задача 2. Переведите число 
(21202), в 
10-ю систему 
счисления, ИСПОЛЬЗУЯ схему Горнсра. 
ОТВЕТ: 209. 

Вариант 8 

Задача 1. Пусть p%q иг - три натуральных числа, записи которых в 10 - й системе счисления представляют собой: р - 2т единиц, 
q - т + 1 единиц, а г - /и циф/; 6. Докажите, что число р + q + г + 8 
есть точный квадрат. 

Решение 

Из условия имеем 

р= 
1 1 . . . 1 « 102m~ ' + 1 0 2 w ~ 2 + ...+ 1 0 + l « ( 1 0 2 m - l ) / 9 ; 

(2т единиц) 
(сумма ?еом.прогресии) 

q* 
1 1 . . . 1 
= 10"+10"-' + ...+ Ю + 1 - (10" + ,-iy9; 

v 
v 
-> v 
„ 
/ 

(m + 1 единиц) (сумма геом.прогресин) 

г= 6. .. 6 
=6x10"*' 
+6хЮ""2 +... + 6x10 + 6 * 

(т цифр 6) 

«б-ОСГ* 1* 10—, + .., + 10+ 1)«[6-(10V 1)]/9. 

Отсюда 

р + 9 + г+8 = ( 1 0 2 т - 1 + 1 0 ' " + , - 1 + 6 . 1 0 " - 6 + 72У9^ 

+ 64J/9 = (102/W 

= l(10"* + 8)/3]J. 

[102m + 10" • (10 + 6) + 64J/9 - (Ю2™ + 2 • 8 • 1(Г + 64)/9 

9 

Методические укгшния 
Так как при любом т е N число 10" + 8 делите* на 3 ("сумма" его 
цифр равна 9), тор + q + г + Ъ- точный квадрат. 

Задача 2, Переведите число (12562)t в десятичную систему 
счисления, ИСПОЛЬЗУЯ схему Гориера 
ОТВЕТ: 5490. 

Вариант 9 

Задача 1 Если основание системы счисления - простое число, 
а число papa, умноженное на число арра, равно араара, то чему равно 
число papa"} 

ОТВЕТ, в 2 - й системе счисления: а)р ж 0, а = 1; 
б) а = р = 0; в) варианты а = 0, /> = I ив=/)= 1 неверны В троичной 
системе счисления нужно проверить 9 вариантов, в пятеричной - 25 
вариантов. 

Задача 2, Переведите число (2 1 03)12 в десятичную систему 
счисления, использ\я схему Горнсра. 
ОТВЕТ. 5163. 

Вариант 10 

Задача 1. Доказать, что любое четное число, не кратное четырем, нельзя Представить в виде разности квадратов двух целых чисел. 

Решение 
Предположим, что число 2к, где к - нечетное число, равно 
m — п , то есть 

2к~(т + п)(т-п). 
(I) 

Из тождества т + п-(т-п) 
+ 2п следует одинаковая четность чисел 
т и п (то есть либо оба они четные, либо - оба нечетные). Следовательно, в правой части равенства (I) стоит или четное число, кратное 
четырем, или нечетное число. Поскольку левая часть равенства 

10