Дети, математика и R

в 18:12, , рубрики: data science, R, Алгоритмы, математика

Нынешнее образование в школе все более и более редуцируется. А в оставшейся части акцент все более и более ставится на внешний эффект. «Проектная работа», презентации, вау-эффекты и пр. мишура. Причем зачастую непонятно, кому раздают все эти упражнения — ребенку или родителям? Следствием всего этого является необходимость дополнительных занятий в различных кружках, в рамках школы или же альтернативно, если есть цель дать ребенку полноценное образование.

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

Сразу отмечу, что тема будет интересна далеко не всем. Кому это неактуально — проходите мимо. У кого будут доп. идеи, было бы интересно тоже ознакомиться. Далее будет ряд задачек, которые были позаимствованы с курсов «Меташколы», математика 3-ий класс. Естественно, что сначала задача решается логическими рассуждениями, потом обсуждается способ решения с применением компьютера. В качестве инструмента использовался R.

Является продолжением предыдущих публикаций.

Общая преамбула

library(tidyverse)
library(glue)
library(magrittr)
library(lubridate)
library(hms)
library(numbers)
library(polynom)
library(Ryacas)
library(stringi)
library(tictoc)

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

Восстановите запись

Задача

Восстановите запись: 3∗∗:∗3=3∗. Найдите сумму всех пропущенных цифр.

Пример решения

# Преобразуем 3ab = c3*3d

df <- 0:9 %>% 
  {tidyr::crossing(a = ., b = ., c = ., d = .)} %>%
  filter(300 + a * 10 + b == (c * 10 + 3) * (30 + d))
df

Задача

Можно ли расставить знаки арифметических действий вместо “∗” в записи 7∗(7∗7∗7)∗7, чтобы получить 8?

Пример решения

ops <- c('*', '/', '+', '-')
# соберем все возможные комбинации операндов
df <- tidyr::crossing(op1 = ops, op2 = ops, op3 = ops, op4 = ops) %>%
  # теперь сформируем команды для каждой комбинации переменных
  mutate(data = glue::glue("7 {op1} (7 {op2} 7 {op3} 7) {op4} 7"),
         expr = rlang::parse_exprs(data)) %>%
  mutate(res = purrr::map_dbl(expr, rlang::eval_bare)) %>%
  arrange(res) %>%
  filter(res == 8)
print(tbl_df(df), n = 20)

Задача

Подряд выписаны все числа от 1 до 100. Сколько раз в записи встречается цифра 4?

Пример решения

# в 100 нет цифры 4, поэтому редуцируем верхнюю грань до 99
# нумерация слева направо
tidyr::crossing(d1 = 0:9, d2 = 0:9) %>%
  # оставим только значения, где есть 4
  filter(d1 == 4 | d2 == 4) %>%
  arrange(d1, d2)

Задача

Цифру 9, с которой начиналось трёхзначное число, перенесли в конец числа. Получилось число, которое на 216 меньше. Назовите сумму цифр первоначального числа.

Пример решения

# нумерация слева направо: abc
df <- tidyr::crossing(b = 0:9, c = 0:9) %>%
  # считаем разницу если 9 слева и девять справа 
  mutate(delta = (900 + 10*b + c) - (100*b + 10*c + 9)) %>%
  filter(between(delta, 200, 230))
df

Задача

Произведение 5 последовательных натуральных чисел равно 2520. Назовите меньшее число.

Пример решения, способ 1

numbers::primeFactors(2520)

Пример решения, способ 2

# https://joftius.wordpress.com/2015/10/19/finding-multiple-roots-of-univariate-functions-in-r/
f <- function(x) {x * (x+1) * (x+2) * (x+3) * (x+4) - 2520}
rootSolve::uniroot.all(f, c(0, 2520))

Пример решения, способ 3

eq <- "x * (x+1) * (x+2) * (x+3) * (x+4) - 2520"
yacas(glue("Simplify({eq})"))

# руками зададим коэффициенты  на основании упрощенного полинома и найдем все корни
rts <- base::polyroot(c(-2520, 24, 50, 35, 10, 1)) # от нулевой степени к n-1
# оставим только реальные корни
# http://www.johnmyleswhite.com/notebook/2009/12/18/using-complex-numbers-in-r/
Re(rts[abs(Im(rts)) < 1^-10])

Задача

Какую цифру можно поставить вместо "∗", чтобы число 543∗ делилось на 4? Назовите все возможные варианты.

Пример решения

tibble(num = 5430 + 0:9, mod = mod(num, 4)) %>%
  arrange(mod, num)

Задача

Чему равна удвоенная треть четверти числа 60?

Пример решения

2*(1/3*(1/4*60))
60 %>% {./4} %>% {./3} %>% {.*2}

Задача

Циферблат часов без стрелок разделите на 2 части так что бы сумма чисел имеющиеся на каждом участке была одна и та же.
Доп. вопрос: на какое количество частей можно ещё разделить циферблат часов так, чтобы в каждой части находились числа сумма которых была бы равна между собой?

Пример решения

# поскольку речь идет о разбиении на 2 равные части, достаточно проанализировать 
# только половину пробега стрелки, вторая половина будет = остатку
sum(1:12) / 2

# вариант разбивки часов
for (i in 1:12){
  res <- cumsum(i:12)
  print(glue("Стартовая точка: {i}, накопительные суммы: {glue_collapse(res, ', ')}"))
  val <- which(res == 39)
  if(! identical(val, integer(0))){
    print(glue("Найден диапазон [{i}; {val + i - 1}]"))
  }
}

«Быки и коровы»

Вариация 1

В записи числа различные цифры от 1 до 5 включительно.
Число отгаданных цифр, стоящих на своих местах — это число быков. Число отгаданных цифр, стоящих не на своих местах — это число коров.

Назовите трёхзначное число, если известно:

  • 314 — 1 бык и 1 корова;
  • 124 — 1 бык и 1 корова;
  • 523 — 1 бык и 1 корова.

Пример решения

library(tidyverse)
library(stringi)
# число вида "an_bn_cn". c -- неоднозначность с функцией

df <- c(1, 2, 3, 4, 5) %>%
  {tidyr::crossing(an = ., bn = ., cn = .)} %>%
  # отдельно сформируем комбинации
  mutate(comb = purrr::pmap(., c)) %>%
  # оставляем только подходящие сочетания
  mutate(val = stri_join(an, bn, cn)) %>%
  # учитываем допустимую позиционную раскладку быков
  # 314 - есть 1 бык
  filter(stri_detect_regex(val, "3[^1][^4]|[^3]1[^4]|[^3][^1]4")) %>%
  # 124 - есть 1 бык
  filter(stri_detect_regex(val, "1[^2][^4]|[^1]2[^4]|[^1][^2]4")) %>%
  # 523 - есть 1 бык
  filter(stri_detect_regex(val, "5[^2][^3]|[^5]2[^3]|[^5][^2]3")) %>%
  # исключим сочетания с совпадающими цифрами
  filter(purrr::map_int(comb, n_distinct) == 3) %>%
  # учитываем наличие только двух чисел (1 бык и 1 корова)
  filter(purrr::map(comb, ~length(base::intersect(.x, c(3, 1, 4)))) == 2) %>%
  filter(purrr::map(comb, ~length(base::intersect(.x, c(1, 2, 4)))) == 2) %>%
  filter(purrr::map(comb, ~length(base::intersect(.x, c(5, 2, 3)))) == 2) 

df

Вариация 2

В записи числа различные цифры от 1 до 5 включительно.
Число отгаданных цифр, стоящих на своих местах — это число быков.
Число отгаданных цифр, стоящих не на своих местах — это число коров.
Назовите трёхзначное число, если известно:

543 — 1 бык; 0 коров;
235 — 1 бык; 0 коров.

Пример решения

library(tidyverse)
library(stringi)

df <- c(1, 2, 3, 4, 5) %>%
  tidyr::crossing(d3 = ., d2 = ., d1 = .) %>%
  # отдельно сформируем комбинации
  mutate(comb = purrr::pmap(., c)) %>%
  # оставляем только подходящие сочетания
  mutate(val = stri_join(d3, d2, d1)) %>%
  # учитываем допустимую позиционную раскладку быков
  # 543 -- 1 бык; 0 коров
  filter(stri_detect_regex(val, "5..|.4.|..3")) %>%
  # 235 -- 1 бык; 0 коров
  filter(stri_detect_regex(val, "2..|.3.|..5")) %>%
  # исключим сочетания с совпадающими цифрами
  filter(purrr::map_int(comb, n_distinct) == 3) %>%
  # учитываем наличие только одного быка
  filter(purrr::map(comb, ~length(base::intersect(.x, c(5, 4, 3)))) == 1) %>%
  filter(purrr::map(comb, ~length(base::intersect(.x, c(2, 3, 5)))) == 1) 

df

Заполняем квадрат

Можно ли расставить в клетках квадратной таблицы 4 на 4 десять минусов так, чтобы в каждом столбце было нечётное число минусов, а в каждой строке было чётное число минусов?

Пример решения, вариант 1

# в каждом столбце должно быть нечетное, а в сумме 10. Итоговая разбивка: 3, 3, 3, 1
library(arrangements)
library(foreach)

# пронумеруем все ячейки:
#  1  2  3  4 
#  5  6  7  8
#  9 10 11 12
# 13 14 15 16

cmb <- arrangements::combinations(1:16, k = 10, replace = FALSE)
pryr::object_size(cmb)

# сделаем через итератор, будем отбрасывать комбинации, которые не соотв. условиям
icomb <- icombinations(1:16, k = 10, replace = FALSE)
foreach(x = icomb, .combine=c) %do% {
  # x - вектор с номерами позиций, куда ставим знаки "минус"
  # считаем и проверяем условия для комибнаций
  # колонки
  isOdd <- function(x, set){
    # проверяем нечетность
    length(base::intersect(x, set)) %% 2 == 1 
  }

  isEven <- function(x, set){
    # проверяем четность
    length(base::intersect(x, set)) %% 2 == 0
  }

  col_flag <- all(
    isOdd(x, c(1, 5, 9, 13)),
    isOdd(x, c(2, 6, 10, 14)),
    isOdd(x, c(3, 7, 11, 15)),
    isOdd(x, c(4, 8, 12, 16))
  )

  row_flag <- all(
    isEven(x, c(1, 2, 3, 4)),
    isEven(x, c(5, 6, 7, 8)),
    isEven(x, c(9, 10, 11, 12)),
    isEven(x, c(13, 14, 15, 16))
  )

  if(col_flag && row_flag) print(x)
}

Пример решения, вариант 2

# в каждом столбце должно быть нечетное, а в сумме 10. Итоговая разбивка: 3, 3, 3, 1
library(tidyverse)
library(magrittr)
library(arrangements)
library(foreach)

# пронумеруем все ячейки:
#  1  2  3  4 
#  5  6  7  8
#  9 10 11 12
# 13 14 15 16

# сделаем через итератор, будем отбрасывать комбинации, которые не соотв. условиям
icomb <- icombinations(1:16, k = 10, replace = FALSE)
df <- foreach(x = icomb, .combine = rbind) %do% {
  # x - вектор с номерами позиций, куда ставим знаки "минус"
  # считаем и проверяем условия для комибнаций
  # создаем матрицу
  v <- rep(0, 16)
  # заполним единицами позиции, заполненные минусами
  # browser()
  v[x] <- 1
  m <- matrix(v, nrow = 4, ncol = 4, byrow = TRUE)
  # проверяем условие: в каждом столбце нечётное число минусов, 
  # а в каждой строке чётное число минусов
  if (all(colSums(m) %% 2 == 1) && all(rowSums(m) %% 2 == 0)) 
    x else NULL
}

df %<>% as_tibble(.name_repair = "minimal")

# а так можно посмотреть конкретную раскладочку
v <- rep(0, 16)
# заполним единицами позиции, заполненные минусами
v[purrr::flatten_int(df[5, ])] <- 1
matrix(v, nrow = 4, ncol = 4, byrow = TRUE)

Комбинаторика

Задача

Сколько различных комбинаций из букв, в которых две одинаковые буквы не стоят рядом, можно составить, переставляя буквы К, А, Ш и А ?

Посмотрим на различные соображения Generating all distinct permutations of a list in R

Пример решения

# Разбиваем строку на символы
# https://stackoverflow.com/questions/44918645/split-a-string-into-character-efficiently
lset <- unlist(base::strsplit("КАША", split = "", fixed = TRUE))
# для наших задач честная разбивка не подходит, нам нужно разные А иметь  
lset <- c("К", "А1", "Ш", "А2")
# library(permutations)

df <- tidyr::crossing(p1 = lset, p2 = lset, p3 = lset, p4 = lset)
ff <- function(...){
  vals <- rlang::list2(...)
  # browser()
  n_distinct(unlist(vals))
}
df %>% 
  # mutate(u = purrr::pmap_int(., ~n_distinct(.x)))
  mutate(u = purrr::pmap_int(., ff)) %>%
  filter(u == 4) %>%
  select(-u) %>%
  # соберем все обратно в строку
  mutate(s = purrr::pmap_chr(., stri_join)) %>%
  mutate_at(vars(s), stri_replace_all_regex, pattern = "(А\d+)", replacement = "А") %>%
  distinct(s) %>%
  # исключим повторы букв А
  filter(!stri_detect_fixed(s, "АА"))

Задача

Сколько воскресений может быть в году? Назовите наибольшее возможное число.

Пример решения

# берем високосный год, считаем полное число недель
366 %/% 7
# поглядим на остаток. В максимальном случае он должен попасть на воскресенье
366 %% 7

Задачка про пиратов

Пираты: A, B, C
Высказывание 1
A: У B 2 глаза
B: У C 2 глаза
C: У A 2 глаза

Высказывание 2
A: У нас на всех 2 глаза
B: У нас на всех 3 глаза
C: У нас на всех 4 глаза

Каждый пират наврал столько раз, сколько у него глаз. Сколько глаз у каждого пирата?

Пример решения

df <- tidyr::crossing(a = 0:2, b = 0:2, c = 0:2) %>%
  mutate(total = a + b + c) %>%
  mutate(a_lie = (b != 2) + (total != 2),
         b_lie = (c != 2) + (total != 3),
         c_lie = (a != 2) + (total != 4)) %>%
  filter(a_lie == a, b_lie == b, c_lie == c)
df

И т.д. и т.п.

Для кого-то это может оказаться поводом провести время со своим ребенком.

Предыдущая публикация — «Несколько соображений по поводу параллельных вычислений в R применительно к «enterprise» задачам».

Автор: i_shutov

Источник


* - обязательные к заполнению поля